Abstract of Paper

Unary Pushdown Automata and Auxiliary Space Lower Bounds
by Giovanni Pighizzini

Abstract:

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.