We investigate the conversion of nondeterministic finite automata and context-free grammars into Parikh equivalent deterministic finite automata, from a descriptional complexity point of view. We prove that for each nondeterministic automaton with n states there exists a Parikh equivalent deterministic automaton with eO( √n·ln n) states. Furthermore, this cost is tight. In contrast, if all the strings accepted by the given automaton contain at least two different letters, then a Parikh equivalent deterministic automaton with a polynomial number of states can be found. Concerning context-free grammars, we prove that for each grammar in Chomsky normal form with n variables there exists a Parikh equivalent deterministic automaton with 2O(n2) states. Even this bound is tight.
Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata / G.J. Lavado, G. Pighizzini, S. Seki. ((Intervento presentato al 13. convegno Italian Conference on Theoretical Computer Science tenutosi a Varese nel 2012.
Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata
G.J. LavadoPrimo
;G. PighizziniSecondo
;
2012
Abstract
We investigate the conversion of nondeterministic finite automata and context-free grammars into Parikh equivalent deterministic finite automata, from a descriptional complexity point of view. We prove that for each nondeterministic automaton with n states there exists a Parikh equivalent deterministic automaton with eO( √n·ln n) states. Furthermore, this cost is tight. In contrast, if all the strings accepted by the given automaton contain at least two different letters, then a Parikh equivalent deterministic automaton with a polynomial number of states can be found. Concerning context-free grammars, we prove that for each grammar in Chomsky normal form with n variables there exists a Parikh equivalent deterministic automaton with 2O(n2) states. Even this bound is tight.File | Dimensione | Formato | |
---|---|---|---|
abstract_parikh_ICTCS2012.pdf
accesso aperto
Descrizione: extended abstract
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
233.55 kB
Formato
Adobe PDF
|
233.55 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.