Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete

• Autorzy: Křivka Zbyněk , Meduna Alexander

Identyfikatory

DOI

10.3233/FI-2021-2028

• Języki publikacji: EN

Abstrakty

EN

This paper investigates the reduction of scattered context grammars with respect to the number of non-context-free productions. It proves that every recursively enumerable language is generated by a scattered context grammar that has no more than one non-context-free production. An open problem is formulated.

Słowa kluczowe

EN

scattered context grammars; size reduction; number of non-context-free productions; parallel productions; computational completeness; descriptional complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 179, nr 4
• Strony: 361--384
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Křivka Zbyněk

• Brno University of Technology, Faculty of Information Technology, IT4Innovations Centre of Excellence, Božetěchova 2, 612 66 Brno, Czech Republic

autor

Meduna Alexander

• Brno University of Technology, Faculty of Information Technology, IT4Innovations Centre of Excellence, Božetěchova 2, 612 66 Brno, Czech Republic

Bibliografia

• [1] Rozenberg G, Salomaa A (eds.). Handbook of Formal Languages, Vol. 1: Word, Language, Grammar. Springer, New York, 1997.
• [2] Greibach S, Hopcroft J. Scattered Context Grammars. Journal of Computer and System Sciences, 1969. 3:233-247.
• [3] Meduna A, Techet J. Scattered Context Grammars and their Applications. WIT Press, UK. WIT Press, 2010. ISBN 978-1-84564-426-0. URL http://www.fit.vutbr.cz/research/view_pub.php?id=8997.
• [4] Masopust T. On the descriptional complexity of scattered context grammars. Theor. Comput. Sci., 2009. 410(1):108-112. doi:10.1016/j.tcs.2008.10.017. URL https://doi.org/10.1016/j.tcs.2008.10.017.
• [5] Masopust T. Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals. Fundam. Inform., 2010. 99(4):473-480. doi:10.3233/FI-2010-258. URL https://doi.org/10.3233/FI-2010-258.
• [6] Křivka Z, Martiško J, Meduna A. CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages. International Journal of Foundations of Computer Science, in press. URL https://www.fit.vut.cz/research/publication/11604.
• [7] Csuhaj-Varjú E, Vaszil G. Scattered context grammars generate any recursively enumerable languages with two nonterminals. Information Processing Letters, 2010. 110(20):902-907.
• [8] Meduna A. Generative power of three-nonterminal scattered context grammars. Theoretical Computer Science, 2000. 246(1):279-284. doi:https://doi.org/10.1016/S0304-3975(00)00153-5. URL http://www.sciencedirect.com/science/article/pii/S0304397500001535.
• [9] Meduna A. Automata and Languages: Theory and Applications. Springer, London, 2000.
• [10] Meduna A, Zemek P. Regulated Grammars and Automata. Springer, 2014. ISBN 978-1-4939-0368-9. URL http://www.fit.vutbr.cz/research/view_pub.php?id=10498.
• [11] Kleijn HCM, Rozenberg G. On the generative power of regular pattern grammars. Acta Informatica, 1983. 20(4):391-411. doi:10.1007/BF00264281. URL https://doi.org/10.1007/BF00264281.
• [12] Kolář D, Meduna A. Regulated Pushdown Automata. Acta Cybernetica, 2000. 2000(4):653-664. URL https://www.fit.vut.cz/research/publication/6020.
• [13] Meduna A, Horáček P, Tomko M. Handbook of Mathematical Models for Languages and Computation. The Institution of Engineering and Technology, 2020. ISBN 978-1-78561-659-4

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).