7 papers · 1 filter
A Congruence-Based Perspective on Finite Tree Automata
Pierre Ganty, Elena Gutiérrez, Pedro Valero
We provide new insights on the determinization and minimization of tree automata using congruences on trees. From this perspective, we study a Brzozowski's style minimization algor…
On the Use of Quasiorders in Formal Language Theory
Pedro Valero
In this thesis we use quasiorders on words to offer a new perspective on two well-studied problems from Formal Language Theory: deciding language inclusion and manipulating the fin…
A Quasiorder-based Perspective on Residual Automata
Pierre Ganty, Elena Gutiérrez, Pedro Valero
In this work, we define a framework of automata constructions based on quasiorders over words to provide new insights on the class of residual automata. We present a new residualiz…
A Congruence-based Perspective on Automata Minimization Algorithms
Pierre Ganty, Elena Gutiérrez, Pedro Valero
In this work we use a framework of finite-state automata constructions based on equivalences over words to provide new insights on the relation between well-known methods for compu…
Complete Abstractions for Checking Language Inclusion
Pierre Ganty, Francesco Ranzato, Pedro Valero
We study the language inclusion problem where is regular or context-free. Our approach relies on abstract interpretation and checks whether an overapproxi…
Regular Expression Search on Compressed Text
Pierre Ganty, Pedro Valero
We present an algorithm for searching regular expression matches in compressed text. The algorithm reports the number of matching lines in the uncompressed text in time linear in t…
A Language-theoretic View on Network Protocols
Pierre Ganty, Boris Köpf, Pedro Valero
Input validation is the first line of defense against malformed or malicious inputs. It is therefore critical that the validator (which is often part of the parser) is free of bugs…