|Abstract of Paper|
Unary Pushdown Automata and Auxiliary
Space Lower Bounds
by Giovanni Pighizzini
It is well-known that context-free languages defined over a one letter alphabet are regular. This implies that unary pushdown automata and unary context-free grammars can be transformed into equivalent nondeterministic and deterministic finite automata. In this paper, we state some upper bounds on the number of states of the resulting automata, with respect to the size of the descriptions of the given pushdown automata and context-free grammars. As a main consequence, we are able to prove a $\log\log(n)$ lower bound for the workspace used by one-way auxiliary pushdown automata in order to accept nonregular unary languages. The notion of space we consider is the so called weak space. This result, which solves a long standing open problem, shows a further main difference between unary and general languages.