ITAT 2016 Proceedings, CEUR Workshop Proceedings Vol. 1649, pp. 26–33 http://ceur-ws.org/Vol-1649, Series ISSN 1613-0073, c 2016 M. Plátek, K. Oliva Redukční analýza A-stromů s minimalistickými omezeními.∗ Martin Plátek1 a Karel Oliva2 1 MFF UK Praha, Malostranské nám. 25, 118 00 Praha, Česká Republika martin.platek@ufal.mff.cuni.cz 2 UJČ ČAV Praha, Letenská, 118 00 Praha, Česká Republika oliva@ujc.cas.cz Abstrakt: Tento příspěvek navazuje na náš loňský pří- strukturální pozorování a nekombinujeme je (zatím) s po- spěvek na ITATu. Zpracovává novým způsobem redukční zorováními statistického typu. analýzu na A-stromech, které jsou formalizací stromů, zpracovaných metodikou pro analytickou rovinu Praž- 1.1 Neformální úvod do redukční analýzy. ského závislostního korpusu (PDT). Redukční analýza A- stromů sestává z minimálních korektních redukcí, které V této sekci neformálně představujeme redukční analýzu používají pouze elementární operace delete a shift. A-stromů se závislostmi a s koordinacemi. Redukční ana- Hlavním cílem je vyvinout formální prostředky, které lýzou českých vět a jejímu modelování se zabýváme již by exaktně zachycovaly lingvisticky pozorované minima- delší dobu. Jako základní variantu redukční analýzy před- listické vlastnosti jednotlivých parametrů stromové re- kládáme úplnou redukční analýzu A-stromů (URAS). Na- dukční analýzy stromů ve formátu PDT a dovolily ná- vazujeme na články z minulých let (viz [2, 1, 3]). Při za- sledně realizovat podobná pozorování na různých přiro- vádění variant redukčních analýz zvýrazňujeme jejich mi- zených, či umělých jazycích. nimalistický charakter. Pomocí pozorování lingvistického typu upřesňujeme URAS je založena na postupném zjednodušování A- strukturálně-složitostní vlastnosti A-stromů se závislostmi stromu po minimálních krocích. URAS definuje všechny a koordinacemi. Zvýrazňujeme vlastnosti, kterými se zá- možné posloupnosti větných redukcí – každá redukce spo- vislosti a koordinace liší. čívá ve vypuštění několika uzlů, nejméně však jednoho uzlu analyzovaného A-stromu. V A-stromě vypouštíme 1 Úvod tak, abychom z A-stromu získali opět A-strom a každá cesta v novém A-stromě byla podposloupností cesty v pů- V této práci zavádíme a studujeme exaktní pojem (úplné) vodním A-stromě. Viz např. obrázky z příkladu 1. V někte- redukční analýzy A-stromů (URAS). A-stromy modelují rých redukcích může být kromě vypouštění použita ope- stromy analytické roviny Pražského závislostního korpusu race shift, která přesune nějaký uzel na novou pozici v A- (PDT). URAS obsahuje všechny korektní redukce, které stromě. lze zařadit do lingvisticky korektní (manuální) redukční V našich lingvistických pozorováních budeme rozlišo- analýzy na A-stromech. URAS používá operace delete a vat vypouštění listů a vypouštění vnitřních uzlů. Kořeny se shift a jeho redukce jsou minimalizovány s ohledem na v URAS nevypouští. Intuitivně i v URAS u většiny závis- počet těchto operací. Postupně zavádíme různé další ome- lostních jevů stačí používat vypouštění listů. Ukážeme, že zující parametry, které je možno minimalizovat a užívat redukce koordinací v PDT s vypouštěním listů nevystačí. pro jemnější aproximace lingvisticky intuitivní redukční Metoda URAS je popsaná následujícími zásadami: analýzy. Zavádíme tříčlennou škálu stability pro omezené URAS. Za korektní omezené URAS považujeme ty, co (i) URAS je složena z jednotlivých redukcí; redukce po- jsou stabilní alespoň v tom nejslabším smyslu. Stabilita užívají operace dvou typů : (1) vypuštění (delete) pomáhá hledat spodní odhady pro intuitivní redukční ana- a (2) přesun (shift); To znamená, že tvary jednotli- lýzu. Typ stability určuje větší či menší vzdálenost od ne- vých slov (i interpunkčních znamének), jejich morfo- omezené URAS. logické charakteristiky i jejich syntaktické kategorie Zavedené pojmy používáme pro klasifikaci pozorování se nemění během jednotlivých redukcí. lingvistického typu. Pozorujeme množiny A-stromů, které odpovídají českým větám a jsou zpracovány metodikou (ii) Struktura, která je korektním A-stromem, musí být analytické roviny PDT. Odkrýváme tak řadu strukturál- korektním A-stromem i po redukci. ních vlastností takovýchto A-stromů. Povšimněme si, že (iii) Redukce nepatří do předem vytipované množiny za- prezentovaná pozorování jsou smysluplná a netriviální na kázaných redukcí. Příkladem zakázané redukce je vy- konečných i nekonečných jazycích (množinách). To je nechání samotného zvratného ´se´. ve spojitosti s lingvistikou velmi užitečné. Prezentujeme ∗ Příspěvek prezentuje výsledky dosažené v rámci projektu agentury (iv) Uvažujeme jen nezmenšitelné redukce, t.j. GAČR číslo GA15-04960S. vynecháme-li z libovolné redukce jednu či více Redukční analýza A-stromů s minimalistickými omezeními 27 operací, nastane porušení principu zachování grama- tické správnosti (ii) nebo redukce se stane zakázanou Rozhodl.Pred a tím poruší princip (iii). ..AuxK Rozhodl.Pred se.AuxT ..AuxK odstoupit.Obj (v) URAS obsahuje všechny možné redukce splňující zá- se.AuxT odstoupit.Obj sady (i) až (iv). dnes.Adv dnes.Adv URAS tvoří základ, z kterého budeme odvozovat další Obrázek 2: A-stromy T11 a T12 nad větou (1). varianty redukční analýzy, tak aby odpovídaly některým typům lingvistické (minimalisticé) intuice. Tento záměr budeme rozvíjet především ve formální části. Rozhodl.Pred V následujících odstavcích nejprve uvedeme jeden pří- ..AuxK Rozhodl.Pred klad ilustrující URAS. Příklad se týká jen redukcí, které se.AuxT odstoupit.Obj ..AuxK zjednodušují závislosti. Později budou následovat pří- dnes.Adv se.AuxT klady, týkající se koordinací. Příklady nejprve poslouží pro dnes.Adv úvod do problematiky, později (ve výsledkové části) jako separační příklady pro taxonomii redukčních analýz. A- stromy na obrázcích v našich příkladech jsou oproti stro- Obrázek 3: Redukce T12 na T13 . mům z PDT trochu zjednodušené. Za prvé: neobsahují identifikační uzel, který nenese žádnou syntaktickou infor- stromů přirozených jazyků, tak i podobných struktur u maci a neodpovídá žádnému slovu věty. Za druhé: značka programovacích a dotazovacích jazyků. V podsekcích, ’Coord’ je nahrazena značkou ’Cr’ a za třetí vynecháváme prezentujících pozorování lingvistického typu, se budeme morfologické značky. věnovat formulaci redukčních vlastností stromů analytické Všimněme si, že korektní A-strom zcela určuje jednu roviny PDT. Značka ⊂ znamená v celém příspěvku vlastní korektní českou větu i s jejím korektním značkováním. podmnožinu. Formalizace redukční analýzy analytických stromů se Příklad 1. Zde ilustrujeme URAS k větě (1). Nevypouš- neobejde bez formalizace lexikální analýzy. tíme zvratnou částici se, nebot’ vypuštění pouhé zvratné částice považujeme za zakázanou redukci. Zde vůbec ne- používáme shift. 2.1 Formalizace lexikální analýzy (1) Rozhodl.Pred se.AuxT dnes.Adv odstoupit.Sb ..AuxK Obrázek 1 reprezentuje schema větné redukční ana- Při formalizaci lexikální analýzy rozlišujeme tři konečné lýzy (tzv. UPRA). Isomorfní (velmi podobné) schema mají množiny slov a značek. Σ p označuje tzv. vlastní slovník 1 , který obsahuje jednotlivé slovní formy a interpunkční URAS A-stromů T11 a T12 z obrázku 2. Obrázek 1 zde za- stupuje i tato schemata. znaménka daného jazyka. Σc označuje tzv. kategoriální se- V jednotlivých redukcích URAS A-stromu T11 se vy- znam, tedy množinu syntakticko-morfologických značek. pouštějí jen listy, tedy redukcemi nevznikají nové hrany. U Hlavní slovník Γ ⊆ Σ p × Σc reprezentuje zjednoznačněnou T12 , při redukci položky ’odstoupit.Sb’, se vypouští vnitřní lexikální analýzu daného jazyka. uzel A-stromu, tedy vzniká nová hrana a to v tomto případě Projekce z Γ+ do Σ∗p resp. do Σ∗c přirozeně definujeme signalizuje změnu významu. To není žádoucí. pomocí homomorfismů: slovníkovým homomorfismem h p : Vznikne tak strom T13 , viz obr. 3. Doplňme, že T11 a Γ → Σ p a kategoriálním homomorfismem hc : Γ → Σc : T12 lze redukovat na T14 a T13 lze také redukovat na T15 . h p ([a, b]) = a a hc ([a, b]) = b pro všechny [a, b] ∈ Γ. Obrázky těchto redukcí jsme vynechali. K tomuto příkladu Příklad 2. V našich pozorováních analytické roviny PDT patří ještě obrázek 4, zobrazující redukci T14 na T15 . pracujeme s hlavním slovníkem označeným jako ΓPDT , Σ pPDT označuje vlastní slovník a ΣcPDT označuje katego- Rozhodl.Pred se.AuxT dnes.Adv odstoupit.Sb ..AuxK riální seznam značek, užívaných v PDT. Rozhodl.Pred se.AuxT odstoupit.Sb ..AuxK Rozhodl.Pred se.AuxT dnes.Adv ..AuxK Rozhodl.Pred Rozhodl.Pred se.AuxT ..AuxK ..AuxK Rozhodl.Pred se.AuxT odstoupit.Obj ..AuxK Obrázek 1: UPRA věty (1). se.AuxT 2 Formalizace redukční analýzy. Obrázek 4: Redukce T14 na T15 . Zde zavedeme obecné formální pojmy, které mohou slou- 1 Index p při označení abecedy se vztahuje na anglickou verzi, kde žit k formulaci redukčních vlastností jak závislostních se používá slovo proper 28 M. Plátek, K. Oliva Výše definované pojmy ilustrujeme na příklade, který vy- nebo Str(ord) = w, a říkáme, že w je řetězem (projekcí) chází z příkladu 1. A-stromu s nebo řetězem (projekcí) R-seznamu ord. { Rozhodl, se, dnes , odstoupit, . } ⊂ Σ pPDT , Normalizace. Říkáme, že A-strom s = (V, E, ord) (R- { Pred, AuxT, Adv, Sb, AuxK} ⊂ ΣcPDT , seznam ord) je normalizovaný, pokud ord má tvar { [Rozhodl,Pred], [se,AuxT], ord = ([1, a1 ], [2, a2 ], · · · , [n, an ]). Normalizace A-stromu [dnes,Adv], [odstoupit,Sb], [.,AuxK]} ⊂ ΓPDT . s = (V, E, ord) je takový normalizovaný A-strom s1 = (V1 , E1 , ord1 ), pro který (V, E) a (V1 , E1 ) jsou izomorfní a Jednotlivým položkám hlavního slovníku z tohoto příkladu Str(s) = Str(s1 ). Všimněme si, že normalizace A-stromu přiřazujeme jména (b1 atd.), která budeme v dalších pří- je jednoznačně daná. kladech užívat jako zkratky. b1 = [Rozhodl,Pred], b2 =[se,AuxT], b3 = [dnes,Adv], Ekvivalence. Dva A-stromy (R-seznamy) jsou ekviva- b4 =[odstoupit,Sb], b5 =[.,AuxK]. lentní, pokud mají stejnou normalizaci. Ekvivalentní A- stromy často nebudeme rozlišovat. V abecedě kategorií v tomto příkladě jsou využity jen Operace shift a delete zavedeme tak, že převedou A-strom jednoduché závislostní kategorie (ne všechny). Kategorie na A-strom. mohou být složené z více značek. Kategorie pro koordi- Delete. Operace dl(i) vyřadí z množiny V a z R-seznamu nace budou obsahovat značky ’Cr’, nebo ’Co’. ord uzel tvaru [i, ai ] a získá tím množinu V1 a R-seznam Věty v našich příkladech končí sentinelem (ukončením ord1 . Z A-stromu s = (V, E, ord) operace dl(i) udělá A- věty), který se během redukční analýzy ani nevypouští, ani strom s1 = (V1 , E1 , ord1 ) tím, že vyřadí uzel tvaru [i, ai ] nepřesunuje. Je to [.,AuxK]. jak z množiny V , tak z R-seznamu ord. Dále vyřadí z E všechny dvojice hran tvaru ([ j, a j ], [i, ai ]) a ([i, ai ], [k, ak ]) 2.2 R-seznamy a A-stromy. (pokud existují). Každou takovou dvojici hran nahradí v E1 jedinou hranou tvaru ([ j, a j ], [k, ak ]). Viz příklad 3. V následující části budeme reprezentovat věty pomocí Shift. Operace sh(i, j) přesune v R-seznamu ord uzel s tzv. R-seznamů a jejich syntaktické struktury pomocí A- indexem i před uzel s indexem j. Vytvoří tak nový R- stromů. R-seznamy a A-stromy jsou datové typy, vhodné seznam ord2 . Provedeme-li operaci sh(i, j) na A-strom pro používání operací delete a shift. Na R-seznamech a s = (V, E, ord), získáme tím A-strom s2 = (V, E, ord2 ). A-stromech zavádíme uniformním způsobem redukce, za- Operace shift mění v A-stromě pouze R-seznam, tedy slo- ložené právě na operacích delete a shift. Redukční se- vosled. Viz příklad 4. znamy (R-seznamy) zjemňují pojem řetězu a A-stromy ne- Poznámka. Připomeňme si, že operace mají být voleny sou více informace než R-seznamy. A-strom a R-seznam tak, že posledním uzlem trvale zůstává sentinel. se skládají z uzlů, které v PDT reprezenují výskyty lexi- kálních jednotek (slov, interpunkčních znamének a jejich značek) v príslušné větě. 2.3 URAS (Úplná redukční analýza A-stromu). V A-stromu jsou pomocí stromové struktury reprezen- továny syntaktické vztahy, pomocí R-seznamu, jež je sou- Zavádíme URAS s možností regulace pomocí množiny částí každého A-stromu, je reprezentováno pořadí slov. (významově) zakázaných redukcí. Příkladem zakázané re- dukce A-stromů z PDT, je vynechání předložky z předlož- R-seznam. Necht’ I je konečná množina přirozených čí- kové vazby, či vynechání samotné zvratné částice. sel, Γ konečná abeceda a V ⊆ (I × Γ), kde V reprezen- tuje totální zobrazení množiny I do Γ. Necht’ ord je úplné Značení. Necht’ Γ je konečná abeceda. T (Γ) značí mno- uspořádání množiny V . Říkáme, že ord je redukčním se- žinu všech A-stromů na Γ. Necht’ T ⊆ T (Γ). Říkáme, že T znamem (R-seznamem) na Γ. Zapisujeme ho jako seznam tvoří T-jazyk na Γ. Množinu R-seznamů R(T) = {R(t) | t ∈ prvků z V . Prvky R-seznamu označujeme jako uzly. Mno- T} nazýváme R-jazykem T-jazyka T. Analogicky, jazyk žinu R-seznamů, která vznikla všemi možnými uspořádá- Str(T) = {Str(t) | t ∈ T} nazýváme Str-jazykem T. Necht’ ními množiny V , označujeme jako ord(V ). Z ⊂ {(s,t)|s,t ∈ T} je daná množina zakázaných redukcí Necht’ u ∈ V , pak u = [i, a], kde i ∈ I, a ∈ Γ. Říkáme, že i na T. Označíme Str(Z) = {(Str(s), Str(t))|(s,t) ∈ Z} a je indexem uzlu u. Slouží k jednoznačné identifikaci uzlu. R(Z) = {(R(s), R(t))|(s,t) ∈ Z}. Říkáme, že a je symbolem uzlu u. Redukce. Nyní zavedeme k T-jazyku T a dané množině A-strom. A-strom nad Γ je trojice s = (V, E, ord), kde zakázaných redukcí Z redukce typu ⊢ZT . Necht’ s,t jsou A- (V, E) je orientovaný strom, jehož (maximální) cesty za- stromy. Říkáme, že s je přímo redukovatelné na t podle T čínají v listech a končí v kořeni, V je konečná množina a Z a píšeme s ⊢ZT t pokud: jeho uzlů, E ⊂ V ×V konečná množina jeho hran a ord ∈ • s,t ∈ T a |Str(s)| > |Str(t)| a (s,t) není ze Z; ord(V ). Říkáme, že ord je R-seznamem A-stromu s. Pí- • t je získáno z s provedením množiny operací vypuš- šeme R(s) = ord. tění (deletů) Dl a následně postupným provedením Projekce. Je-li ord = ([i1 , a1 ], · · · , [in , an ]), tak w = shiftů z uspořádané množiny Sh. Dl je povinně ne- a1 · · · an je řetěz (resp. věta), který označujeme Str(s) = w prázdná, Sh může být prázdná. Redukční analýza A-stromů s minimalistickými omezeními 29 • Libovolný uzel je přesouván pomocí Sh maximálně TP v následujícím textu označuje množinu korektních jednou. A-stromů s koordinacemi a závislostmi, zpracovaných me- • Operační nezmenšitelnost redukce. Pokud bychom todikou analytické roviny PDT. Rozhodnout o tom, zda vynechali při aplikaci na s jednu nebo více operací z daný A-strom patří do TP , by měli umět lidé (lingvisté, Dl nebo z Sh, získali bychom A-strom z takový, že anotátoři), ovládající češtinu a metodiku PDT. z∈/ T, nebo (s, z) ∈ Z. ZP označuje množinu zakázaných redukcí pro analytic- • Jako DL(s,t) označujeme množinu uzlů A-stromu s, kou rovinu PDT. vypuštěnou během redukce s ⊢ZT t a říkáme, že je DL- Příklad 3. Tento příklad navazuje na příklady 1 a 2. množinou redukce s ⊢ZT t. O Sh říkáme, že je SH- Obsahuje formalizaci A-stromů T12 a T13 a tím i popis sekvencí redukce s ⊢ZT t. redukce T12 ⊢ZP TP T13 : T12 = (V2 , E2 , ord2 ), pričemž Doplňující pojmy. Reflexívní a tranzitívní uzávěr relace V2 = {[1, b1 ], [2, b2 ], [3, b3 ], [4, b4 ], [5, b5 ]} ⊢ZT označujeme ⊢ZT ∗ . Částečné uspořádání ⊢ZT přirozeně E2 = {([2, b2 ], [1, b1 ]), ([3, b3 ], [4, b4 ]), ([4, b4 ], [1, b1 ]), definuje ([5, b5 ], [1, b1 ])}, ord2 = ([1, b1 ], [2, b2 ], [3, b3 ], [4, b4 ], [5, b5 ]) • T⊢0Z = {v ∈ T | ¬∃u ∈ T : v ⊢ZT u} - množina neredu- T13 = (V3 , E3 , ord3 ), pričemž T kovatelných A-stromů T-jazyka T. V3 = {[1, b1 ], [2, b2 ], [3, b3 ], [5, b5 ]} • T⊢n+1 Z = {v ∈ T | ∃u ∈ T⊢nZ : u ⊢ZT v} ∪ T⊢nZ , n ∈ N - E3 = {([2, b2 ], [1, b1 ]), ([3, b3 ], [1, b1 ]), ([5, b5 ], [1, b1 ])} T T T množina A-stromů z T, které je možné zredukovat ord3 = ([1, b1 ], [2, b2 ], [3, b3 ], [5, b5 ]) na neredukovatelný A-strom z Tposloupností URAS- Vidíme, že T12 je normalizovaný a že T13 normalizo- redukcí délky nanejvýš n + 1. vaný není, protože vznikl z T12 vypuštěním uzlu [4, b4 ]. Následují strukturální pozorování A-stromů z TP . Pozo- URAS. Pro A-strom s ∈ T a zakázanou množinu Z na- rování odrážejí syntaktické vlastnosti českých vět a anotá- zveme URAS(s, T, Z) ={u ⊢ZT v |s ⊢ZT ∗ u} (úplnou) re- torskou metodiku pro analytickou rovinu PDT. Naše pří- dukční analýzou s podle T a Z. klady tato pozorování ilustrují. Větev. Necht’ B = (s1 , s2 , · · · , sn ) je posloupnost A-stromů Pozorování 1. Necht’ s je A-strom z TP . Všechny větve taková, že s1 ⊢ZT s2 , s2 ⊢ZT s3 , · · ·, sn−1 ⊢ZT sn a sn ∈ T⊢0Z . T URAS(s, TP , ZP) mají stejnou délku. Říkáme, že B je větví URAS(s, T, Z) a n je její délka. Pozorování 2. Necht’ s je A-strom z TP , který neobsa- DL-sekvence a DL-charakteristika. Necht’ Dli je Dl- huje koordinace (tj. značky ´Cr´ a ´Co´). Všechny větve množinou redukce si ⊢T si+1 pro 1 ≤ i < n a Dln je mno- URAS(s, TP , ZP) mají nejen stejnou délku, ale i stejnou žinou uzlů A-stromu sn . DL-charakteristiku. Navíc URAS(s, TP , ZP) obsahuje je- Píšeme Dl(B) = (Dl1 , DL2 , · · · , Dln−1 ) a říkáme, že Dl(B) diný neredukovatelný A-strom. Tedy URAS(s, TP , ZP) lze je DL-sekvencí větve B. považovat za (algebraickou strukturu zvanou) svaz. Množina Ch(B) = ({Dl1 , DL2 , · · · , Dln−1 }) je DL- charakteristikou větve B. Pozorování 3. Necht’ s je A-strom z TP , který neob- DL-charakteristika a DL-sekvence se liší tím, že u DL- sahuje koordinace a r1 , r2 jsou dvě různé redukce z charakteristiky nezáleží na pořadí redukčních množin, ale URAS(s, TP , ZP). Platí, že r1 a r2 mají disjunktní DL- u DL-sekvence ano. množiny. Vidíme, že pro 1 ≤ i < j < n jsou Dli a Dl j disjunktní. Pozorování 4. Necht’ s je A-strom z TP , který obsa- huje koordinaci alespoň tří členů. Existují dvě větve 2.4 Algebraické vlastnosti závislostí a koordinací u URAS(s, TP , ZP) s různou DL-charakteristikou. analytických stromů PDT. Pozorování 5. Necht’ s je A-strom z TP , který obsa- Touto podsekcí začíná výsledková část příspěvku. Před- huje koordinaci alespoň tří členů. Existují dvě redukce kládáme výsledky dvou typů. Nejčastěji prezentujeme lin- z URAS(s, TP , ZP), které nemají disjunktní DL-množiny. gvistická pozorování, formulovaná pomocí zavedeného Průnik těchto DL-množin obsahuje uzel se spojkou nebo aparátu. Získali jsme je (neúplným) procházením materi- čárkou se značkou ¨AuxX¨. álu z PDT. K pozorováním jsme nenašli žádné výjimky a nevěříme, že se nějaké najdou. Pozorování by měla být Předchozí dvě pozorování jsou ilustrovány příkladem 4. podnětem ke (korpusově lingvistické) diskusi. Tvrzení 1. Existuje t ∈ TP , jehož URAS obsahuje více než Druhým typem výsledků jsou tvrzení a důsledky ma- jeden neredukovalelný A-strom. tematického charakteru. Vycházejí z rozboru prezentova- ných (lingvistických) příkladů a z vlastností zavedeného Předchozí tvrzení lze dokázat pomocí A-stromu k větě aparátu. ’Přišel, viděl, zvítězil.’. 30 M. Plátek, K. Oliva 2.5 UPRA (úplná větná redukční analýza.) URAS s omezeným počtem komponent. Necht’ i je při- rozené číslo. Označíme jako URAS(s, T, Z; pk ≤ i) pod- Abychom mohli dát do souvislosti URAS se starším po- množinu URAS(s, T, Z), která obsahuje všechny redukce jmem, větnou redukční analýzou, zavádíme úplnou vět- z URAS(s, T, Z), které nemají více komponent než i. nou redukční analýzu (UPRA), viz [3]. Do UPRA vstupuje Vidíme, že neredukovatelné stromy v URAS(s, T, Z; pk ≤ věta ve formě R-seznamu. UPRA zavádíme zcela analo- i) mohou být pro některá i jiné (větší), než ty z gicky jako URAS. URAS(s, T, Z). Redukce. Mějme jazyk L a R-seznam u takový, že Str(u) ∈ L. Říkáme, že u je R-seznamem k jazyku L a pí- Říkáme, že URAS(s, T, Z; pk ≤ i) je pro dané i T-stabilní, šeme u ∈ R(L). Necht’ U ⊂ {(u, v)|u, v ∈ R(L)} je daná pokud URAS(s, T, Z; pk ≤ i) = URAS(s, T, Z). množina zakázaných redukcí. Říkáme, že URAS(s, T, Z; pk ≤ i) je pro dané i CH- Zavedeme k R(L) a dané U redukce ≻UL . Necht’ u, v ∈ stabilní, pokud množina charakteristik URAS(s, T, Z; pk ≤ R(L). Říkáme, že u je redukovatelné na v podle L a U a i) a URAS(s, T, Z) je stejná. označujeme u ≻UL v, pokud: URAS(s, T, Z; pk ≤ i) je pro dané i Mn-stabilní, pokud každý neredukovatelný strom z URAS(s, T, Z, pk ≤ i) je • |Str(u)| > |Str(v)| a (u,v) není z U; i neredukovatelným stromem URAS(s, T, Z). • R-seznam v je získán z u provedením množiny ope- Požadavky na stabilitu jsou seřazeny od nejsilnější k nej- rací vypuštění (deletů) Dl a následně postupným pro- slabší. Nahlédneme, že stejně můžeme užívat zavedené vedením shiftů z uspořádané množiny Sh. Dl je po- typy stability pro další typy redukčních omezení. vinně neprázdná, Sh může být prázdná. • Libovolný uzel je přesouván pomocí Sh maximálně Počet komponent je jednou přirozenou mírou nesouvis- jednou. losti redukce A-stromu. Budeme používat ještě jednu míru nesouvislosti redukce, která měří velikost mezer mezi • Operační nezmenšitelnost redukce. Pokud bychom komponentami. Následují další formální definice. vynechali při aplikaci na u jednu nebo více operací z Dl nebo z Sh, získali bychom R-seznam z takový, že Velikost mezer v redukci. Jako Sv(s,t) budeme označo- Str(z) ∈/ L, nebo (u, z) ∈ U. vat nejmenší souvislý (bez ohledu na orientaci) podgraf A- • Jako Dl(u, v) označujeme množinu uzlů R-seznamu stromu s, který obsahuje DL-graf G(s,t). Necht’ j je počet u, vypuštěnou provedením množiny deletů Dl a ří- uzlů, které obsahuje Sv(s,t) navíc oproti G(s,t). Píšeme káme, že Dl(u, v) je DL-množinou redukce u ≻UL v. ns(s,t) = j a říkáme, že redukce s ⊢ZT t má velikost mezer O Sh říkáme, že je SH-sekvencí redukce u ≻UL v. j. URAS s omezením na velikost mezer. Necht’ i je při- rozené číslo. Označíme jako URAS(s, T, Z : ns ≤ i) pod- UPRA. Necht’ w ∈ R(L) a U ⊂ {(u, v)|u, v ∈ R(L)} je daná množinu URAS(s, T, Z), která obsahuje všechny redukce množina zakázaných redukcí. UPRA(w, L,U) ={u ≻UL z URAS(s, T, Z), které nemají velikost mezer větší než i. v |w ≻UL ∗ u} nazveme úplnou redukční analýzou w k ja- zyku L a množině nekorektních redukcí U. Omezení můžeme i skládat. Např. URAS(s, T, Z; pk ≤ Zbývající potřebné pojmy pro UPRA lze zavést zcela i, ns ≤ j) = URAS(s, T, Z; pk ≤ i) ∩ URAS(s, T, Z; ns ≤ j). analogicky jako pro URAS. Množiny stromů stabililní s ohledem na omezení. Bu- deme používat následující typy značení pro množiny A- stromů splňující daná omezení. 2.6 Nesouvislosti a stabilita redukcí. Např. TRAS(T, Z; pk ≤ 1, ns ≤ 0; T-st ) = {t ∈ T | Zavádíme dvě míry nesouvislosti redukcí, které se vzá- URAS(t, T, Z; pk ≤ 1, ns ≤ 0) je T-stabilní }. jemně doplňují. S ohledem na tyto a další míry zavádíme Analogicky TRAS(T, Z; pk ≤ 1; CH-st ) = {t ∈ T | několik typů stability pro URAS, které nám dovolí klasifi- URAS(t, T, Z; pk ≤ 1) je CH-stabilní }. Podobně budeme kovat omezená URAS jako stabilní, nebo nestabilní. Stabi- popisovat množiny A-stromů z T parametrizované dalšími lita URAS pro jednotlivé A-stromy je formálním kriteriem omezeními a různými typy stability ze škály T-stabilní, pro lingvistickou adekvátnost redukční analýzy, s ohledem CH-stabilní, Mn-stabilní. na daná omezení. Budeme hledat maximální omezení ta- ková, která zachovávají alespoň nejslabší typ stability. Ná- 2.7 Rozlišení závislostí a koordinací pomocí sleduje několik formálních definic. (ne)souvislosti. Graf redukce. Mějme redukci s ⊢ZT t, kde s = (V, E, or), a její DL-množinu DL(s,t). Píšeme G(s,t) = Předchozí pojmy a následující příklady využijeme k for- (DL(s,t), {(a, b) ∈ E|a, b ∈ DL(s,t)}) a říkáme, že G(s,t) mulaci nových pozorování o PDT. je DL-grafem redukce s ⊢ZT t. Počet komponent redukce. Necht’ i je počet komponent Příklad 4. Tento příklad ilustruje redukce vícenásob- DL-grafu G(s,t). Budeme psát, že pk(s,t) = i a říkat, že i ných koordinací a použití grafově nesouvislé redukce v je počet komponent redukce s ⊢ZT t. URAS. Redukční analýza A-stromů s minimalistickými omezeními 31 (3) Je.Pred dědou.Obj.Co ,.AuxX otcem.Obj.Co a..Cr strýcem.Obj.Co..AuxK Je.Pred Je.Pred a.Cr ..AuxK Na obrázku 5 vidíme schema UPRA věty (3) podle otcem.Obj.Co ..AuxK stromu T31 , jazyka Tp a prázdné zakázané množiny. dědou.Obj.Co Schema stejného tvaru má i schema URAS A-stromu T31 . Věta (3) obsahuje trojnásobnou koordinaci předmětů. Po- Obrázek 8: Vlevo T34 , vzniklý redukcí z T31 a vpravo T35 všimněme si, že dalšímu zjemnění schematu zabraňují ka- vzniklý redukcemi z T32 , T33 a T34 . tegorie (značky), použité podle vzoru PDT. Značka ’Cr’ znamená koordinující symbol (slovo), ’Co’ značí koordi- Z předchozích tvrzení vyplývá následující důsledek. nované slovo, či symbol. Schematu na obrázku odpovídají redukce A-stromů, které jsou reprezentovány obrázky 4 až Důsledek 1. Vidíme, že 8. Všechny tři redukce A-stromu T31 vypouštějí (při zjed- TRAS(TP , ZP, pk ≤ 1; T-st ) ⊂ TRAS(TP , ZP; pk ≤ 2; T-st ) nodušování trojnásobné koordinace na dvojnásobnou) dva nesouvisející listy (podstromy). Třetí redukce navíc pou- Následují výsledky našeho pozorování TP , které se tý- žívá shift. Zbývající redukce dvojnásobných koordinací se kají nesouvislostí. realizují postupným vypouštěním listů, které tvoří souvislý úplný podstrom. Pozorování 6. Necht’ s ∈ TP . URAS(s, TP , ZP; pk ≤ 2) je T-stabilní. Je.Pred dědou.Obj.Co ,.AuxX otcem.Obj.Co a. Cr strýcem.Obj.Co ..AuxK Pozorování 7. Necht’ s ∈ TP je A-strom bez koordinací. URAS(s, TP , ZP; pk ≤ 1) je T-stabilní. Je.Pred otcem.Obj.Co a.Cr strýcem.Obj.Co ..AuxK Pozorování 8. Necht’ s ∈ TP je A-strom s alespoň troj- Je.Pred dědou.Obj.Co a.Cr strýcem.Obj.Co ..AuxK shift násbnou koordinací. URAS(s, TP , ZP; pk ≤ 1) není Mn- stabilní. Je.Pred dědou.Obj.Co a.Cr otcem.Obj.Co ..AuxK Je.Pred ..AuxK Poznámky k předchozímu pozorování. Podobně jako u T31 , každá alespoň trojnásobná koordinace z PDT Obrázek 5: UPRA věty (3) podle T31 . vyžaduje alespoň jednu redukci se dvěma komponen- tami. Pokud povolíme redukce s maximálně jednou Je.Pred komponentou, bude každý neredukovatelný strom z URAS(s, TP , ZP; pk ≤ 1) minimálně o jednu nevykona- nou redukci větší, než příslušný neredukovatelný strom z a.Cr ..AuxK dědou.Obj.Co URAS(s, TP , ZP). strýcem.Obj.Co Pozorování o velikosti mezer jsou analogická pozorová- ,.AuxX otcem.Obj.Co ním o počtu komponent. Důležité pozorování je, že koor- dinace dovolují redukcím jen velikost mezer rovnou jedné Obrázek 6: A-strom T31 . a stromy bez koordinací dovolují redukcím jen jedinou komponentu. Je.Pred a.Cr Je.Pred Pozorování 9. Vypozorovali jsme, že ..AuxK a.Cr ..AuxK TRAS(TP , ZP, ns ≤ 0; T-st ) = TRAS(TP , ZP; pk ≤ 1; T-st), strýcem.Obj.Co otcem.Obj.Co strýcem.Obj.Co TRAS(TP , ZP; ns ≤ 1; T-st ) = TRAS(TP , ZP, pk ≤ 2; T-st) dědou.Obj.Co = TP . Obrázek 7: T32 a T33 vzniklé redukcemi z T31 . Pozorování 10. Necht’ s ∈ TP je A-strom bez koordi- nací. URAS(s, TP , ZP; ns ≤ 0) je T-stabilní. Vidíme, že i URAS(s, TP , ZP; pk ≤ 1, ns ≤ 0) je T-stabilní. Pozorování 11. Necht’ s ∈ TP je A-strom s alespoň trojná- sobnou koordinací. Platí, že URAS(s, TP , ZP; ns ≤ 0) není Mn-stabilní. Snadno ověříme z definic následující tvrzení. Tvrzení 2. Vidíme, že 2.8 URAS s omezeními míry (ne)listovosti. URAS(T11 , TP , ZP; pk ≤ 1) je T-stabilní, URAS(T31 , TP , ZP; pk ≤ 2) je T-stabilní a Snažíme se minimalizovat při redukcích změny hran URAS(T31 , TP , ZP; pk ≤ 1) není Mn-stabilní. (změny významu), takže se snažíme redukovat stromy bez 32 M. Plátek, K. Oliva koordinací tak, že vypouštíme v jistém pořadí jen listy. Po- Pracujeme. Pred.Co a.Cr.Co myslíme. Pred.Co i .Cr jednáme. Pred.Co ..AuxK jmy zaváděné v tomto odstavci zavádíme za dvojím úče- lem. Prvním účelem je dát prostředky pro formální apro- Pracujeme. Pred.Co i. Cr jednáme. Pred.Co ..AuxK ximaci intuitivní redukční analýzy stromů bez koordinací. Druhým účelem je exaktně zachytit fakt, že redukce vlože- myslíme. Pred.Co i .Cr jednáme. Pred.Co ..AuxK ných koordinací nutně používají vypuštění vnitřního uzlu a charakterizovat složitost tohoto faktu. Při redukci vlo- Obrázek 9: UPRA věty s vloženou koordinací. žených koordinací se význam redukovaného stromu nijak nemění. i.Cr Necht’ o je nějaké uspořádání množiny Dl, kde Dl je a.Cr.Co ..AuxK DL-množinou nějaké redukce A-stromu s. Pak říkáme, že jednáme.Pred.Co o realizuje Dl na s. Píšeme o ∈ ord(Dl, s). IN-stupněm operace dl(i) na A-stromě s nazveme počet pracujeme.Pred.Co myslíme.Pred.Co hran z E vcházejících do uzlu [i, ai ]. Všimněme si, že de- lete uzlu [i, ai ] má IN-stupeň 0 právě tehdy, pokud [i, ai ] je Obrázek 10: T51 listem A-stromu s. Uvažujme různé realizace množiny Dl, kde Dl je DL- Tvrzení 3. Pro pro čistě závislostní strom T11 z příkladu množina na s. V různých realizacích Dl na s může mít 1 platí, že URAS(T 11 , TP , ZP; MaxIN ≤ 0) je T-stabilní. dl(i) ∈ Dl různou hodnotu svého IN-stupně, nebot’ dl(i) může být prováděna na různých A-stromech. Tvrzení 4. Pro čistě závislostní strom T12 z příkladu 1 Omezíme se jen na neklesající realizace DL-množin v re- platí, že URAS(T12 , TP , MaxIN ≤ 0) není T-stabilní, ale je dukcích, nebot’ realizace vypouštějící jen listy musí být Mn-stabilní. Navíc URAS(T12 , TP , MinIn ≤ 1, MaxIN ≤ 1) neklesající. Budeme využívat faktu, že ke každé redukci je T-stabilní. existuje neklesající realizace. Důsledek 2. Vidíme, že Značení. Říkáme, že o ∈ ord(Dl, s) je neklesající a píšeme o ∈ Nord(Dl, s), pokud o = (dl(i1 ), dl(i2 ), · · · , dl(in )) a • TRAS(TP , ZP; MaxIN ≤ 0; T-st ) IN(dl(i1 )) ≤ IN(dl(i2 )), · · · , IN(dl(in−1 )) ≤ IN(dl(in )). ⊂ TRAS(TP , ZP; MaxIN ≤ 1; T-st). Píšeme IN(o) = (IN(dl(i1 )), IN(dl(i2 )), · · · , IN(dl(in ))). Necht’ o ∈ Nord(Dl, s), první prvek z o je dl(i), poslední • TRAS(TP , ZP; MinIN ≤ 0; T-st ) prvek z o je dl( j). Budeme psát MinIN(o) = IN(dl(i)) a ⊂ TRAS(TP , ZP; MinIN ≤ 1; T-st). MaxIN(o) = IN(dl( j)). Pozorování 12. TRAS(TP , ZP; MinIN ≤ 1; T-st ) ⊂ TP . URAS se spodní mírou (ne)listovosti. Označíme jako URAS(s, T, Z; MinIn ≤ i) podmnožinu URAS(s, T, Z), Tvrzení 5. Pro T51 z příkladu 5 platí, že která obsahuje všechny redukce z URAS(s, T, Z), které URAS(T51 , TP , ZP; MinIN ≤ 0) je T-stabilní, mají neklesající realizaci o s MinIN(o) ≤ i. URAS(T51 , TP , ZP; MaxIN ≤ 0) není Mn-stabilní a URAS s horní mírou (ne)listovosti. Označíme jako URAS(T51 , TP , ZP; MinIN ≤ 0, MaxIN ≤ 1) URAS(s, T, Z; MaxIN ≤ i) podmnožinu URAS(s, T, Z), je T-stabilní. která obsahuje všechny redukce z URAS(s, T, Z), které T51 nese koordinaci vloženou do koordinace. Vidíme, že mají neklesající realizaci o s MaxIN(o) ≤ i. platí T51 ∈TRAS(TP , ZP; MinIN ≤ 0, MaxIn ≤ 1; T-st ) Pozorování 13. Necht’ t ∈ TP nese koordinaci vloženou 2.9 Závislosti, vložená koordinace a (ne)listovost. do koordinace. Platí, že URAS(t, TP , ZP; MaxIN ≤ 0) není Mn-stabilní. Příklad 5. Tento příklad ilustruje redukce vložených koordinací. Důsledek 3. Vidíme, že (5) Pracujeme.Pred.Co a.Cr.Co myslíme.Pred.Co i..Cr jednáme.Pred.Co..AuxK • TRAS(TP , ZP; MaxIN ≤ 0; T-st ) ⊂ TRAS(TP , ZP; MinIN ≤ 0; MaxIn ≤ 1; Mn-st) Na obrázku 9 vidíme schema UPRA věty (5) podle T51 , • TRAS(TP , ZP; MinIN ≤ 0; MaxIn ≤ 1; Mn-st) TP a ZP. Věta (5) je věta s vloženou koordinací. A-stromy ⊂ TRAS(TP , ZP; MinIN ≤ 1; MaxIn ≤ 1; Mn-st ) odpovídající redukcím jsou na obrázcích 10 až 12. Vlo- žená koordinace se v A-stromě T51 zjednodušuje tak, že se i.Cr vyjme jedna hrana s řídícím uzlem se značkou ’Cr.Co’. To ..AuxK odpovídá dvěma redukcím v UPRA z obrázku . Vidíme, že jednáme.Pred.Co tyto redukce vypouštějí jeden list a jeden vnitřní uzel do pracujeme.Pred.Co kterého vchází jediná hrana. Obrázek 11: T 52 , vzniklé redukcí z T51 . Redukční analýza A-stromů s minimalistickými omezeními 33 i.Cr a) kořenem tn bude nejlevější a, b) z každého a, které není kořenem vede hrana do jeho jednáme.Pred.Co ..AuxK levého souseda, myslíme.Pred.Co c) z i-tého b vede hrana do i-tého a. Jiné hrany tn neob- Obrázek 12: T 53 , vzniklé redukcí z T51 . sahuje. Budiž T1 = {tn |n > 0}. Vidíme, že TRAS(T1 , 0; / dl ≤ 2, ds ≤ 2, pk ≤ 1, MaxIn ≤ 0; T-st) = T1 . • TRAS(TP , ZP; MinIN ≤ 1, MaxIn ≤ 1; Mn-st ) ⊆ TP . Předchozí rovnost dává strukturálně-složitostní charak- teristiku T-jazyka T1 . Zmenšením kteréhokoliv parametru Poznámka. Pro každé t ∈ TP , které jsme pozoro- bud’ rovnost ztrácíme, nebo zmenšení parametru nemá vali, bylo URAS(t, TP , ZP; MinIN ≤ 1) Mn-stabilní. Neu- smysl. míme odhadnout, zda existuje A-strom t ∈ TP takový, že URAS(t, TP , ZP; MinIN ≤ 1) není Mn-stabilní, tedy zda Následující tvrzení není těžké nahlédnout. TRAS(TP , ZP, MinIN ≤ 1, MaxInPc ≤ 1; Mn-st ) = TP . Tvrzení 6. Ke každému k ∈ N existuje regulární jazyk L, takový, že pro libovolný T-jazyk T takový, že Str(T ) = L 2.10 Konzistence URAS a UPRA nad PDT platí, že TRAS(T, 0; / ds ≤ k, Mn-st )6= T . LP značí množinu korektních českých vět (jen) s koordi- Podobné tvrzení platí pro bezkontextové jazyky, které nacemi a závislostmi, která je korektně značkovaná me- nejsou regulární. todikou analytické roviny PDT. Připomeňme, že TP ozna- Poznamenejme, že v následujícím zřejmém tvrzení mají čuje množinu všech korektních A-stromů s koordinacemi označení UPRA(u, L, 0; / ds ≤ k) a Mn-stabilita analogický a závislostmi, zpracovaných metodikou analytické roviny význam jako pro URAS. PDT. ZP označuje množinu zakázaných redukcí na TP . Tvrzení 7. Ke každému bezkontextovému jazyku L exis- Následuje pozorování o konzistenci mezi URAS na TP tuje k ∈ N takové, že pro libovolné u ∈ R(L) platí, že a UPRA na LP . UPRA(u, L, 0; / ds ≤ k) je Mn-stabilní. Podle našich pozorování a naší notace platí, že LP = Str(TP ), R(LP ) = R(TP ) a UP = R(ZP). Předchozí příklad a tvrzení uvádíme, abychom pouká- zali na souvislosti našich lingvistických pozorování TP a Pozorování 14. Necht’ s ⊢ZP UP TP t, pak R(s) ≻LP R(t). Necht’ formální teorií (nekonečných) jazyků. Vidíme, že z po- s,t ∈ TP a R(s) ≻UP ZP LP R(t), pak s ⊢TP t. hledu formální redukční analýzy, nejsou A-stromy z TP Předchozí pozorování formuluje vlastnost konzistence příliš složité. Přesto jsme (na základě lingvistického folk- mezi UPRA a PRAS. Říká, že A-stromy z PDT jsou kon- lóru) očekávali jednodušší a uniformější výsledky. struovány v souladu s větnou redukční analýzou. Toto po- V budoucnu plánujeme zavést míry neprojektivity a ře- zorování je naším základním pozorováním analytické ro- tězové nesouvislosti založené na redukční analýze a kon- viny PDT. Přirozeně všechny zde prezentované příklady frontovat tyto míry s PDT. Očekáváme, že se ukáže sou- na URAS a UPRA splňují podmínky konzistence mezi vislost těchto měr s časovou složitostí redukční analýzy. URAS a UPRA. Reference 2.11 Další omezení a výhledy do budoucna. [1] Markéta Lopatková, Jirí Mírovský, and Vladislav Kubon. Následující omezení mají, na rozdíl od předchozích po- Gramatické závislosti vs. koordinace z pohledu redukční dobnou platnost pro URAS i pro UPRA. analýzy. In Proceedings of the main track of the 14th Confe- rence on Information Technologies - Applications and The- URAS s omezením na počet deletů. Necht’ i je přiro- ory (ITAT 2014), with selected papers from Znalosti 2014 zené číslo. Označíme jako URAS(s, T, Z : dl ≤ i) pod- collocated with Znalosti 2014, Demanovska Dolina - Jasna, množinu URAS(s, T, Z), která obsahuje všechny redukce Slovakia, September 25 - 29, 2014., pages 61–67, 2014. z URAS(s, T, Z), které nemají počet deletů větší než i. [2] Martin Plátek, Dana Pardubská, and Markéta Lopatková. URAS s omezením na vzdálenost vypouštěných uzlů. On minimalism of analysis by reduction by restarting auto- Necht’ k je přirozené číslo. Označíme jako URAS(s, T, Z : mata. In Formal Grammar - 19th International Conference, ds ≤ k) podmnožinu URAS(s, T, Z), která obsahuje FG 2014, Tübingen, Germany, August 16-17, 2014. Procee- všechny redukce z URAS(s, T, Z), které nemají vzdálenost dings, pages 155–170, 2014. mezi vypouštěnými uzly (podle uspořádání v R-seznamu) [3] Martin Plátek, Dana Pardubská, and Karel Oliva. Redukční větší než k. analýza a pražský závislostní korpus. In Proceedings ITAT 2015: Information Technologies - Applications and Theory, Příklad 6. Uvažujme formální jazyk L1 = {an bn |n > 0}. Slovensky Raj, Slovakia, September 17-21, 2015., pages 43– Každému slovu (větě) tohoto jazyka přiřadíme A-strom tn 50, 2015. následujícím způsobem: