Abstrakt: Tento prˇíspeˇvek navazuje na náš lonˇský prˇíspeˇvek na ITATu. Zpracovává novým zpu˚sobem redukcˇní analýzu na A-stromech, které jsou formalizací stromu˚, zpracovaných metodikou pro analytickou rovinu Pražského závislostního korpusu (PDT). Redukcˇní analýza Astromu˚ sestává z minimálních korektních redukcí, které používají pouze elementární operace delete a shift. Hlavním cílem je vyvinout formální prostrˇedky, které by exaktneˇ zachycovaly lingvisticky pozorované minimalistické vlastnosti jednotlivých parametru˚ stromové redukcˇní analýzy stromu˚ ve formátu PDT a dovolily následneˇ realizovat podobná pozorování na ru˚zných prˇirozených, cˇi umeˇlých jazycích. Pomocí pozorování lingvistického typu uprˇesnˇujeme strukturálneˇ-složitostní vlastnosti A-stromu˚ se závislostmi a koordinacemi. Zvýraznˇujeme vlastnosti, kterými se závislosti a koordinace liší. V této práci zavádíme a studujeme exaktní pojem (úplné) redukcˇní analýzy A-stromu˚ (URAS). A-stromy modelují stromy analytické roviny Pražského závislostního korpusu (PDT). URAS obsahuje všechny korektní redukce, které lze zarˇadit do lingvisticky korektní (manuální) redukcˇní analýzy na A-stromech. URAS používá operace delete a shift a jeho redukce jsou minimalizovány s ohledem na pocˇet teˇchto operací. Postupneˇ zavádíme ru˚zné další omezující parametry, které je možno minimalizovat a užívat pro jemneˇjší aproximace lingvisticky intuitivní redukcˇní analýzy. Zavádíme trˇícˇlennou škálu stability pro omezené URAS. Za korektní omezené URAS považujeme ty, co jsou stabilní alesponˇ v tom nejslabším smyslu. Stabilita pomáhá hledat spodní odhady pro intuitivní redukcˇní analýzu. Typ stability urcˇuje veˇtší cˇi menší vzdálenost od neomezené URAS. Zavedené pojmy používáme pro klasifikaci pozorování lingvistického typu. Pozorujeme množiny A-stromu˚, které odpovídají cˇeským veˇtám a jsou zpracovány metodikou analytické roviny PDT. Odkrýváme tak rˇadu strukturálních vlastností takovýchto A-stromu˚. Povšimneˇme si, že prezentovaná pozorování jsou smysluplná a netriviální na konecˇných i nekonecˇných jazycích (množinách). To je ve spojitosti s lingvistikou velmi užitecˇné. Prezentujeme ∗Pˇríspeˇvek prezentuje výsledky dosažené v rámci projektu agentury GACˇ R cˇíslo GA15-04960S.
1.1
V této sekci neformálneˇ prˇedstavujeme redukcˇní analýzu A-stromu˚ se závislostmi a s koordinacemi. Redukcˇní analýzou cˇeských veˇt a jejímu modelování se zabýváme již delší dobu. Jako základní variantu redukcˇní analýzy prˇedkládáme úplnou redukcˇní analýzu A-stromu˚ (URAS). Navazujeme na cˇlánky z minulých let (viz [2, 1, 3]). Prˇi zavádeˇní variant redukcˇních analýz zvýraznˇujeme jejich minimalistický charakter.
URAS je založena na postupném zjednodušování Astromu po minimálních krocích. URAS definuje všechny možné posloupnosti veˇtných redukcí – každá redukce spocˇívá ve vypušteˇní neˇkolika uzlu˚, nejméneˇ však jednoho uzlu analyzovaného A-stromu. V A-stromeˇ vypouštíme tak, abychom z A-stromu získali opeˇt A-strom a každá cesta v novém A-stromeˇ byla podposloupností cesty v pu˚vodním A-stromeˇ. Viz naprˇ. obrázky z prˇíkladu 1. V neˇkterých redukcích mu˚že být kromeˇ vypoušteˇní použita operace shift, která prˇesune neˇjaký uzel na novou pozici v Astromeˇ.
V našich lingvistických pozorováních budeme rozlišovat vypoušteˇní listu˚ a vypoušteˇní vnitrˇních uzlu˚. Korˇeny se v URAS nevypouští. Intuitivneˇ i v URAS u veˇtšiny závislostních jevu˚ stacˇí používat vypoušteˇní listu˚. Ukážeme, že redukce koordinací v PDT s vypoušteˇním listu˚ nevystacˇí.
Metoda URAS je popsaná následujícími zásadami:
(i) URAS je složena z jednotlivých redukcí; redukce
používají operace dvou typu˚ : (
vynecháme-li z libovolné redukce jednu cˇi více Rozhodl.Pred se.AuxT operací, nastane porušení principu zachování gramatické správnosti (ii) nebo redukce se stane zakázanou a tím poruší princip (iii). (v) URAS obsahuje všechny možné redukce splnˇující zásady (i) až (iv).
URAS tvorˇí základ, z kterého budeme odvozovat další varianty redukcˇní analýzy, tak aby odpovídaly neˇkterým typu˚m lingvistické (minimalisticé) intuice. Tento zámeˇr budeme rozvíjet prˇedevším ve formální cˇásti.
V následujících odstavcích nejprve uvedeme jeden prˇíklad ilustrující URAS. Prˇíklad se týká jen redukcí, které zjednodušují závislosti. Pozdeˇji budou následovat prˇíklady, týkající se koordinací. Prˇíklady nejprve poslouží pro úvod do problematiky, pozdeˇji (ve výsledkové cˇásti) jako separacˇní prˇíklady pro taxonomii redukcˇních analýz. Astromy na obrázcích v našich prˇíkladech jsou oproti stromu˚m z PDT trochu zjednodušené. Za prvé: neobsahují identifikacˇní uzel, který nenese žádnou syntaktickou informaci a neodpovídá žádnému slovu veˇty. Za druhé: znacˇka ’Coord’ je nahrazena znacˇkou ’Cr’ a za trˇetí vynecháváme morfologické znacˇky.
Všimneˇme si, že korektní A-strom zcela urcˇuje jednu korektní cˇeskou veˇtu i s jejím korektním znacˇkováním.
tíme zvratnou cˇástici se, nebot’ vypušteˇní pouhé zvratné
cˇástice považujeme za zakázanou redukci. Zde vu˚bec
nepoužíváme shift.
(
lýzy (tzv. UPRA). Isomorfní (velmi podobné) schema mají
stupuje i tato schemata.
poušteˇjí jen listy, tedy redukcemi nevznikají nové hrany. U
uzel A-stromu, tedy vzniká nová hrana a to v tomto prˇípadeˇ signalizuje zmeˇnu významu. To není žádoucí.
patrˇí ješteˇ obrázek 4, zobrazující redukci T14 na T15.
Rozhodl.Pred se.AuxT dnes.Adv odstoupit.Sb ..AuxK Rozhodl.Pred se.AuxT odstoupit.Sb ..AuxK
Rozhodl.Pred se.AuxT dnes.Adv ..AuxK Rozhodl.Pred se.AuxT ..AuxK
Obrázek 1: UPRA veˇty (
Formalizace redukcˇní analýzy.
Zde zavedeme obecné formální pojmy, které mohou
sloužit k formulaci redukcˇních vlastností jak závislostních
Obrázek 2: A-stromy T11 a T12 nad veˇtou (
Obrázek 3: Redukce T12 na T13. stromu˚ prˇirozených jazyku˚, tak i podobných struktur u programovacích a dotazovacích jazyku˚. V podsekcích, prezentujících pozorování lingvistického typu, se budeme veˇnovat formulaci redukcˇních vlastností stromu˚ analytické roviny PDT. Znacˇka ⊂ znamená v celém prˇíspeˇvku vlastní podmnožinu.
Formalizace redukcˇní analýzy analytických stromu˚ se neobejde bez formalizace lexikální analýzy. 2.1
Prˇi formalizaci lexikální analýzy rozlišujeme trˇi konecˇné množiny slov a znacˇek. Σp oznacˇuje tzv. vlastní slovník 1, který obsahuje jednotlivé slovní formy a interpunkcˇní znaménka daného jazyka. Σc oznacˇuje tzv. kategoriální seznam, tedy množinu syntakticko-morfologických znacˇek. Hlavní slovník Γ ⊆ Σp × Σc reprezentuje zjednoznacˇneˇnou lexikální analýzu daného jazyka.
Projekce z Γ+ do Σ∗p resp. do Σc∗ pˇrirozeneˇ definujeme pomocí homomorfismu˚: slovníkovým homomorfismem hp : Γ → Σp a kategoriálním homomorfismem hc : Γ → Σc: hp([a, b]) = a a hc([a, b]) = b pro všechny [a, b] ∈ Γ.
pracujeme s hlavním slovníkem oznacˇeným jako ΓPDT , ΣpPDT oznacˇuje vlastní slovník a ΣcPDT oznacˇuje kategoriální seznam znacˇek, užívaných v PDT.
Rozhodl.Pred
chází z prˇíkladu 1. { Rozhodl, se, dnes , odstoupit, . } ⊂ ΣpPDT , { Pred, AuxT, Adv, Sb, AuxK} ⊂ ΣcPDT , { [Rozhodl,Pred], [se,AuxT], [dnes,Adv], [odstoupit,Sb], [.,AuxK]} ⊂ ΓPDT .
prˇirˇazujeme jména (b1 atd.), která budeme v dalších prˇíkladech užívat jako zkratky. b1= [Rozhodl,Pred], b2=[se,AuxT], b3= [dnes,Adv], b4=[odstoupit,Sb], b5=[.,AuxK].
V abecedeˇ kategorií v tomto prˇíkladeˇ jsou využity jen jednoduché závislostní kategorie (ne všechny). Kategorie mohou být složené z více znacˇek. Kategorie pro koordinace budou obsahovat znacˇky ’Cr’, nebo ’Co’.
Veˇty v našich prˇíkladech koncˇí sentinelem (ukoncˇením veˇty), který se beˇhem redukcˇní analýzy ani nevypouští, ani neprˇesunuje. Je to [.,AuxK]. 2.2
V následující cˇásti budeme reprezentovat veˇty pomocí tzv. R-seznamu˚ a jejich syntaktické struktury pomocí Astromu˚. R-seznamy a A-stromy jsou datové typy, vhodné pro používání operací delete a shift. Na R-seznamech a A-stromech zavádíme uniformním zpu˚sobem redukce, založené práveˇ na operacích delete a shift. Redukcˇní seznamy (R-seznamy) zjemnˇují pojem rˇeteˇzu a A-stromy nesou více informace než R-seznamy. A-strom a R-seznam se skládají z uzlu˚, které v PDT reprezenují výskyty lexikálních jednotek (slov, interpunkcˇních znamének a jejich znacˇek) v príslušné veˇteˇ.
V A-stromu jsou pomocí stromové struktury reprezentovány syntaktické vztahy, pomocí R-seznamu, jež je soucˇástí každého A-stromu, je reprezentováno porˇadí slov. R-seznam. Necht’ I je konecˇná množina prˇirozených cˇísel, Γ konecˇná abeceda a V ⊆ (I × Γ), kde V reprezentuje totální zobrazení množiny I do Γ. Necht’ ord je úplné usporˇádání množiny V . Rˇíkáme, že ord je redukcˇním seznamem (R-seznamem) na Γ. Zapisujeme ho jako seznam prvku˚ z V . Prvky R-seznamu oznacˇujeme jako uzly. Množinu R-seznamu˚, která vznikla všemi možnými usporˇádáními množiny V , oznacˇujeme jako ord(V ).
Necht’ u ∈ V , pak u = [i, a], kde i ∈ I, a ∈ Γ. Rˇ íkáme, že i je indexem uzlu u. Slouží k jednoznacˇné identifikaci uzlu.
A-strom. A-strom nad Γ je trojice s = (V, E, ord), kde (V, E) je orientovaný strom, jehož (maximální) cesty zacˇínají v listech a koncˇí v korˇeni, V je konecˇná množina jeho uzlu˚, E ⊂ V × V konecˇná množina jeho hran a ord ∈ ord(V ). Rˇ íkáme, že ord je R-seznamem A-stromu s. Píšeme R(s) = ord.
Projekce. Je-li ord = ([i1, a1], · · · , [in, an]), tak w = a1 · · · an je rˇeteˇz (resp. veˇta), který oznacˇujeme Str(s) = w nebo Str(ord) = w, a rˇíkáme, že w je rˇeteˇzem (projekcí) A-stromu s nebo rˇeteˇzem (projekcí) R-seznamu ord. Normalizace. Rˇ íkáme, že A-strom s = (V, E, ord) (Rseznam ord) je normalizovaný, pokud ord má tvar ord = ([1, a1], [2, a2], · · · , [n, an]). Normalizace A-stromu s = (V, E, ord) je takový normalizovaný A-strom s1 = (V1, E1, ord1), pro který (V, E) a (V1, E1) jsou izomorfní a Str(s) = Str(s1). Všimneˇme si, že normalizace A-stromu je jednoznacˇneˇ daná.
Ekvivalence. Dva A-stromy (R-seznamy) jsou ekvivalentní, pokud mají stejnou normalizaci. Ekvivalentní Astromy cˇasto nebudeme rozlišovat.
Operace shift a delete zavedeme tak, že prˇevedou A-strom na A-strom.
Delete. Operace dl(i) vyrˇadí z množiny V a z R-seznamu ord uzel tvaru [i, ai] a získá tím množinu V1 a R-seznam ord1. Z A-stromu s = (V, E, ord) operace dl(i) udeˇlá Astrom s1 = (V1, E1, ord1) tím, že vyrˇadí uzel tvaru [i, ai] jak z množiny V , tak z R-seznamu ord. Dále vyrˇadí z E všechny dvojice hran tvaru ([ j, a j], [i, ai]) a ([i, ai], [k, ak]) (pokud existují). Každou takovou dvojici hran nahradí v E1 jedinou hranou tvaru ([ j, a j], [k, ak]). Viz prˇíklad 3. Shift. Operace sh(i, j) prˇesune v R-seznamu ord uzel s indexem i prˇed uzel s indexem j. Vytvorˇí tak nový Rseznam ord2. Provedeme-li operaci sh(i, j) na A-strom s = (V, E, ord), získáme tím A-strom s2 = (V, E, ord2). Operace shift meˇní v A-stromeˇ pouze R-seznam, tedy slovosled. Viz prˇíklad 4.
Poznámka. Prˇipomenˇme si, že operace mají být voleny tak, že posledním uzlem trvale zu˚stává sentinel. 2.3
URAS (Úplná redukcˇní analýza A-stromu).
Zavádíme URAS s možností regulace pomocí množiny (významoveˇ) zakázaných redukcí. Prˇíkladem zakázané redukce A-stromu˚ z PDT, je vynechání prˇedložky z prˇedložkové vazby, cˇi vynechání samotné zvratné cˇástice. Znacˇení. Necht’ Γ je konecˇná abeceda. T (Γ) znacˇí množinu všech A-stromu˚ na Γ. Necht’ T ⊆ T (Γ). Rˇ íkáme, že T tvorˇí T-jazyk na Γ. Množinu R-seznamu˚ R(T) = {R(t) | t ∈ T} nazýváme R-jazykem T-jazyka T. Analogicky, jazyk Str(T) = {Str(t) | t ∈ T} nazýváme Str-jazykem T. Necht’ Z ⊂ {(s,t)|s,t ∈ T} je daná množina zakázaných redukcí na T. Oznacˇíme Str(Z) = {(Str(s), Str(t))|(s,t) ∈ Z} a R(Z) = {(R(s), R(t))|(s,t) ∈ Z}.
Redukce. Nyní zavedeme k T-jazyku T a dané množineˇ Z zakázaných redukcí Z redukce typu ⊢T . Necht’ s,t jsou Astromy. Rˇíkáme, že s je prˇímo redukovatelné na t podle T a Z a píšeme s ⊢ZT t pokud: • s,t ∈ T a |Str(s)| > |Str(t)| a (s,t) není ze Z; • t je získáno z s provedením množiny operací vypušteˇní (deletu˚) Dl a následneˇ postupným provedením shiftu˚ z usporˇádané množiny Sh. Dl je povinneˇ neprázdná, Sh mu˚že být prázdná. • Libovolný uzel je prˇesouván pomocí Sh maximálneˇ jednou. • Operacˇní nezmenšitelnost redukce. Pokud bychom vynechali prˇi aplikaci na s jednu nebo více operací z Dl nebo z Sh, získali bychom A-strom z takový, že z ∈/ T, nebo (s, z) ∈ Z. • Jako DL(s, t) oznacˇujeme množinu uzlu˚ A-stromu s, vypušteˇnou beˇhem redukce s ⊢TZ t a rˇíkáme, že je DLmnožinou redukce s ⊢TZ t. O Sh rˇíkáme, že je SHsekvencí redukce s ⊢ZT t.
Doplnˇ ující pojmy. Reflexívní a tranzitívní uzáveˇr relace ⊢ZT oznacˇujeme ⊢TZ ∗. Cˇ ástecˇné usporˇádání ⊢ZT prˇirozeneˇ definuje • T⊢0ZT = {v ∈ T | ¬∃u ∈ T : v ⊢ZT u} - množina neredukovatelných A-stromu˚ T-jazyka T. • T nZ+1 = {v ∈ T | ∃u ∈ T nZ : u ⊢ZT v} ∪ T nZ , n ∈ N množina A-stromu˚ z T, ⊢kTteré je možné zredukovat ⊢T ⊢T na neredukovatelný A-strom z Tposloupností URASredukcí délky nanejvýš n + 1.
URAS. Pro A-strom s ∈ T a zakázanou množinu Z nazveme URAS(s, T, Z) ={u ⊢TZ v |s ⊢TZ ∗u} (úplnou) redukcˇní analýzou s podle T a Z.
Veˇtev. Necht’ B = (s1, s2, · · · , sn) je posloupnost A-stromu˚ taková, že s1 ⊢TZ s2, s2 ⊢TZ s3, · · ·, sn−1 ⊢TZ sn a sn ∈ T 0Z . ⊢T Rˇ íkáme, že B je veˇtví URAS(s, T, Z) a n je její délka. DL-sekvence a DL-charakteristika. Necht’ Dli je Dlmnožinou redukce si ⊢T si+1 pro 1 ≤ i < n a Dln je množinou uzlu˚ A-stromu sn.
Píšeme Dl(B) = (Dl1, DL2, · · · , Dln−1) a rˇíkáme, že Dl(B) je DL-sekvencí veˇtve B.
Množina Ch(B) = ({Dl1, DL2, · · · , Dln−1}) je DLcharakteristikou veˇtve B.
DL-charakteristika a DL-sekvence se liší tím, že u DLcharakteristiky nezáleží na porˇadí redukcˇních množin, ale u DL-sekvence ano.
Vidíme, že pro 1 ≤ i < j < n jsou Dli a Dl j disjunktní. 2.4
Algebraické vlastnosti závislostí a koordinací u analytických stromu˚ PDT.
Touto podsekcí zacˇíná výsledková cˇást prˇíspeˇvku. Prˇedkládáme výsledky dvou typu˚. Nejcˇasteˇji prezentujeme lingvistická pozorování, formulovaná pomocí zavedeného aparátu. Získali jsme je (neúplným) procházením materiálu z PDT. K pozorováním jsme nenašli žádné výjimky a neveˇrˇíme, že se neˇjaké najdou. Pozorování by meˇla být podneˇtem ke (korpusoveˇ lingvistické) diskusi.
Druhým typem výsledku˚ jsou tvrzení a du˚sledky matematického charakteru. Vycházejí z rozboru prezentovaných (lingvistických) prˇíkladu˚ a z vlastností zavedeného aparátu.
TP v následujícím textu oznacˇuje množinu korektních A-stromu˚ s koordinacemi a závislostmi, zpracovaných metodikou analytické roviny PDT. Rozhodnout o tom, zda daný A-strom patrˇí do TP, by meˇli umeˇt lidé (lingvisté, anotátorˇi), ovládající cˇeštinu a metodiku PDT.
ZP oznacˇuje množinu zakázaných redukcí pro analytickou rovinu PDT.
ZPT13: redukce T12 ⊢TP
T12 = (V2, E2, ord2), pricˇemž V2 = {[1, b1], [2, b2], [3, b3], [4, b4], [5, b5]}
E2 = {([2, b2], [1, b1]), ([3, b3], [4, b4]), ([4, b4], [1, b1]), ([5, b5], [1, b1])}, ord2 = ([1, b1], [2, b2], [3, b3], [4, b4], [5, b5]) T13 = (V3, E3, ord3), pricˇemž V3 = {[1, b1], [2, b2], [3, b3], [5, b5]} E3 = {([2, b2], [1, b1]), ([3, b3], [1, b1]), ([5, b5], [1, b1])} ord3 = ([1, b1], [2, b2], [3, b3], [5, b5])
Následují strukturální pozorování A-stromu˚ z TP. Pozorování odrážejí syntaktické vlastnosti cˇeských veˇt a anotátorskou metodiku pro analytickou rovinu PDT. Naše prˇíklady tato pozorování ilustrují.
huje koordinace (tj. znacˇky ´Cr´ a ´Co´). Všechny veˇtve
diný neredukovatelný A-strom. Tedy URAS(s, TP, ZP) lze považovat za (algebraickou strukturu zvanou) svaz.
sahuje koordinace a r1, r2 jsou dveˇ ru˚zné redukce z
množiny.
huje koordinaci alesponˇ trˇí cˇlenu˚. Existují dveˇ veˇtve
huje koordinaci alesponˇ trˇí cˇlenu˚. Existují dveˇ redukce z URAS(s, TP, ZP), které nemají disjunktní DL-množiny.
Prˇedchozí dveˇ pozorování jsou ilustrovány prˇíkladem 4. Tvrzení 1. Existuje t ∈ TP, jehož URAS obsahuje více než jeden neredukovalelný A-strom.
Prˇedchozí tvrzení lze dokázat pomocí A-stromu k veˇteˇ ’Prˇišel, videˇl, zvíteˇzil.’. 2.5
Abychom mohli dát do souvislosti URAS se starším pojmem, veˇtnou redukcˇní analýzou, zavádíme úplnou veˇtnou redukcˇní analýzu (UPRA), viz [3]. Do UPRA vstupuje veˇta ve formeˇ R-seznamu. UPRA zavádíme zcela analogicky jako URAS.
Redukce. Meˇjme jazyk L a R-seznam u takový, že Str(u) ∈ L. Rˇ íkáme, že u je R-seznamem k jazyku L a píšeme u ∈ R(L). Necht’ U ⊂ {(u, v)|u, v ∈ R(L)} je daná množina zakázaných redukcí.
Zavedeme k R(L) a dané U redukce ≻UL . Necht’ u, v ∈ R(L). Rˇ íkáme, že u je redukovatelné na v podle L a U a oznacˇujeme u ≻UL v, pokud: • |Str(u)| > |Str(v)| a (u,v) není z U ; • R-seznam v je získán z u provedením množiny operací vypušteˇní (deletu˚) Dl a následneˇ postupným provedením shiftu˚ z usporˇádané množiny Sh. Dl je povinneˇ neprázdná, Sh mu˚že být prázdná. • Libovolný uzel je prˇesouván pomocí Sh maximálneˇ jednou. • Operacˇní nezmenšitelnost redukce. Pokud bychom vynechali prˇi aplikaci na u jednu nebo více operací z Dl nebo z Sh, získali bychom R-seznam z takový, že Str(z) ∈/ L, nebo (u, z) ∈ U . • Jako Dl(u, v) oznacˇujeme množinu uzlu˚ R-seznamu u, vypušteˇnou provedením množiny deletu˚ Dl a rˇíkáme, že Dl(u, v) je DL-množinou redukce u ≻UL v.
O Sh rˇíkáme, že je SH-sekvencí redukce u ≻UL v. UPRA. Necht’ w ∈ R(L) a U ⊂ {(u, v)|u, v ∈ R(L)} je daná U množina zakázaných redukcí. UPRA(w, L,U ) ={u ≻L v |w ≻UL ∗u} nazveme úplnou redukcˇní analýzou w k jazyku L a množineˇ nekorektních redukcí U .
Zbývající potrˇebné pojmy pro UPRA lze zavést zcela analogicky jako pro URAS. 2.6
Zavádíme dveˇ míry nesouvislosti redukcí, které se vzájemneˇ doplnˇují. S ohledem na tyto a další míry zavádíme neˇkolik typu˚ stability pro URAS, které nám dovolí klasifikovat omezená URAS jako stabilní, nebo nestabilní. Stabilita URAS pro jednotlivé A-stromy je formálním kriteriem pro lingvistickou adekvátnost redukcˇní analýzy, s ohledem na daná omezení. Budeme hledat maximální omezení taková, která zachovávají alesponˇ nejslabší typ stability. Následuje neˇkolik formálních definic.
Graf redukce. Meˇjme redukci s ⊢TZ t, kde s = (V, E, or), a její DL-množinu DL(s,t). Píšeme G(s,t) = (DL(s,t), {(a, b) ∈ E|a, b ∈ DL(s,t)}) a rˇíkáme, že G(s,t) je DL-grafem redukce s ⊢TZ t.
Pocˇet komponent redukce. Necht’ i je pocˇet komponent DL-grafu G(s,t). Budeme psát, že pk(s,t) = i a rˇíkat, že i je pocˇet komponent redukce s ⊢TZ t.
URAS s omezeným pocˇtem komponent. Necht’ i je prˇirozené cˇíslo. Oznacˇíme jako URAS(s, T, Z; pk ≤ i) podmnožinu URAS(s, T, Z), která obsahuje všechny redukce z URAS(s, T, Z), které nemají více komponent než i. Vidíme, že neredukovatelné stromy v URAS(s, T, Z; pk ≤ i) mohou být pro neˇkterá i jiné (veˇtší), než ty z URAS(s, T, Z).
Rˇ íkáme, že URAS(s, T, Z; pk ≤ i) je pro dané i T-stabilní, pokud URAS(s, T, Z; pk ≤ i) = URAS(s, T, Z). Rˇ íkáme, že URAS(s, T, Z; pk ≤ i) je pro dané i CHstabilní, pokud množina charakteristik URAS(s, T, Z; pk ≤ i) a URAS(s, T, Z) je stejná.
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 i neredukovatelným stromem URAS(s, T, Z).
Požadavky na stabilitu jsou serˇazeny od nejsilneˇjší k nejslabší. Nahlédneme, že stejneˇ mu˚žeme užívat zavedené typy stability pro další typy redukcˇních omezení. Pocˇet komponent je jednou prˇirozenou mírou nesouvislosti redukce A-stromu. Budeme používat ješteˇ jednu míru nesouvislosti redukce, která meˇrˇí velikost mezer mezi komponentami. Následují další formální definice. Velikost mezer v redukci. Jako Sv(s,t) budeme oznacˇovat nejmenší souvislý (bez ohledu na orientaci) podgraf Astromu s, který obsahuje DL-graf G(s,t). Necht’ j je pocˇet uzlu˚, které obsahuje Sv(s, t) navíc oproti G(s,t). Píšeme ns(s,t) = j a rˇíkáme, že redukce s ⊢TZ t má velikost mezer j.
URAS s omezením na velikost mezer. Necht’ i je prˇirozené cˇíslo. Oznacˇíme jako URAS(s, T, Z : ns ≤ i) podmnožinu URAS(s, T, Z), která obsahuje všechny redukce z URAS(s, T, Z), které nemají velikost mezer veˇtší než i. Omezení mu˚žeme i skládat. Naprˇ. URAS(s, T, Z; pk ≤ i, ns ≤ j) = URAS(s, T, Z; pk ≤ i) ∩ URAS(s, T, Z; ns ≤ j). Množiny stromu˚ stabililní s ohledem na omezení. Budeme používat následující typy znacˇení pro množiny Astromu˚ splnˇující daná omezení.
Naprˇ. TRAS(T, Z; pk ≤ 1, ns ≤ 0; T-st ) = {t ∈ T | URAS(t, T, Z; pk ≤ 1, ns ≤ 0) je T-stabilní }.
Analogicky TRAS(T, Z; pk ≤ 1; CH-st ) = {t ∈ T | URAS(t, T, Z; pk ≤ 1) je CH-stabilní }. Podobneˇ budeme popisovat množiny A-stromu˚ z T parametrizované dalšími omezeními a ru˚znými typy stability ze škály T-stabilní, CH-stabilní, Mn-stabilní. 2.7
Prˇedchozí pojmy a následující prˇíklady využijeme k formulaci nových pozorování o PDT.
ných koordinací a použití grafoveˇ nesouvislé redukce v
stromu T31, jazyka Tp a prázdné zakázané množiny.
Veˇta (
nodušování trojnásobné koordinace na dvojnásobnou) dva nesouvisející listy (podstromy). Trˇetí redukce navíc používá shift. Zbývající redukce dvojnásobných koordinací se realizují postupným vypoušteˇním listu˚, které tvorˇí souvislý úplný podstrom.
Je.Pred dědou.Obj.Co ,.AuxX otcem.Obj.Co a. Cr strýcem.Obj.Co ..AuxK Je.Pred otcem.Obj.Co a.Cr strýcem.Obj.Co ..AuxK
Je.Pred dědou.Obj.Co a.Cr strýcem.Obj.Co ..AuxK shift
Je.Pred dědou.Obj.Co a.Cr otcem.Obj.Co ..AuxK
Je.Pred ..AuxK
Obrázek 5: UPRA veˇty (
Je.Pred dědou.Obj.Co
a.Cr ,.AuxX
otcem.Obj.Co Obrázek 6: A-strom T31.
URAS(T11, TP, ZP; pk ≤ 1) je T-stabilní, URAS(T31, TP, ZP; pk ≤ 2) je T-stabilní a URAS(T31, TP, ZP; pk ≤ 1) není Mn-stabilní.
Poznámky k prˇedchozímu pozorování. Podobneˇ jako u T31, každá alesponˇ trojnásobná koordinace z PDT vyžaduje alesponˇ jednu redukci se dveˇma komponentami. Pokud povolíme redukce s maximálneˇ jednou komponentou, bude každý neredukovatelný strom z URAS(s, TP, ZP; pk ≤ 1) minimálneˇ o jednu nevykonanou redukci veˇtší, než prˇíslušný neredukovatelný strom z URAS(s, TP, ZP).
Pozorování o velikosti mezer jsou analogická pozorováním o pocˇtu komponent. Du˚ležité pozorování je, že koordinace dovolují redukcím jen velikost mezer rovnou jedné a stromy bez koordinací dovolují redukcím jen jedinou komponentu.
TRAS(TP, ZP, ns ≤ 0; T-st ) = TRAS(TP, ZP; pk ≤ 1; T-st), TRAS(TP, ZP; ns ≤ 1; T-st ) = TRAS(TP, ZP, pk ≤ 2; T-st) = TP.
Pozorování 10. Necht’ s ∈ TP je A-strom bez koordinací. 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 alesponˇ trojnásobnou koordinací. Platí, že URAS(s, TP, ZP; ns ≤ 0) není
2.8
Snažíme se minimalizovat prˇi redukcích zmeˇny hran (zmeˇny významu), takže se snažíme redukovat stromy bez koordinací tak, že vypouštíme v jistém porˇadí jen listy. Pojmy zavádeˇné v tomto odstavci zavádíme za dvojím úcˇelem. Prvním úcˇelem je dát prostrˇedky pro formální aproximaci intuitivní redukcˇní analýzy stromu˚ bez koordinací. Druhým úcˇelem je exaktneˇ zachytit fakt, že redukce vložených koordinací nutneˇ používají vypušteˇní vnitrˇního uzlu a charakterizovat složitost tohoto faktu. Prˇi redukci vložených koordinací se význam redukovaného stromu nijak nemeˇní.
Necht’ o je neˇjaké usporˇádání množiny Dl, kde Dl je DL-množinou neˇjaké redukce A-stromu s. Pak rˇíkáme, že o realizuje Dl na s. Píšeme o ∈ ord(Dl, s).
IN-stupneˇm operace dl(i) na A-stromeˇ s nazveme pocˇet hran z E vcházejících do uzlu [i, ai]. Všimneˇme si, že delete uzlu [i, ai] má IN-stupenˇ 0 práveˇ tehdy, pokud [i, ai] je listem A-stromu s.
Uvažujme ru˚zné realizace množiny Dl, kde Dl je DLmnožina na s. V ru˚zných realizacích Dl na s mu˚že mít dl(i) ∈ Dl ru˚znou hodnotu svého IN-stupneˇ, nebot’ dl(i) mu˚že být provádeˇna na ru˚zných A-stromech.
Omezíme se jen na neklesající realizace DL-množin v redukcích, nebot’ realizace vypoušteˇjící jen listy musí být neklesající. Budeme využívat faktu, že ke každé redukci existuje neklesající realizace.
Znacˇení. Rˇ í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 IN(dl(i1)) ≤ IN(dl(i2)), · · · , IN(dl(in−1)) ≤ IN(dl(in)). 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í prvek z o je dl( j). Budeme psát MinIN(o) = IN(dl(i)) a MaxIN(o) = IN(dl( j)).
URAS se spodní mírou (ne)listovosti. Oznacˇíme jako URAS(s, T, Z; MinIn ≤ i) podmnožinu URAS(s, T, Z), která obsahuje všechny redukce z URAS(s, T, Z), které mají neklesající realizaci o s MinIN(o) ≤ i.
URAS s horní mírou (ne)listovosti. Oznacˇíme jako URAS(s, T, Z; MaxIN ≤ i) podmnožinu URAS(s, T, Z), která obsahuje všechny redukce z URAS(s, T, Z), které mají neklesající realizaci o s MaxIN(o) ≤ i. 2.9
Závislosti, vložená koordinace a (ne)listovost.
koordinací.
(5) Pracujeme.Pred.Co a.Cr.Co myslíme.Pred.Co i..Cr jednáme.Pred.Co..AuxK
TP a ZP. Veˇta (5) je veˇta s vloženou koordinací. A-stromy odpovídající redukcím jsou na obrázcích 10 až 12. Vložená koordinace se v A-stromeˇ T51 zjednodušuje tak, že se vyjme jedna hrana s rˇídícím uzlem se znacˇkou ’Cr.Co’. To odpovídá dveˇma redukcím v UPRA z obrázku . Vidíme, že tyto redukce vypoušteˇjí jeden list a jeden vnitrˇní uzel do kterého vchází jediná hrana.
Pracujeme. Pred.Co a.Cr.Co myslíme. Pred.Co i .Cr jednáme. Pred.Co ..AuxK Pracujeme. Pred.Co i. Cr jednáme. Pred.Co ..AuxK
myslíme. Pred.Co i .Cr jednáme. Pred.Co ..AuxK Obrázek 9: UPRA veˇty s vloženou koordinací.
a.Cr.Co pracujeme.Pred.Co myslíme.Pred.Co Obrázek 10: T51 i.Cr
..AuxK jednáme.Pred.Co
1 platí, že URAS(T 11, TP, ZP; MaxIN ≤ 0) je T-stabilní.
platí, že URAS(T12, TP, MaxIN ≤ 0) není T-stabilní, ale je Mn-stabilní. Navíc URAS(T12, TP, MinIn ≤ 1, MaxIN ≤ 1) je T-stabilní.
• TRAS(TP, ZP; MaxIN ≤ 0; T-st ) • TRAS(TP, ZP; MinIN ≤ 0; T-st ) ⊂ TRAS(TP, ZP; MaxIN ≤ 1; T-st).
⊂ TRAS(TP, ZP; MinIN ≤ 1; T-st).
Pozorování 12. TRAS(TP, ZP; MinIN ≤ 1; T-st ) ⊂ TP.
URAS(T51, TP, ZP; MinIN ≤ 0) je T-stabilní, URAS(T51, TP, ZP; MaxIN ≤ 0) není Mn-stabilní a URAS(T51, TP, ZP; MinIN ≤ 0, MaxIN ≤ 1) je T-stabilní.
platí T51 ∈TRAS(TP, ZP; MinIN ≤ 0, MaxIn ≤ 1; T-st ) Pozorování 13. Necht’ t ∈ TP nese koordinaci vloženou do koordinace. Platí, že URAS(t, TP, ZP; MaxIN ≤ 0) není
Du˚ sledek 3. Vidíme, že • TRAS(TP, ZP; MaxIN ≤ 0; T-st )
⊂ TRAS(TP, ZP; MinIN ≤ 0; MaxIn ≤ 1; Mn-st) • TRAS(TP, ZP; MinIN ≤ 0; MaxIn ≤ 1; Mn-st) ⊂ TRAS(TP, ZP; MinIN ≤ 1; MaxIn ≤ 1; Mn-st ) i.Cr
..AuxK jednáme.Pred.Co pracujeme.Pred.Co Obrázek 11: T 52, vzniklé redukcí z T51. jednáme.Pred.Co ..AuxK
• TRAS(TP, ZP; MinIN ≤ 1, MaxIn ≤ 1; Mn-st ) ⊆ TP. Poznámka. Pro každé t ∈ TP , které jsme pozorovali, bylo URAS(t, TP, ZP; MinIN ≤ 1) Mn-stabilní. Neumíme odhadnout, zda existuje A-strom t ∈ TP takový, že URAS(t, TP, ZP; MinIN ≤ 1) není Mn-stabilní, tedy zda TRAS(TP, ZP, MinIN ≤ 1, MaxInPc ≤ 1; Mn-st ) = TP. 2.10
LP znacˇí množinu korektních cˇeských veˇt (jen) s koordinacemi a závislostmi, která je korektneˇ znacˇkovaná metodikou analytické roviny PDT. Prˇipomenˇme, že TP oznacˇuje množinu všech korektních A-stromu˚ s koordinacemi a závislostmi, zpracovaných metodikou analytické roviny PDT. ZP oznacˇuje množinu zakázaných redukcí na TP.
Následuje pozorování o konzistenci mezi URAS na TP a UPRA na LP.
Podle našich pozorování a naší notace platí, že LP = Str(TP), R(LP) = R(TP) a U P = R(ZP). s,t ∈ TP a R(s) ≻ULPP R(t), pak s ⊢ZTPP t.
Pozorování 14. Necht’ s ⊢ZTPP t, pak R(s) ≻ULPP R(t). Necht’
Prˇedchozí pozorování formuluje vlastnost konzistence mezi UPRA a PRAS. Rˇ íká, že A-stromy z PDT jsou konstruovány v souladu s veˇtnou redukcˇní analýzou. Toto pozorování je naším základním pozorováním analytické roviny PDT. Prˇirozeneˇ všechny zde prezentované prˇíklady na URAS a UPRA splnˇují podmínky konzistence mezi URAS a UPRA. 2.11
Následující omezení mají, na rozdíl od prˇedchozích podobnou platnost pro URAS i pro UPRA.
URAS s omezením na pocˇet deletu˚ . Necht’ i je prˇirozené cˇíslo. Oznacˇíme jako URAS(s, T, Z : dl ≤ i) podmnožinu URAS(s, T, Z), která obsahuje všechny redukce z URAS(s, T, Z), které nemají pocˇet deletu˚ veˇtší než i. URAS s omezením na vzdálenost vypoušteˇných uzlu˚ . Necht’ k je prˇirozené cˇíslo. Oznacˇíme jako URAS(s, T, Z : ds ≤ k) podmnožinu URAS(s, T, Z), která obsahuje všechny redukce z URAS(s, T, Z), které nemají vzdálenost mezi vypoušteˇnými uzly (podle usporˇádání v R-seznamu) veˇtší než k.
Prˇíklad 6. Uvažujme formální jazyk L1 = {anbn|n > 0}. Každému slovu (veˇteˇ) tohoto jazyka prˇirˇadíme A-strom tn následujícím zpu˚sobem:
levého souseda,
sahuje.
Budiž T1 = {tn|n > 0}. Vidíme, že TRAS(T1, 0/; dl ≤ 2, ds ≤ 2, pk ≤ 1, MaxIn ≤ 0; T-st) = T1.
teristiku T-jazyka T1. Zmenšením kteréhokoliv parametru bud’ rovnost ztrácíme, nebo zmenšení parametru nemá smysl.
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 platí, že TRAS(T, 0/; ds ≤ k, Mn-st )6= T .
tuje k ∈ N takové, že pro libovolné u ∈ R(L) platí, že UPRA(u, L, 0/; ds ≤ k) je Mn-stabilní.