JUCS - Journal of Universal Computer Science 1(1): 67-82, doi: 10.3217/jucs-001-01-0067
Grammars Based on the Shuffle Operation
expand article infoGheorghe Paun, Grzegorz Rozenberg§, Arto Salomaa|
‡ Institute of Mathematics of the Romanian Academy, Bucharest, Romania§ University of Leiden, Department of Computer Science, Netherlands| Academy of Finland and University of Turku, Department of Mathematics, Turku, Finland
Open Access
Abstract
We consider generative mechanisms producing languages by starting from a finite set of words and shuffling the current words with words in given sets, depending on certain conditions. Namely, regular and finite sets are given for controlling the shuffling: strings are shuffled only to strings in associated sets. Six classes of such grammars are considered, with the shuffling being done on a left most position, on a prefix, arbitrarily, globally, in parallel, or using a maximal selector. Most of the corresponding six families of languages, obtained for finite, respectively for regular selection, are found to be incomparable. The relations of these families with Chomsky language families are briefly investigated.
Keywords
Shuffle operation, Chomsky grammars, L Systems