Review of "Lakshmanan Kuppusamy; A note on ambiguity of internal contextual grammars. Theoret. Comput. Sci. 369 (2006), no. 1-3, 436–441"

Peter R.J. Asveld

    Research output: Contribution to journalBook/Film/Article reviewAcademic

    16 Downloads (Pure)

    Abstract

    An internal contextual grammar (ICG) G=(V,A,(Si,Ci)ni=1) (n≥1) consists of an alphabet V, a finite set A⊆V∗ of axioms, sets of selectors Si⊆V∗, and finite sets of context Ci⊆V∗×V∗ (1≤i≤n). Then x⇒y (i.e., x derives y) iff x=x1x2x3, y=x1ux2vx3 for x1,x2,x3∈V∗, x2∈Si, (u,v)∈Ci for some 1≤i≤n. The language generated by this grammar is {x∈V∗∣w⇒∗x,w∈A}, where ⇒∗ is the reflexive and transitive closure of ⇒. Requiring that the languages Si belong to a family F—frequently restricted to the finite languages or to the regular languages—results in families of internal contextual languages parameterized by F.
    For a derivation δ of G, the sequence of axioms and contexts [and selectors, respectively] used in δ is called the [complete] control sequence of δ. G is 0-ambiguous if there are two different axioms leading to the same word. And G is 1-ambiguous [2-ambiguous] if there are two derivations of a word having different unordered [complete] control sequences. The main results are: (a) there are inherently 1-ambiguous languages generated by ICGs with arbitrary choice that are 0-ambiguous with respect to finite choice, (b) there are inherently 2-ambiguous languages generated by ICGs with arbitrary choice that are 1-ambiguous with respect to regular choice, and (c) there are inherently 2-ambiguous languages with respect to depth-first ICGs with arbitrary choice that are 1-ambiguous with respect to finite choice.
    Original languageEnglish
    Pages (from-to)6366-6367
    Number of pages2
    JournalMathematical reviews
    VolumeMR2277588
    Publication statusPublished - 2007

    Keywords

    • HMI-SLT: Speech and Language Technology

    Fingerprint Dive into the research topics of 'Review of "Lakshmanan Kuppusamy; A note on ambiguity of internal contextual grammars. Theoret. Comput. Sci. 369 (2006), no. 1-3, 436–441"'. Together they form a unique fingerprint.

  • Cite this