Detail publikace

Simulations and Aintichains for Efficient Handling of Tree Automata

HOLÍK Lukáš a VOJNAR Tomáš. Simulations and Aintichains for Efficient Handling of Tree Automata. FIT Monograph. Brno: Fakulta informačních technologií VUT v Brně, 2010. ISBN 978-80-214-4217-7.
Název česky
Simulace a antiřetězy pro efektivní práci se stromovými automaty
Typ
odborná monografie
Jazyk
angličtina
Autoři
Holík Lukáš, doc. Mgr., Ph.D. (UITS FIT VUT)
Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT)
Abstrakt

Cílem této práce je vývoj technik umožnujících praktické využití nedeterministických konečných automatu, zejména nedeterministických stromových automatu. Jde zvláště o techniky pro redukci velikosti a testování jazykové inkluze, jež hrají zásadní roli v mnoha oblastech aplikace konečných automatu. V oblasti redukce velikosti vycházíme z dobře známých metod pro slovní automaty které jsou založeny na relacích simulace. Navrhli jsme efektivní algoritmy pro výpočet stromových variant simulačních relací a identifikovali jsme nový typ relace založený na kombinaci takzvaných horních a dolních simulací nad stromovými automaty. Tyto kombinované relace jsou zvláště vhodné pro redukci velikosti automatu slučováním stavu. Navržený princip kombinace relací simulace je relevantní i pro slovní automaty. Náš přínos v oblasti testování jazykové inkluze je dvojí. Nejprve jsme zobecnili na stromové automaty algoritmy založené na tzv. protiřetězech, které byly původně navrženy pro slovní automaty. Dále se nám podařilo použitím simulačních relací výrazně zefektivnit protiřetězové algoritmy pro testování jazykové inkluze jak pro slovní, tak pro stromové automaty. Relevanci našich technik pro praxi jsme demonstrovali jejich nasazením v rámci regulárního stromového model checkingu, což je verifikační metoda založená na stromových automatech. Použití našich algoritmu zde vedlo k výraznému zrychlení a zvetšení škálovatelnosti celé metody. Základní myšlenky našich algoritmu pro redukci velikosti automatu a testování jazykové inkluze jsou aplikovatelné i na jiné typy automatu. Příkladem jsou naše redukční techniky pro alternující Büchiho automaty prezentované v poslední části práce.

Rok
2010
Strany
150
Řada
FIT Monograph
ISBN
978-80-214-4217-7
Vydavatel
Fakulta informačních technologií VUT v Brně
Místo
Brno, CZ
BibTeX 
@BOOK{FITPUB9464,
   author = "Luk\'{a}\v{s} Hol\'{i}k and Tom\'{a}\v{s} Vojnar",
   title = "Simulations and Aintichains for Efficient Handling of Tree Automata",
   pages = 150,
   series = "FIT Monograph",
   year = 2010,
   location = "Brno, CZ",
   publisher = "Faculty of Information Technology BUT",
   ISBN = "978-80-214-4217-7",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9464"
}
Nahoru