Paper Info
Title
Parikh Image of Pushdown Automata.
Abstract
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 (n) states and (p ge 2n + 4) stack symbols that accepts one single long word for which every equivalent context-free grammar needs (varOmega (n^2(p-2n-4))) variables. This family shows that the classical algorithm for converting a PDA into an equivalent context-free grammar is optimal even when the alphabet is unary. Moreover, we observe that language equivalence and Parikh equivalence, which ignores the ordering between symbols, coincide for this family. We conclude that, when assuming this weaker equivalence, the conversion algorithm is also optimal. Second, Parikh’s theorem motivates the comparison of PDAs against finite state automata. In particular, the same family of unary PDAs gives a lower bound on the number of states of every Parikh-equivalent finite state automaton. Finally, we look into the case of unary deterministic PDAs. We show a new construction converting a unary deterministic PDA into an equivalent context-free grammar that achieves best known bounds.
Year
DOI
Venue
2017
10.1007/978-3-662-55751-8_22
FCT
DocType
Volume
Citations 
Conference
abs/1706.08315
0
PageRank 
References 
Authors
0.34
8
2
Name
Order
Citations
PageRank
Pierre Ganty124220.29
Elena Gutiérrez200.68