| Issue |
RAIRO-Theor. Inf. Appl.
Volume 52, Number 2-3-4, April–December 2018
8th Workshop on Non-classical Models of Automata and Applications (NCMA 2016)
|
|
|---|---|---|
| Page(s) | 219 - 234 | |
| DOI | https://doi.org/10.1051/ita/2018016 | |
| Published online | 07 February 2019 | |
Regular Article
Regular and linear permutation languages
Institute of Informatics, Faculty of Mathematics, Physics, and Informatics, University of Gdańsk,
80-308
Gdańsk, Poland.
* Corresponding author: gmadejsk@inf.ug.edu.pl
Accepted: 21 November 2018
A permutation rule is a non-context-free rule whose both sides contain the same multiset of symbols with at least one non-terminal. This rule does not add or substitute any symbols in the sentential form, but can be used to change the order of neighbouring symbols. In this paper, we consider regular and linear grammars extended with permutation rules. It is established that the generative power of these grammars relies not only on the length of the permutation rules, but also whether we allow or forbid the usage of erasing rules. This is quite surprising, since there is only one non-terminal in sentential forms of derivations for regular or linear grammars. Some decidability problems and closure properties of the generated families of languages are investigated. We also show a link to a similar model which mixes the symbols: grammars with jumping derivation mode.
Mathematics Subject Classification: 68Q42 / 68Q85
Key words: Permutation languages / interchange rules / context-free grammars / linear grammars / regular grammars / closure properties / decidability / generative power
© EDP Sciences, 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.