We investigate, under Parikh equivalence, the state complexity of some language operations which preserve regularity. For union, concatenation, Kleene star, complement, intersection, shue, and reversal, we obtain a polynomial state complexity over any xed alphabet, in contrast to the intrinsic exponential state complexity of some of these operations in the classical version. For projection we prove a superpolynomial state complexity, which is lower than the exponential one of the corresponding classical operation. We also prove that for each two deterministic automata A and B it is possible to obtain a deterministic automaton with a polynomial number of states whose accepted language has as Parikh image the intersection of the Parikh images of the languages accepted by A and B.
Operational State Complexity under Parikh Equivalence / G.J. Lavado, G. Pighizzini, S. Seki. ((Intervento presentato al 15. convegno The Italian Conference on Theoretical Computer Science tenutosi a Perugia nel 2014.
Operational State Complexity under Parikh Equivalence
G.J. LavadoPrimo
;G. PighizziniSecondo
;
2014
Abstract
We investigate, under Parikh equivalence, the state complexity of some language operations which preserve regularity. For union, concatenation, Kleene star, complement, intersection, shue, and reversal, we obtain a polynomial state complexity over any xed alphabet, in contrast to the intrinsic exponential state complexity of some of these operations in the classical version. For projection we prove a superpolynomial state complexity, which is lower than the exponential one of the corresponding classical operation. We also prove that for each two deterministic automata A and B it is possible to obtain a deterministic automaton with a polynomial number of states whose accepted language has as Parikh image the intersection of the Parikh images of the languages accepted by A and B.File | Dimensione | Formato | |
---|---|---|---|
abstract_ICTCS2014.pdf
accesso aperto
Descrizione: extended abstract
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
261.87 kB
Formato
Adobe PDF
|
261.87 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.