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. Lavado
Primo
;
G. Pighizzini
Secondo
;
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.
17-set-2014
context-free grammars; Parikh equivalence; regular languages; semilinear sets; state complexity
Settore INF/01 - Informatica
Dipartimento di Matematica e Informatica
Universita degli Studi di Perugia
Italian Chapter of the European Association of Theoretical Computer Science (EATCS)
Fondazione Cassa di Risparmio di Perugia
http://www.dmi.unipg.it/ictcs2014/
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.
Conference Object
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/482852
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? ND
social impact