JUCS - Journal of Universal Computer Science 1(12): 790-810, doi: 10.3217/jucs-001-12-0790
Parikh Prime Words and GO-like Territories
expand article infoAlexandru Mateescu‡, Gheorghe Paun§, Grzegorz Rozenberg|, Arto Salomaa‡
‡ Academy of Finland and University of Turku, Department of Mathematics, Turku, Finland§ Institute of Mathematics of the Romanian Academy, Bucharest, Romania| University of Leiden, Department of Computer Science, Netherlands

Corresponding author: Alexandru Mateescu

© Alexandru Mateescu, Gheorghe Paun, Grzegorz Rozenberg, Arto Salomaa.
This article is freely available under the J.UCS Open Content License.
Citation: Mateescu A, Paun G, Rozenberg G, Salomaa A (1995) Parikh Prime Words and GO-like Territories. JUCS - Journal of Universal Computer Science 1(12): 790-810. https://doi.org/10.3217/jucs-001-12-0790
Open Access
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"). 1.) Research supported by the Academy of Finland, project 11281, and the ESPRIT Basic Research Working Group ASMICS II.
Keywords
formal languages, context free languages, L-systems, Parikh mapping, word problems