The problem of the commutative equivalence of context-free and regular languages is studied. In particular conditions ensuring that a context-free language of exponential growth is commutatively equivalent with a regular language are investigated.
Abstract. The problem of the commutative equivalence of semigroups generated by semi-linear languages is studied. In particular conditions ensuring that the Kleene closure of a bounded semi-linear code is commutatively equivalent to a regular language are investigated.
This paper concerns the structure and the properties of a special class of combinatorial systems called minimal linear grammars. The role of unambiguous minimal linear grammars is investigated in the framework of the information transmission and coding problem and some related issues.
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma
