Grammars Based on the Shuffle Operation

Zenodo (CERN European Organization for Nuclear Research)

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.

Authors 3

1. Arto K. Salomaa

   IMAR - Institutul de Matematică „Simion Stoilow” al Academiei Române

   Affiliation as printed

   Institute of Mathematics of the Romanian Academy, Bucharest, Romania

2. Gheorghe Pǎun Aachen Department of Computer Science

   Leiden University

   Affiliation as printed

   University of Leiden, Department of Computer Science, Netherlands

3. Grzegorz Rozenberg

   Research Council of Finland · University of Turku

   Affiliation as printed

   Academy of Finland and University of Turku, Department of Mathematics, Turku, Finland