Article

Free access

Tree adjoining and head wrapping

Authors:

K. Vijay-Shanker,

David J. Weir,

Aravind K. JoshiAuthors Info & Claims

COLING '86: Proceedings of the 11th coference on Computational linguistics

Pages 202 - 207

https://doi.org/10.3115/991365.991425

Published: 25 August 1986 Publication History

PDF eReader

Abstract

In this paper we discuss the formal relationship between thw classes of languages generated by Tree Adjoining Grammars and Head Grammars. In particular, we show that Head Languages are included in Tree Adjoining Languages and that Tree Adjoining Grammars are equivalent to a modification of Head Grammars called Modified Head Grammars. The inclusion of MHL in HL, and thus the equivalence of HG's and TAG's in the most general case remains to be established.

References

[1]

Gorn, S. 1962 Processors for Infinite Codes of the Shannon-Fano type, Proc. of Symp. Math. Theory of Automata.

Google Scholar

[2]

Joshi, A. K. 1983 How Much Context Sensitivity is Necessary for Characterizing Structural Descriptions-Tree Adjoining Grammars, in Natural Language Processing-Theoretical Computational and Psychological Perspectives, eds D. Dowty, L. Karttunen, A. Zwicky, Cambridge University Press, New York.

Google Scholar

[3]

Joshi, A. K., Levy, L. and Takahashi, M. 1975 Tree Adjunct Grammars. Jour. Comp. Sys. Sci. 10(1): 136--163.

Digital Library

Google Scholar

[4]

Joshi, A. K., Vijay-Shanker, K. and Weir, D. J. 1986 Tree Adjoining Grammars and Head Grammars, Tech. Rep., MS-CIS-86-1, Dept of CIS, Univ. of Pennsylvania.

Google Scholar

[5]

Kroch, A. and Joshi, A. K. 1985 The Linguistic Relevance of Tree Adjoining Grammars, Tech. Rep., MS-CIS-85-18, Dept. of CIS, Univ. of Pennsylvania.

Google Scholar

[6]

Pollard, C. 1894 Head Grammars. Ph.D. dissertation, Standford Univ., California.

Google Scholar

[7]

Roach, K. 1984 Formal Properties of Head Grammars, Manuscript, Standford University. To appear in Mathematics of Language, ed. A. Manaster-Ramer, Amsterdam: John Benjamins.

Google Scholar

[8]

Rounds, W. C. 1985 LFP: A Logic for Linguistic Descriptions and an Analysis of its Complexity, Unpublished Manuscript Univ. of Mich., Ann Arbor, Sept 1985.

Google Scholar

[9]

Vijay-Shanker, K. and Joshi, A. K. 1985 Some Computational Properties of Tree Adjoining Grammars. Proc. of 23rd Meeting of Assoc. Comp. Ling., 82--93.

Digital Library

Google Scholar

[10]

Weir, D. J., Vijay-Shanker, K. and Joshi, A. K. 1986 The Relationship Between Tree Adjoining Grammars and Head Grammars, Proc. of 24th Meeting of Assoc. Comp. Ling.

Digital Library

Google Scholar

Cited By

View all

Schabes YWaters R(1995)Tree insertion grammarComputational Linguistics10.5555/218355.21836321:4(479-513)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/218355.218363
Groenink AAbney SHinrichs E(1995)Literal movement grammarsProceedings of the seventh conference on European chapter of the Association for Computational Linguistics10.3115/976973.976987(90-97)Online publication date: 27-Mar-1995
https://dl.acm.org/doi/10.3115/976973.976987
Staudacher PKrauwer SMoortgat Mdes Tombe LKlein E(1993)New frontiers beyond context-freenessProceedings of the sixth conference on European chapter of the Association for Computational Linguistics10.3115/976744.976786(358-367)Online publication date: 21-Apr-1993
https://dl.acm.org/doi/10.3115/976744.976786
Show More Cited By

Tree adjoining and head wrapping
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Adjoining tree-to-string translation
HLT '11: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1

We introduce synchronous tree adjoining grammars (TAG) into tree-to-string translation, which converts a source tree to a target string. Without reconstructing TAG derivations explicitly, our rule extraction algorithm directly learns tree-to-string ...
An Earley-type parsing algorithm for Tree Adjoining Grammars
ACL '88: Proceedings of the 26th annual meeting on Association for Computational Linguistics

We will describe an Earley-type parser for Tree Adjoining Grammars (TAGs). Although a CKY-type parser for TAGs has been developed earlier (Vijay-Shanker and Joshi, 1985), this is the first practical parser for TAGs because as is well known for CFGs, the ...
A study of tree adjoining grammars

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

COLING '86: Proceedings of the 11th coference on Computational linguistics

August 1986

697 pages

Program Chair:
Makoto Nagao
Kyoto University, Japan

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 25 August 1986

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,537 of 1,537 submissions, 100%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
242
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)4

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Schabes YWaters R(1995)Tree insertion grammarComputational Linguistics10.5555/218355.21836321:4(479-513)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/218355.218363
Groenink AAbney SHinrichs E(1995)Literal movement grammarsProceedings of the seventh conference on European chapter of the Association for Computational Linguistics10.3115/976973.976987(90-97)Online publication date: 27-Mar-1995
https://dl.acm.org/doi/10.3115/976973.976987
Staudacher PKrauwer SMoortgat Mdes Tombe LKlein E(1993)New frontiers beyond context-freenessProceedings of the sixth conference on European chapter of the Association for Computational Linguistics10.3115/976744.976786(358-367)Online publication date: 21-Apr-1993
https://dl.acm.org/doi/10.3115/976744.976786
Weir DJoshi AHobbs J(1988)Combinatory Categorial GrammarsProceedings of the 26th annual meeting on Association for Computational Linguistics10.3115/982023.982057(278-285)Online publication date: 7-Jun-1988
https://dl.acm.org/doi/10.3115/982023.982057
Joshi AOrtony AWilks Y(1987)Unification and some new grammatical formalismsProceedings of the 1987 workshop on Theoretical issues in natural language processing10.3115/980304.980314(45-50)Online publication date: 7-Jan-1987
https://dl.acm.org/doi/10.3115/980304.980314
Weir DVijay-Shanker KJoshi ABiermann A(1986)The relationship between Tree Adjoining Grammars and Head GrammarsProceedings of the 24th annual meeting on Association for Computational Linguistics10.3115/981131.981142(67-74)Online publication date: 10-Jul-1986
https://dl.acm.org/doi/10.3115/981131.981142

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

Adjoining tree-to-string translation

An Earley-type parsing algorithm for Tree Adjoining Grammars

A study of tree adjoining grammars

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations