Inherent Ambiguity of Languages Generated by Spine Grammars
Summary :
There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, head grammars, and combinatory categorial grammars. It is known that these models of grammars have the same generative power of string languages and fall into the class of mildly context-sensitive grammars. For an automaton, it is known that the class of languages accepted by transfer pushdown automata is exactly the class of linear indexed languages. In this paper, deterministic transfer pushdown automata is introduced. We will show that the language accepted by a deterministic transfer pushdown automaton is generated by an unambiguous spine grammar. Moreover, we will show that there exists an inherently ambiguous language.
- Publication
- IEICE TRANSACTIONS on Information Vol.E88-D No.6 pp.1150-1158
- Publication Date
- 2005/06/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietisy/e88-d.6.1150
- Type of Manuscript
- PAPER
- Category
- Automata and Formal Language Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ikuo KAWAHARADA, Takumi KASAI, "Inherent Ambiguity of Languages Generated by Spine Grammars" in IEICE TRANSACTIONS on Information,
vol. E88-D, no. 6, pp. 1150-1158, June 2005, doi: 10.1093/ietisy/e88-d.6.1150.
Abstract: There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, head grammars, and combinatory categorial grammars. It is known that these models of grammars have the same generative power of string languages and fall into the class of mildly context-sensitive grammars. For an automaton, it is known that the class of languages accepted by transfer pushdown automata is exactly the class of linear indexed languages. In this paper, deterministic transfer pushdown automata is introduced. We will show that the language accepted by a deterministic transfer pushdown automaton is generated by an unambiguous spine grammar. Moreover, we will show that there exists an inherently ambiguous language.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.6.1150/_p
Copy
@ARTICLE{e88-d_6_1150,
author={Ikuo KAWAHARADA, Takumi KASAI, },
journal={IEICE TRANSACTIONS on Information},
title={Inherent Ambiguity of Languages Generated by Spine Grammars},
year={2005},
volume={E88-D},
number={6},
pages={1150-1158},
abstract={There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, head grammars, and combinatory categorial grammars. It is known that these models of grammars have the same generative power of string languages and fall into the class of mildly context-sensitive grammars. For an automaton, it is known that the class of languages accepted by transfer pushdown automata is exactly the class of linear indexed languages. In this paper, deterministic transfer pushdown automata is introduced. We will show that the language accepted by a deterministic transfer pushdown automaton is generated by an unambiguous spine grammar. Moreover, we will show that there exists an inherently ambiguous language.},
keywords={},
doi={10.1093/ietisy/e88-d.6.1150},
ISSN={},
month={June},}
Copy
TY - JOUR
TI - Inherent Ambiguity of Languages Generated by Spine Grammars
T2 - IEICE TRANSACTIONS on Information
SP - 1150
EP - 1158
AU - Ikuo KAWAHARADA
AU - Takumi KASAI
PY - 2005
DO - 10.1093/ietisy/e88-d.6.1150
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2005
AB - There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, head grammars, and combinatory categorial grammars. It is known that these models of grammars have the same generative power of string languages and fall into the class of mildly context-sensitive grammars. For an automaton, it is known that the class of languages accepted by transfer pushdown automata is exactly the class of linear indexed languages. In this paper, deterministic transfer pushdown automata is introduced. We will show that the language accepted by a deterministic transfer pushdown automaton is generated by an unambiguous spine grammar. Moreover, we will show that there exists an inherently ambiguous language.
ER -
English
