On the Trade-off Between Ambiguity and Complexity in Contextual Languages

• Autorzy: Kuppusamy L. , Mahendran A. , Krithivasan K.
• Języki publikacji: EN

Abstrakty

EN

Contextual grammars are introduced by Solomon Marcus in 1969 based on the fundamental concept of descriptive linguistics of insertion of strings in given contexts. Internal contextual grammars are introduced by Pǎun and Nguyen in 1980. For contextual grammars several descriptional complexity measures and levels of ambiguity have been defined. In this paper, we analyze the trade-off between ambiguity and complexity of languages generated by internal contextual grammars. The notion of a pseudo inherently ambiguous language with respect to two complexity measures is introduced and investigated. These languages can be generated by unambiguous grammars which are minimal with respect to one measure and ambiguous if they are minimal with respect to the other measure. An open problem from [15] is solved in this framework.

Słowa kluczowe

EN

inherently ambiguous; unambiguous; descriptional complexity measures; internal contextual grammars

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 122, nr 4
• Strony: 315--326
• Opis fizyczny: Bibliogr. 17 poz., rys., tab.

Twórcy

autor

Kuppusamy L.

• School of Computing Science and Engineering VIT University, Vellore 632 014, India

autor

Mahendran A.

• School of Computing Science and Engineering VIT University, Vellore 632 014, India

autor

Krithivasan K.

• Department of Computer Science and Engineering IIT Madras, Chennai 600 036, India

Bibliografia

• [1] Georgescu, G.: The syntactic complexity of internal contextual grammars and languages, II International Conference on Mathematical Linguistics (C. Martin-Vide, Ed.), 17–28, Amsterdam, 1996.
• [2] Gruska, J.: Descriptional complexity of context-free languages, Proc. Mathematical Foundations of Computer Science’73, 71–84, High Tatras, 1973.
• [3] Ilie, L.: On ambiguity in internal contextual languages, II International Conference on Mathematical Linguistics (C. Martin-Vide, Ed.), 29–45, John Benjamins, Amsterdam, 1997.
• [4] Ilie, L.: On computational complexity of contextual languages. Theoretical Computer Science, 183/1, 1997, 33–44.
• [5] Krishna, S.N., Lakshmanan, K., Rama, R.: On some classes of contextual grammars. International Journal of Computer Mathematics, 80/2, 2003, 151–164.
• [6] Kudlek, M.: On probabilistic contextual grammars, Fundamenta Informaticae, 64/1-4, 2005, 255–260.
• [7] Lakshmanan, K.: Incompatible measures of internal contextual grammars, Proc. Descriptional Complexity of Formal Systems’05, (C. Mereghetti, B. Palano, G. Pighizzini, D. Wotschke, Eds.), 253–260, Como, Italy, 2005.
• [8] Lakshmanan, K.: A note on ambiguity of internal contextual grammars, Theoretical Computer Science, 369, 2006, 436-441.
• [9] Lakshmanan, K.: New classes of contextual grammars for mildly context sensitive formalisms. Book chapter in New Topics in Theoretical Computer Science (N. Oleg, Terikhovsky, N. William, Burton, Eds.). Nova Publishers, USA. 2008, 1–25.
• [10] Marcus, S.: Contextual grammars, Rev. Roum. Pures. Appl. 14, 1969, 1525–1534.
• [11] Martin-Vide, C., Miguel-Verges, J., P˘aun, Gh., Salomaa, A.: Attempting to define the ambiguity in internal contextual languages, II International Conference on Mathematical Linguistics (C. Martin-Vide Ed.), 59–81, John Benjamins, Amsterdam, 1997.
• [12] Păun, Gh.: On the complexity of contextual grammars with choice, Stud. Cerc. Matem. 27, 1975, 559–569.
• [13] Păun, Gh.: Contextual grammars, The Publ. House of the Romanian Academy of Sciences, Bucuresti, 1982.
• [14] Păun, Gh.: Further remarks on the syntactical complexity of Marcus contextual languages, Ann. Univ. Buc., Ser. Matem.-Inform., 1991, 72–82.
• [15] Păun, Gh.: Marcus contextual grammars, Kluwer Academic Publishers, 1997.
• [16] Păun, Gh., Nguyen, X.M.: On the inner contextual grammars, Rev. Roum. Pures. Appl., 25, 1980, 641–651.
• [17] Păun, Gh., Rozenberg, G., Salomaa, A.: Contextual grammars: erasing, determinism, one-side contexts, In: Proceedings of Developments in Language Theory-DLT’1993, 1993, Finland, 370–388.