For each sufficiently large n, there exists a unary regular language L such that both L and its complement L c are accepted by unambiguous nondeterministic automata with at most n states, while the smallest deterministic automata for these two languages still require a superpolynomial number of states, at least e^{\Omega(\sqrt[3]{n\cdot\ln^{2}\n})} . Actually, L and L c are “balanced” not only in the number of states but, moreover, they are accepted by nondeterministic machines sharing the same transition graph, differing only in the distribution of their final states. As a consequence, the gap between the sizes of unary unambiguous self-verifying automata and deterministic automata is also superpolynomial.
Pairs of complementary unary languages with “balanced” nondeterministic automata / V. Geffert, G. Pighizzini. - In: ALGORITHMICA. - ISSN 0178-4617. - 63:3(2012), pp. 571-587. ((Intervento presentato al convegno LATIN 2010.
Pairs of complementary unary languages with “balanced” nondeterministic automata
G. PighizziniUltimo
2012
Abstract
For each sufficiently large n, there exists a unary regular language L such that both L and its complement L c are accepted by unambiguous nondeterministic automata with at most n states, while the smallest deterministic automata for these two languages still require a superpolynomial number of states, at least e^{\Omega(\sqrt[3]{n\cdot\ln^{2}\n})} . Actually, L and L c are “balanced” not only in the number of states but, moreover, they are accepted by nondeterministic machines sharing the same transition graph, differing only in the distribution of their final states. As a consequence, the gap between the sizes of unary unambiguous self-verifying automata and deterministic automata is also superpolynomial.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.