Parikh Prime Words and GO-like Territories

Alexandru Mateescu (Academy of Finland and University of Turku, Department of Mathematics, Finland)

Gheorghe Paun (Institute of Mathematics of the Romanian Academy, Romania)

Grzegorz Rozenberg (University of Leiden, Department of Computer Science, The Netherlands)

Arto Salomaa (Academy of Finland and University of Turku, Department of Mathematics, Finland)

Abstract: An n-dimensional vector of natural numbers is said to be prime if the greatest common divisor of its components is one. A word is said to be Parikh prime if its Parikh vector is prime. The languages of Parikh prime and of Parikh non-prime words are investigated (they are neither semilinear nor slender, hence are not context-free or D0L languages, both of them can be generated by matrix grammars with appearance checking). Marking in the plane the points identified by prime (2-dimensional) vectors, interesting patterns of non-marked ("free") points appear (they are similar to the territories in the game of GO). The shape of such possible territories is investigated (with an exhaustive analysis of tro-, tetro-, pento- and hexominoes). Some open problems are formulated (both concerning the mentioned languages and the "GO territories theory").

Keywords: L-systems, Parikh mapping, context free languages, formal languages, word problems

Categories: F.4.2, F.4.3, G.2.1