This is the first paper of a group of three where we prove the following result. Let A be an alphabet of t letters and let psi : A* -> N-t be the corresponding Parikh morphism. Given two languages L-1, L-2 subset of A*, we say that L1 is commutatively equivalent to L-2 if there exists a bijection f : L-1 -> L-2 from L-1 onto L-2 such that, for every u is an element of L-1, psi (u) = psi (f (u). Then every bounded context-free language is commutatively equivalent to a regular language. (C) 2014 Elsevier B.V. All rights reserved.

D'Alessandro, F., Intrigila, B. (2015). On the commutative equivalence of bounded context-free and regular languages: The code case. THEORETICAL COMPUTER SCIENCE, 562, 304-319 [10.1016/j.tcs.2014.10.005].

On the commutative equivalence of bounded context-free and regular languages: The code case

Intrigila, Benedetto
2015-01-01

Abstract

This is the first paper of a group of three where we prove the following result. Let A be an alphabet of t letters and let psi : A* -> N-t be the corresponding Parikh morphism. Given two languages L-1, L-2 subset of A*, we say that L1 is commutatively equivalent to L-2 if there exists a bijection f : L-1 -> L-2 from L-1 onto L-2 such that, for every u is an element of L-1, psi (u) = psi (f (u). Then every bounded context-free language is commutatively equivalent to a regular language. (C) 2014 Elsevier B.V. All rights reserved.
2015
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - INFORMATICA
English
Con Impact Factor ISI
D'Alessandro, F., Intrigila, B. (2015). On the commutative equivalence of bounded context-free and regular languages: The code case. THEORETICAL COMPUTER SCIENCE, 562, 304-319 [10.1016/j.tcs.2014.10.005].
D'Alessandro, F; Intrigila, B
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
DalessandroIntrigila1.pdf

solo utenti autorizzati

Descrizione: Articolo principale
Licenza: Copyright dell'editore
Dimensione 291.35 kB
Formato Adobe PDF
291.35 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/2108/205503
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 9
social impact