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.
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 |
Keywords
- HMI-SLT: Speech and Language Technology