Regular and linear permutation languages. (English) Zbl 1429.68125
Summary: 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.
Keywords:
permutation languages; interchange rules; context-free grammars; linear grammars; regular grammars; closure properties; decidability; generative powerReferences:
| [1] | B.S. Baker and R.V. Book, Reversal-bounded multipushdown machines. J. Comput. Syst. Sci.88 (1974) 315-332 · Zbl 0309.68043 |
| [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. · Zbl 1459.68099 |
| [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 · Zbl 1371.68148 |
| [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 0980.68066 |
| [5] | G. Horváth and B. Nagy, Pumping lemmas for linear and nonlinear context-free languages. Acta Univ. Sapientiae, Informatica2 (2010) 194-209 · Zbl 1218.68096 |
| [6] | Z. Krivka and A. Meduna, Jumping grammars. Int. J. Found. Comput. Sci.26 (2015) 709-732 · Zbl 1332.68104 · doi:10.1142/S0129054115500409 |
| [7] | G. Madejski, Infinite hierarchy of permutation languages. Fundam. Inform.130 (2014) 263-274 · Zbl 1359.68175 |
| [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 · Zbl 1423.68261 |
| [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 · Zbl 1283.68199 · doi:10.1142/S0129054112500244 |
| [12] | B. Nagy, Languages generated by context-free grammars extended by type AB -> BA rules. J. Autom. Lang. Comb.14 (2009) 175-186 · Zbl 1206.68178 |
| [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 · Zbl 1264.68100 |
| [15] | B. Nagy, Linguistic power of permutation languages by regular help, in Bio-Inspired Models for Natural and Formal Languages, edited by G. Bel-Enguix and M.D. Jiménez-López. Cambridge Scholars, Cambridge (2011) 135-152 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
