2-INF-158 Systémy na prepisovanie termov
Odporúčaný ročník: | 2. |
Semester: | zimný |
Rozsah: | P3 |
Hodnotenie: | 30/70 |
Počet kreditov: | 4 |
Vyučujúci: | prednáša RNDr. Marián Vittek PhD. |
www stránka: | |
Predmet je v tomto akademickom roku suspendovaný. |
Cieľ:
- uviesť systémy na prepisovanie termov ako výpočtový model podporený jazykom ELAN
- študovať vlastnosti systémov na prepisovanie termov
- prezentovať princípy constraint solving
- prezentovať ekvacionálne programovanie ako integráciu tradičných deklaratívnych paradigiem (funkc. a log. programovania)
Sylabus:
- prepisovanie termov - vlastnosti systémov na prepisovanie termov
- abstraktné redukčné relácie - konvergentné (t.j. noetherovské a konfluentné) relácie, skladanie konvergentných relácií
- postačujúce podmienky zastavenia a konfluentnosti systémov na prepisovanie termov - zjednodušujúce usporiadanie, kritické dvojice termov
- zúplňovacie procedúry - Knuth-Bendixova procedúra, "nepadajúca" zúplňovacia procedúra, analýza zúplňovania (skrížené dvojice)
- modifikácie systémov na prepisovanie termov – podmienkové systémy, ekvacionálne prepisovacie systémy, modulárne systémy, prepisovanie termov na grafoch
- unifikačné problémy - porovnanie so vzorkou, unifikácia, unifikácia nekonečných termov, sémantická unifikácia, druhovo-usporiadaná unifikácia, unifikácia vyšších rádov
- efektívne unifikačné algoritmy - deštruktívne vs. nedeštruktívne algoritmy, viacnásobné porovnávanie so vzorkou, viacnásobná unifikácia
- programovací jazyk ELAN založený na prepisovaní termov - stratégie riadiace prepisovanie termov
- integrácia všeobecných metód logického programovania (goal solving) s (efektívnymi) špecializovanými algoritmami nad konkrétnym oborom (constraint solving)
- ekvacionálne programovanie - integrácia funkcionálneho a logického programovania, "equation and constraint solving", prepisovanie zužovaním, stratégie ekvacionálneho výpočtu
Literatúra:
Dershowitz,N., Jouannaud,J.P.: Rewrite Systems. Handbook of Theoretical Computer Science, Vol. B, Formal Models and Semantics, Elsevier Science Publisher B.V., 1990
Ružička,P., Prívara,I.: Variácie na tému unifikácia. Informačné Systémy 20/1-2, 1991
Jouannaud,J.P., Kirchner,C.: Solving equations in abstract algebras. 1990