Showing 2019Show all
3 papers · 1 filter
cs.FL2019
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…
cs.FL2019
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…
cs.FL2019
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…