### Abstract

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 language | English |
---|---|

Pages (from-to) | 6366-6367 |

Number of pages | 2 |

Journal | Mathematical reviews |

Volume | MR2277588 |

Publication status | Published - 2007 |

### Fingerprint

### Keywords

- HMI-SLT: Speech and Language Technology

### Cite this

*Mathematical reviews*,

*MR2277588*, 6366-6367.

}

*Mathematical reviews*, vol. MR2277588, pp. 6366-6367.

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

Research output: Contribution to journal › Book/Film/Article review › Academic

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 -