Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars

• Autorzy: Fernau Henning , Kuppusamy Lakshmanan , Oladele Rufus O. , Raman Indhumathi

Identyfikatory

DOI

10.3233/FI-2021-2056

• Języki publikacji: EN

Abstrakty

EN

A simple semi-conditional (SSC) grammar is a form of regulated rewriting system where the derivations are controlled either by a permitting string alone or by a forbidden string alone and this condition is specified in the rule. The maximum length i (j, resp.) of the permitting (forbidden, resp.) strings serves as a measure of descriptional complexity known as the degree of such grammars. In addition to the degree, the numbers of nonterminals and of conditional rules are also counted into the descriptional complexity measures of these grammars. We improve on some previously obtained results on the computational completeness of SSC grammars by minimizing the number of nonterminals and / or the number of conditional rules for a given degree (i, j). More specifically we prove, using a refined analysis of a normal form for type-0 grammars due to Geffert, that every recursively enumerable language is generated by an SSC grammar of (i) degree (2, 1) with eight conditional rules and nine nonterminals, (ii) degree (3, 1) with seven conditional rules and seven nonterminals (iii) degree (4, 1) with six conditional rules and seven nonterminals and (iv) degree (4, 1) with eight conditional rules and six nonterminals.

Słowa kluczowe

EN

simple semi-conditional grammars; computational completeness; Geffert normal forms; descriptional complexity measures

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 181, nr 2-3
• Strony: 189--211
• Opis fizyczny: Bibliogr. 21 poz., tab.

Twórcy

autor

Fernau Henning

• CIRT, Fachbereich 4, Universität Trier, D-54286 Trier, Germany

autor

Kuppusamy Lakshmanan

• School of Computer Science and Engineering, VIT, Vellore-632 014, India

autor

Oladele Rufus O.

• Department of Computer Science, University of Ilorin, P.M.B.1515, Ilorin, Nigeria

autor

Raman Indhumathi

• Department of Applied Mathematics and Computational Sciences, PSG College of Technology, Coimbatore-641 004, India

Bibliografia

• [1] Chomsky N. A note on phrase structure grammars. Information and Control (now Information and Computation), 1959. 2:393-395. doi:10.1016/S0019-9958(59)80017-6.
• [2] Chomsky N. On certain formal properties of grammars. Information and Control (now Information and Computation), 1959. 2:137-167. doi:10.1016/S0019-9958(59)90362-6.
• [3] Ginsburg S, Rice HG. Two Families of Languages Related to ALGOL. Journal of the ACM, 1962. 9(3):350-371. doi:10.1145/321127.321132.
• [4] Dassow J, Păun Gh. Regulated Rewriting in Formal Language Theory, volume 18 of EATCS Monographs in Theoretical Computer Science. Springer, 1989. ISBN:978-3-642-74934-6, 1431-2654.
• [5] Fernau H, Freund R, Oswald M, Reinhardt K. Refining the Nonterminal Complexity of Graph-Controlled, Programmed, and Matrix Grammars. Journal of Automata, Languages and Combinatorics, 2007. 12(1/2):117-138.
• [6] Fernau H, Kuppusamy L, Oladele RO. New Nonterminal Complexity Results for Semi-conditional Grammars. In: Manea F, Miller RG, Nowotka D (eds.), Sailing Routes in the World of Computation, 14th Conference on Computability in Europe, CiE, volume 10936 of LNCS. Springer, 2018 pp. 172-182. doi:10.1007/978-3-319-94418-0_18.
• [7] Vaszil G. On the descriptional complexity of some rewriting mechanisms regulated by context conditions. Theoretical Computer Science, 2005. 330:361-373. doi:10.1016/j.tcs.2004.06.032.
• [8] Păun G. A variant of random context grammars: semi-conditional grammars. Theoretical Computer Science, 1985. 41:1-17.
• [9] Meduna A, Gopalaratnam M. On Semi-Conditional Grammars with Productions Having either Forbidding or Permitting Conditions. Acta Cybernetica, 1994. 11:309-323.
• [10] Meduna A, Svec M. Reduction of simple semi-conditional grammars with respect to the number of conditional productions. Acta Cybernetica, 2002. 15(3):353-360. ID:32252297. ISSN:0324-721X.
• [11] Okubo F. A note on the descriptional complexity of semi-conditional grammars. Information Processing Letters, 2009. 110(1):36-40. doi:10.1016/j.ipl.2009.10.002.
• [12] Fernau H, Kuppusamy L, Oladele RO, Raman I. Minimizing Rules and Nonterminals in Semi-conditional Grammars: Non-trivial for the Simple Case. In: Durand-Lose J, Verlan S (eds.), Machines, Computations, and Universality, MCU, volume 10881 of LNCS. Springer, 2018 pp. 88-104. doi:10.1007/978-3-319-92402-1_5.
• [13] Masopust T. A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions. In: Dediu A, Ionescu A, Martín-Vide C (eds.), Language and Automata Theory and Applications, LATA, volume 5457 of LNCS. Springer, 2009 pp. 554-565. doi:10.1007/978-3-642-00982-2_47.
• [14] Geffert V. Normal forms for phrase-structure grammars. RAIRO Informatique théorique et Applications/Theoretical Informatics and Applications, 1991. 25:473-498.
• [15] Masopust T. Formal Models: Regulation and Reduction. Ph.D. thesis, Faculty of Information Technology, Brno University of Technology, Brno, Czech Republic, 2007. ID:125186906.
• [16] Oladele RO, Isah SN. Reduction of Simple Semi-Conditional Grammars. Pacific Journal of Science and Technology, 2017. 18(1):112-116.
• [17] Geffert V. How to generate languages using only two pairs of parentheses. Journal of Information Processing and Cybernetics EIK, 1991. 27(5/6):303-315. ID:26440616.
• [18] Mayer O. Some restrictive devices for context-free languages. Information and Control (now Information and Computation), 1972. 20:69-92. doi:10.1016/S0019-9958(72)90287-2.
• [19] Masopust T, Meduna A. Descriptional Complexity of Generalized Forbidding Grammars. In: Geffert V, Pighizzini G (eds.), 9th International Workshop on Descriptional Complexity of Formal Systems - DCFS. University of Kosice, Slovakia, 2007 pp. 170-177. ISBN:978-80-7097-688-3.
• [20] Fernau H, Kuppusamy L, Oladele RO, Raman I. Improved Descriptional Complexity Results on Generalized Forbidding Grammars. In: Pal SP, Vijayakumar A (eds.), 5th Annual International Conference on Algorithms and Discrete Applied Mathematics CALDAM, volume 11394 of LNCS. Springer, 2019. doi:10.1007/978-3-030-11509-8_15.
• [21] Gazdag Z, Tichler K. On the Power of Permitting Semi-conditional Grammars. In: Charlier É, Leroy J, Rigo M (eds.), Developments in Language Theory - 21st International Conference, DLT, volume 10396 of LNCS. Springer, 2017 pp. 173-184. doi:10.1007/978-3-319-62809-7_12.