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 ψ:A⁎⟶Nt be the corresponding Parikh morphism. Given two languages L1,L2⊆A⁎, 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 code case / D'Alessandro, Flavio; Benedetto, Intrigila. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 562:(2014), pp. 304-319. [10.1016/j.tcs.2014.10.005]
On the commutative equivalence of bounded context-free and regular languages: the code case
D'ALESSANDRO, Flavio;
2014
Abstract
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 ψ:A⁎⟶Nt be the corresponding Parikh morphism. Given two languages L1,L2⊆A⁎, 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
