Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 1 / Issue 1

available in:   HTML (41 kB) PDF (215 kB) PS (70 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-001-01-0067


Grammars Based on the Shuffle Operation

Gheorghe Paun (Institute of Mathematics of the Romanian Academy of Sciences, 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: 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: Chomsky grammars, L Systems, Shuffle operation

Categories: F.4.2, F.4.3