Cesko.wiki Gramatika spojování stromů
Technology
12 hours ago
8
4
2
Author
Albert FloresGramatika spojování stromů je teoretickou matematickou disciplínou, která se zabývá kombinováním dvou nebo více stromů do jednoho souvislého stromu. Tato disciplína je významná pro teorii formálních jazyků a syntaktickou analýzu. Cílem je nalézt algoritmy a metody, které umožní spojování stromů s co nejmenšími náklady a s minimálními konflikty. Existuje několik přístupů k tomuto problému, včetně Bottom-Up Trees Grammar (BUG), Sequitur, Left-corner parsing a dalších. V České republice se tímto tématem zabývá nejen akademická sféra, ale také některé společnosti a výzkumné ústavy.
Gramatika spojování stromů, anglicky Tree-adjoining grammar (TAG), je gramatický formalismus definovaný Aravindem Joshim. Stromové gramatiky jsou do jisté míry podobné bezkontextovým gramatikám, ale základní jednotkou přepisu je strom, nikoli symbol. Zatímco bezkontextové gramatiky mají pravidla pro přepis symbolů jako řetězců jiných symbolů, stromové gramatiky mají pravidla pro přepis uzlů stromů do jiných stromů. TAG se skládá z několika elementárních stromů, které lze kombinovat pomocí včlenění stromů do jiných stromů.
TAG je lexikálně orientovaný matematický formalismus, který dokáže přesně zachytit syntaktické vlastnosti přirozených jazyků (například angličtiny, francouzštiny či korejštiny).