A note on ambiguity of internal contextual grammars

Simple item page
dc.contributor.authorKuppusamy, L.
dc.date.accessioned2026-02-05T09:37:08Z
dc.date.issued2006
dc.description.abstractIn 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.
dc.identifier.citationTheoretical Computer Science, 2006, 369, 46082, pp. 436-441
dc.identifier.issn3043975
dc.identifier.urihttps://doi.org/10.1016/j.tcs.2006.08.009
dc.identifier.urihttps://idr.nitk.ac.in/handle/123456789/27846
dc.subjectComputational linguistics
dc.subjectFormal languages
dc.subjectMathematical models
dc.subjectProblem solving
dc.subjectDepth-first contextual grammars
dc.subjectInherent ambiguity
dc.subjectInternal contextual grammars
dc.subjectComputational grammars
dc.titleA note on ambiguity of internal contextual grammars

Files

Collections

Journal Articles