Please use this identifier to cite or link to this item:
https://idr.nitk.ac.in/jspui/handle/123456789/9654
Title: | A note on ambiguity of internal contextual grammars |
Authors: | Kuppusamy, L. |
Issue Date: | 2006 |
Citation: | Theoretical Computer Science, 2006, Vol.369, 43891, pp.436-441 |
Abstract: | In this paper, we continue the study of ambiguity of internal contextual grammars which was investigated in Ilie [On ambiguity in internal contextual languages, in: C. Martin-Vide (Ed.), Second Int. Conf. on Mathematical Linguistics, Tarragona, 1996, John Benjamins, Amsterdam, 1997, pp. 29-45] and Martin-Vide et al. [Attempting to define the ambiguity in internal contextual languages, in: C. Martin-Vide (Ed.), Second Int. Conf. on Mathematical Linguistics, Tarragona, 1996, John Benjamins, Amsterdam, 1997, pp. 59-81]. We solve some open problems formulated in these papers. The main results are: (i) there are inherently 1-ambiguous languages with respect to internal contextual grammars with arbitrary choice which are 0-unambiguous with respect to finite choice, (ii) there are inherently 2-ambiguous languages with respect to internal contextual grammars with arbitrary choice which are 1-unambiguous with respect to regular choice, and (iii) there are inherently 2-ambiguous languages with respect to depth-first internal contextual grammars with arbitrary choice which are 1-unambiguous with respect to finite choice. 2006 Elsevier B.V. All rights reserved. |
URI: | 10.1016/j.tcs.2006.08.009 http://idr.nitk.ac.in/jspui/handle/123456789/9654 |
Appears in Collections: | 1. Journal Articles |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.