Parikh Prime Words and GO-like Territories
Дата
Авторы
Mateescu,Alexandru
Paun,Gheorghe
Rozenberg,Grzegorz
Salomaa,Arto
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
formal languages , context free languages , L-systems , Parikh mapping , word problems