We investigate, under Parikh equivalence, the state complexity of some language operations which preserve regularity. For union, concatenation, Kleene star, complement, intersection, shuffle, and reversal, we obtain a polynomial state complexity over any fixed 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. Finally, we prove that for each finite set there exists a small context-free grammar defining a language with the same Parikh image.
Operational state complexity under Parikh equivalence / G.J. Lavado, G. Pighizzini, S. Seki - In: Descriptional complexity of formal systems : 16th international workshop, DCFS 2014 : Turku, Finland, august 5-8, 2014 : proceedings / [a cura di] H. Jürgensen, J. Karhumäki, A. Okhotin. - Cham : Springer, 2014. - ISBN 9783319097039. - pp. 294-305 (( Intervento presentato al 16. convegno International Workshop DCFS tenutosi a Turku, Finland nel 2014.
Operational state complexity under Parikh equivalence
G.J. Lavado;G. Pighizzini;
2014
Abstract
We investigate, under Parikh equivalence, the state complexity of some language operations which preserve regularity. For union, concatenation, Kleene star, complement, intersection, shuffle, and reversal, we obtain a polynomial state complexity over any fixed 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. Finally, we prove that for each finite set there exists a small context-free grammar defining a language with the same Parikh image.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.