Nová česká práce z pomezí algebry a teorie grafů

Antonín Říha

[Kronika]

(pdf)

Новая чешская работа о пограничной области алгебры и теории графов / Un Ouvrage récent tchèque concernant l’algèbre et la théorie des graphiques

Jako 25. svazek filologické série Acta Universitatis Carolinae vyšla práce Ladislava Nebeského nazvaná Algebraic Properties of Trees (Praha 1969, 99 s.).

Je to matematická práce z oblasti na pomezí algebry a teorie grafů a ve filologické sérii vychází proto, že studuje některé vlastnosti pojmu v lingvistice hojně užívaného a může přispět vedle zajímavých výsledků matematických také k hlubšímu pochopení některých myšlenek závislostní koncepce syntaxe,[1] resp. inspirovat k řešení dalších lingvistických otázek. Lingvistickému využití práce je věnován obsáhlý dodatek Pavla Nováka.

Nebeského práce obsahuje dva hlavní výsledky: První z nich — ekvivalence pojmů stromová algebra a strom — je odvozen v kapitole první a dále rozšířen v dalších dvou, druhý — nutná a postačující podmínka pro projektivitu — je obsažen v závěrečné, čtvrté kapitole práce.

Důležitým základním pojmem celé práce je pojem průsečíku uzlů grafu. Průsečík uspořádané trojice uzlů (x, y, z) je definován jako uzel, který leží v grafu zároveň na cestě od x do y, od y do z i od x do z. Je zavedena tzv. průsečíková operace, která každé uspořádané trojici uzlů grafu přiřazuje jejich průsečík, pokud existuje. Významnou vlastností průsečíku je, že právě ve stromu má každá uspořádaná trojice uzlů právě jeden průsečík.

Stromová algebra je uspořádaná dvojice (M, P), kde M je množina a P ternární operace na M splňující jisté axiómy. V práci je dokázáno, že existuje vzájemně jednoznačný vztah mezi množinou všech stromů a množinou všech stromových algeber, zajištěný navzájem inverzními relacemi „být vlastní stromovou algebrou stromu“ a „být stromem indukovaným stromovou algebrou“. [82]Přitom vlastní stromová algebra stromu T =(M, H) je stromová algebra A =(M, P), kde P je průsečíková operace definovaná na M. Je-li (M, H) strom, P jeho průsečíková operace, indukuje stromová algebra (M, P) opět strom (M, H).

Odvozené věty poskytují mimo jiné možnost studovat některé problémy týkající se stromů v termínech ekvivalentních algebraických struktur. Pojem průsečíku a výsledky s ním těsně souvisící nebyly dosud soustavně lingvisticky interpretovány. Inspirují k řešení některých zajímavých obecných problémů a je na nich založeno matematické odvození druhého hlavního výsledku práce.

Druhý hlavní výsledek práce je speciálnější a více spjatý s lingvistickou interpretací. Pojem projektivity se vyskytuje především v pracích přijímajících závislostní koncepci syntaxe. Věta se nazývá projektivní, právě když je projektivní její závislostní strom, tj. právě když pro každé dva jeho uzly A, B je splněna následující podmínka: jestliže B následuje za A a A závisí na B nebo B na A, pak každý uzel následující za A a předcházející B (tj. za kterým B následuje) je podřazen uzlu A nebo B.[2] Přitom (budeme-li místo o uzlech mluvit o příslušných větných členech) „B následuje za A“ znamená, že B je ve slovosledném uspořádání na některém z míst od A do konce věty a „A závisí na B“ znamená, že A je gramaticky bezprostředně podřazen B. Pojem projektivity byl formálně definován více autory. Přehled literatury, jednotlivé definice a důkazy jejich ekvivalence podal S. Marcus.[3] L. Nebeský formuluje novou nutnou a postačující podmínku pro projektivitu, která umožňuje zobecnění tohoto pojmu a také, jak uvádí P. Novák, klasifikaci neprojektivních případů. Nutná a postačující podmínka sestává ze dvou požadavků: první z nich je nezávislý na vrcholu stromu a klade jisté omezení na uspořádání uzlů stromu, druhý je jen lokální (týká se nejvýše tří uzlů) a požaduje, aby vrchol ležel na cestě od minimálního do maximálního uzlu v definovaném uspořádání.

P. Novák v dodatku poukazuje na to, že se mu v souboru dosud známých neprojektivních konstrukcí češtiny[4] nepodařilo nalézt takovou, která by nesplňovala alespoň jednu z výše uvedených podmínek, což pokládá za možný příznak toho, že i v lingvistické interpretaci je možno postupovat stejným směrem při studiu podmínek projektivity. Kromě toho poznamenává, že první z obou podmínek je téměř identická s podmínkou spojitosti složek v syntaktické koncepci bezprostředních složek, což přispívá ke zpřesnění pohledu na vzájemný vztah podmínky projektivity a spojitosti složek.

Již v jiných pracích jsme měli příležitost se přesvědčit, že L. Nebeský dovede odkrýt zajímavé základní problémy i nově se postavit k pojmům již definovaným. Jeho práce Algebraic Properties of Trees je toho novým dokladem.

Slovo a slovesnost, ročník 32 (1971), číslo 1, s. 81-82

Předchozí Jiří Krámský: Sborník prací leidenských lingvistů

Následující Jiří Kraus: Užitečná chrestomatie z kvantitativní stylistiky