=Paper=
{{Paper
|id=Vol-1649/26
|storemode=property
|title=Redukční analýza A-stromů s minimalistickými omezeními
|pdfUrl=https://ceur-ws.org/Vol-1649/26.pdf
|volume=Vol-1649
|authors=Martin Plátek, Karel Oliva
|dblpUrl=https://dblp.org/rec/conf/itat/PlatekO16
}}
==Redukční analýza A-stromů s minimalistickými omezeními==
https://ceur-ws.org/Vol-1649/26.pdf
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: