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.

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.

DOI : 10.1051/ita/2018016
Classification : 68Q42, 68Q85
Mots clés : Permutation languages, interchange rules, context-free grammars, linear grammars, regular grammars, closure properties, decidability, generative power
Madejski, Grzegorz 1

1
@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] B.S. Baker and R.V. Book, Reversal-bounded multipushdown machines. J. Comput. Syst. Sci. 8 (1974) 315–332 | DOI | MR | Zbl

[2] W. Czerwinski and S. Lasota, 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 B. Luttik and M.A. Reniers. Vol. 89 of EPTCS, Open Publishing Association, Waterloo (2012) 35–48.

[3] H. Fernau, M. Paramasivan, M.L. Schmid and V. Vorel, Characterization and complexity results on jumping finite automata. Theor. Comput. Sci. 679 (2017) 31–52 | DOI | MR | Zbl

[4] J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley Series in Computer Science. Addison-Wesley-Longman, MA (2001) | Zbl

[5] G. Horváth and B. Nagy, Pumping lemmas for linear and nonlinear context-free languages. Acta Univ. Sapientiae, Informatica 2 (2010) 194–209 | Zbl

[6] Z. Krivka and A. Meduna, Jumping grammars. Int. J. Found. Comput. Sci. 26 (2015) 709–732 | DOI | MR | Zbl

[7] G. Madejski, Infinite hierarchy of permutation languages. Fundam. Inform. 130 (2014) 263–274 | DOI | MR | Zbl

[8] G. Madejski, 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 F. Drewes. Vol. 9223 of Lecture Notes in Computer Science. Springer, Cham (2015) 211–223 | MR | Zbl

[9] G. Madejski, 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 H. Bordihn, R. Freund, B. Nagy and G. Vaszil. TU Wien, Vienna (2016) 25–33

[10] G. Madejski, 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 H. Bordihn, R. Freund, B. Nagy and G. Vaszil, Vol. 321 of books@ocg.at. Österreichische Computer Gesellschaft, Wien( 2016) 243–258

[11] A. Meduna and P. Zemek, Jumping finite automata. Int. J. Found. Comput. Sci. 23 (2012) 1555–1578 | DOI | MR | Zbl

[12] B. Nagy, Languages generated by context-free grammars extended by type AB -> BA rules. J. Autom. Lang. Comb. 14 (2009) 175–186 | MR | Zbl

[13] B. Nagy, 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 J. Cabestany, F.S. Hernández, A. Prieto and J.M. Corchado. Vol. 5517 of Lecture Notes in Computer Science. Springer, Berlin, Heidelberg (2009) 504–511

[14] B. Nagy, 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 M. Ito, Y. Kobayashi and K. Shoji. World Scientific, Singapore (2010) 163–178 | MR | Zbl

[15] B. Nagy, Linguistic power of permutation languages by regular help, in Bio-Inspired Models for Natural and Formal Languages, edited byG. Bel-Enguix and M.D. Jiménez-López. Cambridge Scholars, Cambridge (2011) 135–152

Cité par Sources :