Baum angrenzende Grammatik - Tree-adjoining grammar

Die an den Baum angrenzende Grammatik ( TAG ) ist ein von Aravind Joshi definierter Grammatikformalismus . An Bäume angrenzende Grammatiken ähneln kontextfreien Grammatiken , aber die elementare Einheit des Umschreibens ist eher der Baum als das Symbol. Während kontextfreie Grammatiken Regeln zum Umschreiben von Symbolen als Zeichenfolgen anderer Symbole enthalten, gelten für baumnahe Grammatiken Regeln zum Umschreiben der Baumknoten als andere Bäume (siehe Baum (Graphentheorie) und Baum (Datenstruktur) ).

Geschichte

Die TAG entstand aus Untersuchungen von Joshi und seinen Schülern zur Familie der Adjunktionsgrammatiken (AG), der "String-Grammatik" von Zellig Harris . AGs behandeln natürliche und effektive exozentrische Eigenschaften der Sprache, haben jedoch keine gute Charakterisierung endozentrischer Konstruktionen. Das Umgekehrte gilt für das Umschreiben von Grammatiken oder die Phrasenstruktur-Grammatik (PSG). 1969 führte Joshi eine Familie von Grammatiken ein, die diese Komplementarität ausnutzt, indem sie die beiden Arten von Regeln mischt. Einige sehr einfache Umschreiberegeln reichen aus, um das Vokabular von Zeichenfolgen für Zusatzregeln zu generieren. Diese Familie unterscheidet sich von der Chomsky-Schützenberger-Hierarchie , schneidet sie jedoch auf interessante und sprachlich relevante Weise. Die mittleren Zeichenfolgen und Zusatzzeichenfolgen können auch durch eine Abhängigkeitsgrammatik generiert werden , wodurch die Einschränkungen von Umschreibesystemen vollständig vermieden werden.

Beschreibung

Die Regeln in einem TAG sind Bäume mit einem speziellen Blattknoten, dem Fußknoten , der an einem Wort verankert ist. Es gibt zwei Arten von Grund Bäume in TAG: Anfangs Bäume (oft dargestellt als ‚ ‚) und Hilfsbäume (‘ ‘). Anfangsbäume stellen grundlegende Valenzbeziehungen dar, während Hilfsbäume eine Rekursion ermöglichen. Bei Hilfsbäumen sind der Wurzelknoten (oben) und der Fußknoten mit demselben Symbol gekennzeichnet. Eine Ableitung beginnt mit einem Anfangsbaum, der entweder durch Substitution oder Adjunktion kombiniert wird . Die Substitution ersetzt einen Grenzknoten durch einen anderen Baum, dessen oberster Knoten dieselbe Bezeichnung hat. Die Wurzel- / Fußbezeichnung des Hilfsbaums muss mit der Bezeichnung des Knotens übereinstimmen, an den er angrenzt. Eine Adjunktion kann somit den Effekt haben, dass ein Hilfsbaum in die Mitte eines anderen Baums eingefügt wird. ${\ displaystyle \ alpha}$${\ displaystyle \ beta}$

Andere Varianten von TAG ermöglichen Mehrkomponentenbäume , Bäume mit mehreren Fußknoten und andere Erweiterungen.

Komplexität und Anwendung

An Bäume angrenzende Grammatiken sind leistungsfähiger (in Bezug auf die schwache Generationskapazität ) als kontextfreie Grammatiken , jedoch weniger leistungsfähig als lineare kontextfreie Umschreibungssysteme , indizierte oder kontextsensitive Grammatiken.

Ein TAG kann die Sprache der Quadrate (in denen eine beliebige Zeichenfolge wiederholt wird) und die Sprache beschreiben . Diese Art der Verarbeitung kann durch einen eingebetteten Pushdown-Automaten dargestellt werden . Sprachen mit Würfeln (dh dreifachen Zeichenfolgen) oder mit mehr als vier verschiedenen Zeichenfolgen gleicher Länge können nicht durch baumnahe Grammatiken generiert werden. ${\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n} d ^ {n} | 1 \ leq n \}}$

Aus diesen Gründen werden baumnahe Grammatiken häufig als leicht kontextsensitiv beschrieben . Es wird vermutet, dass diese Grammatikklassen leistungsfähig genug sind, um natürliche Sprachen zu modellieren , während sie im allgemeinen Fall effizient analysiert werden können.

Äquivalenzen

Vijay-Shanker und Weir (1994) zeigen , dass die lineare indexierten Grammatiken , kombinatorische Kategorialgrammatik , baum angrenzenden Grammatiken, und Kopf Grammatiken sind schwach äquivalent Formalismen, dass sie alle die gleiche Zeichenfolge Sprachen definieren.

Lexikalisiert

Lexikalisierte baumnahe Grammatiken (LTAG) sind eine Variante der TAG, bei der jeder Elementarbaum (initial oder auxiliary) einem lexikalischen Element zugeordnet ist. Eine lexikalisierte Grammatik für Englisch wurde von der XTAG-Forschungsgruppe des Instituts für kognitionswissenschaftliche Forschung an der University of Pennsylvania entwickelt.

Anmerkungen

Verweise

Externe Links

• Das XTAG-Projekt , das ein TAG für die Verarbeitung natürlicher Sprache verwendet.
• Ein Tutorial zu TAG
• SemConst-Dokumentation Eine kurze Übersicht über Syntax- und semantische Schnittstellenprobleme im TAG-Framework.
• Das TuLiPa-Projekt Die Tübinger Linguistic Parsing Architecture (TuLiPA) ist eine syntaktische (und semantische) Parsing-Umgebung mit mehreren Formalismen, die hauptsächlich für Mehrkomponenten-Baum-angrenzende Grammatiken mit Baumtupeln entwickelt wurde
• Das Metagrammar Toolkit , das verschiedene Tools zum Bearbeiten und Kompilieren von MetaGrammars in TAGs bietet . Es enthält auch eine breite Abdeckung französischer Metagramme.
• LLP2 Ein lexikalisierter Baum neben dem Grammatik- Parser, der eine benutzerfreundliche grafische Umgebung bietet (Seite auf Französisch).