3 papers
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.FL2018
The Parikh Property for Weighted Context-Free Grammars
Pierre Ganty, Elena Gutiérrez
Parikh's Theorem states that every context-free grammar (CFG) is equivalent to some regular CFG when the ordering of symbols in the words is ignored. The same is not true for the s…
cs.FL2017
Parikh Image of Pushdown Automata
Pierre Ganty, Elena Gutiérrez
We compare pushdown automata (PDAs for short) against other representations. First, we show that there is a family of PDAs over a unary alphabet with states and …