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.
Mots clés : Permutation languages, interchange rules, context-free grammars, linear grammars, regular grammars, closure properties, decidability, generative power
@article{ITA_2018__52_2-3-4_219_0,
author = {Madejski, Grzegorz},
editor = {Bordihn, Henning and Nagy, Benedek and Vaszil, Gy\"orgy},
title = {Regular and linear permutation languages},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {219--234},
publisher = {EDP-Sciences},
volume = {52},
number = {2-3-4},
year = {2018},
doi = {10.1051/ita/2018016},
mrnumber = {3915310},
zbl = {1429.68125},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2018016/}
}
TY - JOUR AU - Madejski, Grzegorz ED - Bordihn, Henning ED - Nagy, Benedek ED - Vaszil, György TI - Regular and linear permutation languages JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2018 SP - 219 EP - 234 VL - 52 IS - 2-3-4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2018016/ DO - 10.1051/ita/2018016 LA - en ID - ITA_2018__52_2-3-4_219_0 ER -
%0 Journal Article %A Madejski, Grzegorz %E Bordihn, Henning %E Nagy, Benedek %E Vaszil, György %T Regular and linear permutation languages %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2018 %P 219-234 %V 52 %N 2-3-4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2018016/ %R 10.1051/ita/2018016 %G en %F ITA_2018__52_2-3-4_219_0
Madejski, Grzegorz. Regular and linear permutation languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 2-3-4, pp. 219-234. doi : 10.1051/ita/2018016. http://www.numdam.org/articles/10.1051/ita/2018016/
[1] and , Reversal-bounded multipushdown machines. J. Comput. Syst. Sci. 8 (1974) 315–332 | DOI | MR | Zbl
[2] and , Partially-commutative context-free languages, in Proceedings Combined 19th International Workshop on Expressiveness in Concurrency and 9th Workshop on Structured Operational Semantics, EXPRESS/SOS 2012, Newcastle upon Tyne, UK, September 3, 2012, edited by and . Vol. 89 of EPTCS, Open Publishing Association, Waterloo (2012) 35–48.
[3] , , and , Characterization and complexity results on jumping finite automata. Theor. Comput. Sci. 679 (2017) 31–52 | DOI | MR | Zbl
[4] , and , Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley Series in Computer Science. Addison-Wesley-Longman, MA (2001) | Zbl
[5] and , Pumping lemmas for linear and nonlinear context-free languages. Acta Univ. Sapientiae, Informatica 2 (2010) 194–209 | Zbl
[6] and , Jumping grammars. Int. J. Found. Comput. Sci. 26 (2015) 709–732 | DOI | MR | Zbl
[7] , Infinite hierarchy of permutation languages. Fundam. Inform. 130 (2014) 263–274 | DOI | MR | Zbl
[8] , The membership problem for linear and regular permutation languages, in Implementation and Application of Automata – 20th International Conference, CIAA 2015, Umeå, Sweden, August 18–21, 2015, Proceedings, edited by . Vol. 9223 of Lecture Notes in Computer Science. Springer, Cham (2015) 211–223 | MR | Zbl
[9] , Jumping and pumping lemmas and their applications, in Eighth Workshop on Non-Classical Models of Automata and Applications, NCMA 2016, Debrecen, Hungary, August 29–30, 2016. Short Papers, edited by , , and . TU Wien, Vienna (2016) 25–33
[10] , Regular and linear permutation languages, in Eighth Workshop on Non-Classical Models of Automata and Applications, NCMA 2016, Debrecen, Hungary, August 29–30, 2016. Proceedings, edited by , , and , Vol. 321 of books@ocg.at. Österreichische Computer Gesellschaft, Wien( 2016) 243–258
[11] and , Jumping finite automata. Int. J. Found. Comput. Sci. 23 (2012) 1555–1578 | DOI | MR | Zbl
[12] , Languages generated by context-free grammars extended by type AB -> BA rules. J. Autom. Lang. Comb. 14 (2009) 175–186 | MR | Zbl
[13] , Permutation languages in formal linguistics, in Bio-Inspired Systems: Computational and Ambient Intelligence, 10th International Work-Conference on Artificial Neural Networks, IWANN 2009, Salamanca, Spain, June 10–12, 2009. Proceedings, Part I, edited by , , and Vol. 5517 of Lecture Notes in Computer Science. Springer, Berlin, Heidelberg (2009) 504–511
[14] , On a hierarchy of permutation languages, in Automata, Formal Languages and Algebraic Systems. Proceedings of AFLAS 2008, Kyoto, Japan, September 20–22, 2008, edited by , and World Scientific, Singapore (2010) 163–178 | MR | Zbl
[15] , Linguistic power of permutation languages by regular help, in Bio-Inspired Models for Natural and Formal Languages, edited by and . Cambridge Scholars, Cambridge (2011) 135–152
Cité par Sources :
