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.
|Titolo:||Operational state complexity under Parikh equivalence|
|Parole Chiave:||context-free grammars; Parikh equivalence; regular languages; semilinear sets; state complexity|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2014|
|Digital Object Identifier (DOI):||10.1007/978-3-319-09704-6_26|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|