2012/08/24 by Tomáš Masopust, Masopust, Tomáš
Computer Science · #68Q45 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #msc:68Q45
paper · pdf · doi:10.48550/arxiv.1208.5002
arxiv created 2012/08/24 · arxiv updated 2012/08/27
Recently, an infinite hierarchy of languages accepted by stateless deterministic pushdown automata has been established based on the number of pushdown symbols. However, the witness language for the n-th level of the hierarchy is over an input alphabet with 2(n-1) elements. In this paper, we improve this result by showing that a binary alphabet is sufficient to establish this hierarchy. As a consequence of our construction, we solve the open problem formulated by Meduna et al. Then we extend these results to m-state realtime deterministic pushdown automata, for all m at least 1. The existence of such a hierarchy for m-state deterministic pushdown automata is left open.