The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-free Tree Grammars

Journal of Logic, Language and Information 20 (3):361-384 (2011)
  Copy   BIBTEX

Abstract

The equivalence of leaf languages of tree adjoining grammars and monadic linear context-free grammars was shown about a decade ago. This paper presents a proof of the strong equivalence of these grammar formalisms. Non-strict tree adjoining grammars and monadic linear context-free grammars define the same class of tree languages. We also present a logical characterisation of this tree language class showing that a tree language is a member of this class iff it is the two-dimensional yield of an MSO-definable three-dimensional tree language

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Second-order abstract categorial grammars as hyperedge replacement grammars.Makoto Kanazawa - 2010 - Journal of Logic, Language and Information 19 (2):137-161.
Lexicalized Non-Local MCTAG with Dominance Links is NP-Complete.Lucas Champollion - 2011 - Journal of Logic, Language and Information 20 (3):343-359.
Highly constrained unification grammars.Daniel Feinstein & Shuly Wintner - 2008 - Journal of Logic, Language and Information 17 (3):345-381.
A descriptive characterisation of linear languages.Tore Langholm - 2006 - Journal of Logic, Language and Information 15 (3):233-250.
Product-free Lambek calculus and context-free grammars.Mati Pentus - 1997 - Journal of Symbolic Logic 62 (2):648-660.

Analytics

Added to PP
2011-07-16

Downloads
31 (#503,056)

6 months
5 (#629,136)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Variation in mild context-sensitivity.Robert Frank & Tim Hunter - 2021 - Evolutionary Linguistic Theory 3 (2):181-214.

Add more citations

References found in this work

No references found.

Add more references