Regular and linear permutation languages

Grzegorz Madejski

Abstract

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.
Author Grzegorz Madejski (FMPI / II)
Grzegorz Madejski,,
- Institute of Informatics
Journal seriesRairo-Theoretical Informatics and Applications, ISSN 0988-3754, (A 15 pkt)
Issue year2018
Vol52
No2-4
Pages219-234
Publication size in sheets0.75
Conference8th Workshop on Non-Classical Models of Automata and Applications (NCMA), 29-08-2016 - 30-08-2016, Debrecen, Węgry
Keywords in Englishpermutation languages, interchange rules, context-free grammars, linear grammars, regular grammars,closure properties, decidability, generative power
ASJC Classification1706 Computer Science Applications; 2600 General Mathematics; 1712 Software
DOIDOI:10.1051/ita/2018016
URL https://www.rairo-ita.org/articles/ita/pdf/first/ita180062.pdf
Languageen angielski
Score (nominal)0
ScoreMinisterial score = 0.0, 24-07-2019, ArticleFromConference
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2017 = 0.506; WoS Impact Factor: 2017 = 0.35 (2) - 2017=0.403 (5)
Citation count*
Cite
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.
Back