This is the third paper of a group of three where we prove the following result. Let A be an alphabet of t letters and let ψ be the corresponding Parikh morphism. Given two languages L1, L2, we say that L1 is commutatively equivalent to L2 if there exists a bijection f: L1 →L2 from L1 onto L2 such that, for every u∈L1, ψ(u)=ψ(f(u)). Then every bounded context-free language is commutatively equivalent to a regular language.
On the commutative equivalence of bounded context-free and regular languages: the semi-linear case / D'Alessandro, Flavio; B., Intrigila. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 572:(2015), pp. 1-24. [10.1016/j.tcs.2015.01.008]
On the commutative equivalence of bounded context-free and regular languages: the semi-linear case
D'ALESSANDRO, Flavio
;
2015
Abstract
This is the third paper of a group of three where we prove the following result. Let A be an alphabet of t letters and let ψ be the corresponding Parikh morphism. Given two languages L1, L2, we say that L1 is commutatively equivalent to L2 if there exists a bijection f: L1 →L2 from L1 onto L2 such that, for every u∈L1, ψ(u)=ψ(f(u)). Then every bounded context-free language is commutatively equivalent to a regular language.| File | Dimensione | Formato | |
|---|---|---|---|
|
Dalessandro_On-the-commutative-equivalence_2015.pdf
accesso aperto
Note: link al prodotto sul sito dell’editore: https://doi.org/10.1016/j.tcs.2014.10.005
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Creative commons
Dimensione
361.24 kB
Formato
Adobe PDF
|
361.24 kB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
