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.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.