PARIKH MATRIX MAPPING AND LANGUAGES
Radu-Florian Atanasiu · International Journal of Foundations of Computer Science · 2010
Restricting the Parikh Matrix mapping to a language rather than to an alphabet rises a set of problems that seem interesting to us. Moreover, amiability (or M -equivalence as it is named by other authors) is exploited in order to characterise certain types of languages. The paper also proposes a series of results establishing relations between classes of languages defined by Parikh matrix mappings and the Chomsky hierarchy. Finally, a result related to word composition concludes the paper, showing that for every two arbitrary words there exist two other words such that their composition (two by two) is amiable.