Gramatika přidání stromu

Gramatika sousedící se stromem TAG ) je formální gramatika , kterou vynalezl Aravind Joshi ( anglicky  Tato gramatika zobecňuje bezkontextovou gramatiku v tom, že elementárními jednotkami v pravidlech odvozování jsou spíše stromy než jednotlivé znaky. Gramatika tedy definuje pravidla pro nahrazení uzlů stromu podstromy (viz strom v teorii grafů a strom v informatice ).

Historie

TAG vznikl jako výsledek výzkumu Joshiho a jeho studentů rodiny adjunkčních gramatik [1] . Přílohové gramatiky se dobře hodí pro analýzu frází, které obsahují hlavní slovo a mnoho závislých slov, která zužují význam hlavního slova (například "velmi velký dům"). Jasně však necharakterizují fráze, ve kterých ani jedno slovo nemůže nést funkci celé struktury. Totéž platí pro gramatiku s frázovou strukturou . V roce 1969 představil Joshi rodinu gramatik, které tuto komplementaritu využívaly smícháním dvou typů pravidel. Tato rodina není součástí Chomského hierarchie [2] a patří mezi slabě kontextové gramatiky , tedy z hlediska generujících vlastností je silnější než bezkontextové gramatiky , ale slabší než kontextové [3] . Stromové sčítací gramatiky jsou slabě ekvivalentní lineárním indexovaným gramatikám , kombinatorickým kategorickým gramatikám a hlavičkovým gramatikám [4] (pro libovolnou stromovou sčítací gramatiku lze sestavit odpovídající gramatiku z kterékoli z těchto tří rodin, které budou generovat stejné řetězce).

Popis

Pravidlo TAG je strom s listovým uzlem, ke kterému lze připojit slovo (LTAG).

Existují dva typy stromů: "počáteční" (často označované jako ' ') a "pomocné" (' '). Počáteční stromy představují hlavní valence fráze, zatímco pomocné stromy umožňují použití rekurze [5] . Pomocné stromy mají horní a listový uzel označeny stejným symbolem.

Náhrady začínají od původního stromu a provádějí se nahrazením nebo přidáním . Nahrazení nahrazuje uzel stromem, jehož horní uzel je označen stejným symbolem jako nahrazovaný uzel. Append vloží pomocný podstrom do středu stromu [6] . Pomocný strom musí být označen stejným štítkem jako uzel, ke kterému je připojen.

Poznámky

  1. ↑ Joshi, Aravind; S. R. Kosaraju, H. Yamada. Řetězcové doplňkové gramatiky  (neopr.) . — Proceedings Desáté výroční symposium o teorii automatů, Waterloo, Kanada, 1969.
  2. ↑ Joshi, Aravind. Vlastnosti formálních mluvnic se smíšenými typy pravidel a jejich jazyková relevance  (anglicky)  : journal. - Proceedings Third International Symposium on Computational Linguistics, Stockholm, Švédsko, 1969.
  3. ↑ Joshi, Aravind. Jak velká kontextová citlivost je nezbytná pro charakterizaci strukturálních popisů // Zpracování přirozeného jazyka: teoretické, výpočetní a psychologické perspektivy  (anglicky) / D. Dowty, L. Karttunen a A. Zwicky, (eds.). - New York, NY: Cambridge University Press , 1985. - S. 206-250.
  4. ↑ Vijay-Shanker, K. and Weir, David J. 1994. The Equivalence of Four Extensions of Context-Free Grammars . Teorie matematických systémů 27 (6): 511-546.
  5. ↑ Jurafský, Daniel; James H. Martin. Zpracování řeči a jazyka  (neurčité) . - Upper Saddle River, NJ: Prentice Hall , 2000. - s  . 354 .
  6. ↑ Joshi, Aravind; Owen Rambow (2003). „Formalismus pro gramatiku závislostí založený na gramatice sousedící se stromem“ (PDF) . Sborník příspěvků z konference o teorii významového textu . Použitý zastaralý parametr |coauthors=( nápověda ) Archivováno 29. listopadu 2020 na Wayback Machine

Odkazy

V angličtině: