Length-Reducing Automata (Almost) Without Auxiliary Symbols
Artur Jeż, Tomasz Jurdziński · Universitätsbibliothek Gießen · 2011
Length-reducing two-pushdown automaton (lr-tpda) is a machine model for growing context-sensitive languages and Church-Rosser languages, the language classes complementing and refining the Chomsky hierarchy. These automata are closely related to restarting automata, an analytic model for some natural language processing techniques. While the latter model was considered in numerous variants depending on usage of the auxiliary symbols, lr-tpdas were always assumed to use the auxiliary symbols in non-limited way. We study lr-tpdas with limited usage of auxiliary symbols. We show that, the deterministic automata without auxiliary symbols can recognize all deterministic context-free languages. Moreover, non-deterministic automata using one extra alphabet symbol can recognize all context-free languages. Next, we inspect automata over one-letter alphabet, without auxiliary symbol. We show that even this restricted variant of lr-tpdas is quite powerful. Finally, we show that most of our constructions are stateless.