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

12 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

Fingerprint

Contextual Grammars
Ambiguous
Internal
Axioms
Selector
Finite Set
Arbitrary
Review
Ambiguity
Transitive Closure
Unordered
Language
Grammar

Keywords

  • HMI-SLT: Speech and Language Technology

Cite this

@article{555ffcb5dcb442728a09f2de41cf5bdb,
title = "Review of {"}Lakshmanan Kuppusamy; A note on ambiguity of internal contextual grammars. Theoret. Comput. Sci. 369 (2006), no. 1-3, 436–441{"}",
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.",
keywords = "HMI-SLT: Speech and Language Technology",
author = "Asveld, {Peter R.J.}",
year = "2007",
language = "English",
volume = "MR2277588",
pages = "6366--6367",
journal = "Mathematical reviews",
issn = "0025-5629",
publisher = "American Mathematical Society",

}

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

In: Mathematical reviews, Vol. MR2277588, 2007, p. 6366-6367.

Research output: Contribution to journalBook/Film/Article reviewAcademic

TY - JOUR

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

AU - Asveld, Peter R.J.

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

KW - HMI-SLT: Speech and Language Technology

M3 - Book/Film/Article review

VL - MR2277588

SP - 6366

EP - 6367

JO - Mathematical reviews

JF - Mathematical reviews

SN - 0025-5629

ER -