Detail práce
Reducing Size of Nondeterministic Automata with SAT Solvers
Nedeterministické konečné automaty (NKA) jsou široce využívány v počítačové vědě, například v oblasti formálních jazyků pro reprezentaci regulárních jazyků, k monitorování vysokorychlostních sítí, rozpoznávání obrazu, modelování hardware, nebo dokonce v bioinformatice pro vyhledávání sekvencí nukleotidových kyselin v DNA. NKA jsou také používány v abstraktním regulárním model checkingu, dále ve verifikaci programů manupulujících s řetězci, ve verifikaci programů využívajících ukazatele, pro konstrukci lineárních rovnic a nerovnic, v rozhodovacích procedurách WS1S a WS2S logiky a mnohých dalších. Minimalizace automatů je základní technikou, která pomáhá snižovat nároky na zdroje (paměť, čas nebo množství hardwarových komponentů) a urychlovat operace prováděné na automatech. Běžně používané minimalizační techniky, jakými jsou slučování stavů, odstraňování hran přechodů nebo saturace, mohou v automatech zanechat potenciální minimalizovatelné podgrafy obsahující duplicitní jazykovou informaci. Tyto fragmenty sestávají ze skupiny stavů, kde je již část jazyka jednoho stavu pokryta jazyky ostatních stavů z této skupiny. Tato práce popisuje novou techniku využívající SAT solver, který poskytuje informaci umožňující minimalizovat tyto doposud neminimalizovatelné části automatů. Nově vyvíjená metoda, která využívá pouze informaci od SAT solveru a slučování stavů minimalizuje automaty podobně efektivně, a v případě automatů s nízkým počtem přechodů dokonce rychleji než nástroj RABIT/Reduce, který využívá slučování stavů a odstraňování hran.
konečné automaty, nedeterministické konečné automaty, minimalizace, redukce, SAT solver, Z3 solver, ekvivalence stavů, ekvivalence jazyků, slučování stavů, quotienting
Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm "A".
- Zkoušel jste se porovnat s nástrojem RABIT/Reduce i pro větší lookahead než 1?
- Máte představu na automatech jakých strukturálních vlastností dává Váš přístup nejlepší výsledky v porovnání s nástrojem RABIT/Reduce?
- Komise, například: Proč se nepařilo oponentovi aplikaci spustit?
- Komise, například: Je Váš kód ve stavu k publikování?
Burget Lukáš, doc. Ing., Ph.D. (UPGM FIT VUT), člen
Mrázek Vojtěch, Ing., Ph.D. (UPSY FIT VUT), člen
Rozman Jaroslav, Ing., Ph.D. (UITS FIT VUT), člen
@bachelorsthesis{FITBT23436,
author = "Michal \v{S}ed\'{y}",
type = "Bakal\'{a}\v{r}sk\'{a} pr\'{a}ce",
title = "Reducing Size of Nondeterministic Automata with SAT Solvers",
school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
year = 2021,
location = "Brno, CZ",
language = "english",
url = "https://www.fit.vut.cz/study/thesis/23436/"
}