Regular and linear permutation languages
AbstractA 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.
|Journal series||Rairo-Theoretical Informatics and Applications, ISSN 0988-3754, (A 15 pkt)|
|Publication size in sheets||0.75|
|Conference||8th Workshop on Non-Classical Models of Automata and Applications (NCMA), 29-08-2016 - 30-08-2016, Debrecen, Węgry|
|Keywords in English||permutation languages, interchange rules, context-free grammars, linear grammars, regular grammars,closure properties, decidability, generative power|
|ASJC Classification||; ;|
|Score||= 15.0, 28-01-2020, ArticleFromConference|
|Publication indicators||: 2017 = 0.506; : 2018 = 0.282 (2) - 2018=0.245 (5)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.