Regular and linear permutation languages

Grzegorz Madejski


A permutation rule is a non-context-free rule whose both sides contain the same multisetof symbols with at least one non-terminal. This rule does not add or substitute any symbols in thesentential form, but can be used to change the order of neighbouring symbols. In this paper, we considerregular and linear grammars extended with permutation rules. It is established that the generativepower of these grammars relies not only on the length of the permutation rules, but also whether weallow or forbid the usage of erasing rules. This is quite surprising, since there is only one non-terminal insentential forms of derivations for regular or linear grammars. Some decidability problems and closureproperties of the generated families of languages are investigated. We also show a link to a similarmodel which mixes the symbols: grammars with jumping derivation mode.
Publication typeIn press (online first, early view)
Author Grzegorz Madejski (FMPI / II)
Grzegorz Madejski,,
- Institute of Informatics
Journal seriesRairo-Theoretical Informatics and Applications, ISSN 0988-3754, (A 15 pkt)
Issue year2019
Noonline first
Publication size in sheets0.75
Keywords in Englishpermutation languages, interchange rules, context-free grammars, linear grammars, regular grammars,closure properties, decidability, generative power
Languageen angielski
Score (nominal)15
ScoreMinisterial score = 15.0, 28-02-2019, ArticleFromJournal
Ministerial score (2013-2016) = 15.0, 28-02-2019, ArticleFromJournal
Publication indicators WoS Impact Factor: 2017 = 0.35 (2) - 2017=0.403 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.