Operational State Complexity under Parikh Equivalence (Extended Abstract)
Giovanna J. Lavado, Giovanni Pighizzini · Archivio Istituzionale della Ricerca (Universita Degli Studi Di Milano) · 2014
We investigate, under Parikh equivalence, the state complex- ity of some language operations which preserve regularity. For union, concatenation, Kleene star, complement, intersection, shue, and rever- sal, 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 superpoly- nomial state complexity, which is lower than the exponential one of the corresponding classical operation. We also prove that for each two de- terministic 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 lan- guages accepted by A and B.