Trädtilläggsgrammatik

Tree -adjoining grammatik TAG ) är en formell grammatik uppfunnen av Aravind Joshi ( engelska  Denna grammatik generaliserar den sammanhangsfria grammatiken genom att de elementära enheterna i slutledningsreglerna är träd snarare än enskilda tecken. Sålunda definierar grammatiken reglerna för att ersätta trädnoder med underträd (se träd i grafteori och träd i datavetenskap ).

Historik

TAG uppstod som ett resultat av forskning av Joshi och hans elever i en familj av tilläggsgrammatiker [1] . Bifogade grammatiker är väl lämpade för att analysera fraser som innehåller ett huvudord och många beroende ord som begränsar betydelsen av huvudordet (till exempel "ett mycket stort hus"). Men de karakteriserar inte tydligt fraser där inte ett enda ord kan bära hela strukturens funktion. Detsamma gäller grammatik med frasstruktur . 1969 introducerade Joshi en familj av grammatiker som utnyttjade denna komplementaritet genom att blanda två typer av regler. Denna familj är inte en del av Chomsky-hierarkin [2] och tillhör svagt kontextkänsliga grammatiker , det vill säga när det gäller genererande egenskaper är den starkare än sammanhangsfria grammatiker , men svagare än sammanhangskänsliga [3] . Trädadditionsgrammatik är svagt likvärdiga med linjärt indexerade grammatiker , kombinatoriska kategoriska grammatiker och rubrikgrammatik [4] (för vilken trädadditionsgrammatik som helst kan man konstruera en motsvarande grammatik från vilken som helst av dessa tre familjer som kommer att generera samma strängar).

Beskrivning

En TAG-regel är ett träd med en lövnod till vilken ett ord (LTAG) kan fästas.

Det finns två typer av träd: "initial" (ofta kallad ' ') och "hjälp" (' '). De initiala träden representerar frasens huvudsakliga valenser, medan hjälpträden tillåter användning av rekursion [5] . Hjälpträd har toppnoden och lövnoden markerade med samma symbol.

Ersättningar börjar från det ursprungliga trädet och görs genom substitution eller tillägg . En ersättare ersätter en nod med ett träd vars toppnod är märkt med samma symbol som den som ersätts. Append infogar ett extra underträd i mitten av trädet [6] . Ett hjälpträd måste märkas med samma etikett som noden som det är fäst vid.

Anteckningar

  1. ↑ Joshi, Aravind; S.R. Kosaraju, H. Yamada. Stråkadjunktgrammatik  (neopr.) . — Proceedings Tenth Annual Symposium on Automatateory, Waterloo, Kanada, 1969.
  2. ↑ Joshi, Aravind. Egenskaper hos formell grammatik med blandade typer av regler och deras språkliga relevans  (engelska)  : journal. - Proceedings Third International Symposium on Computational Linguistics, Stockholm, Sverige, 1969.
  3. ↑ Joshi, Aravind. Hur mycket kontextkänslighet krävs för att karakterisera strukturella beskrivningar // Natural Language Processing: Theoretical, Computational, and Psychological Perspectives  (engelska) / D. Dowty, L. Karttunen, och A. Zwicky, (red.). - New York, NY: Cambridge University Press , 1985. - S. 206-250.
  4. ↑ Vijay-Shanker, K. och Weir, David J. 1994. Ekvivalensen av fyra förlängningar av kontextfria grammatiker . Mathematical Systems Theory 27(6): 511-546.
  5. ↑ Jurafsky, Daniel; James H. Martin. Tal- och språkbehandling  (obestämd tid) . - Upper Saddle River, NJ: Prentice Hall , 2000. - s  . 354 .
  6. ↑ Joshi, Aravind; Owen Rambow (2003). "En formalism för beroendegrammatik baserad på trädangränsande grammatik" (PDF) . Proceedings of the Conference on Meaning-Text Theory . Utfasad parameter används |coauthors=( hjälp ) Arkiverad 29 november 2020 på Wayback Machine

Länkar

På engelska: