Advertisement
Published in:
2010 | OriginalPaper | Chapter
The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-Free Tree Grammars
Authors : Stephan Kepser, James Rogers
Published in: The Mathematics of Language
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
It has been observed quite early after the introduction of Tree Adjoining Grammars that the adjoining operation seems to be a special case of the more general deduction step in a context-free tree grammar (CFTG) derivation. TAGs look like special cases of a subclass of CFTGs, namely monadic linear CFTGs. More than a decade ago it was shown that the two grammar formalisms are indeed weakly equivalent, i.e., define the same classes of string languages. This paper now closes the remaining gap showing the strong equivalence for so-called non-strict TAGs, a variant of TAGs where the restrictions for head and foot nodes are slightly generalised.