Vysoké učení technické v Brně. Fakulta informačních technologií
Redukce velikosti konečných automatů pomocí SAT solveru
Abstract
dc:description.abstractNedeterministické 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.
Degree
thesis:*- Level thesis:degree_level
- Bakalářský
- Discipline thesis:degree_discipline
- Informační technologie
- Grantor dc:publisher
- Vysoké učení technické v Brně. Fakulta informačních technologií
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Šedý, Michal
- Advisor dc:contributor.advisor
-
- Holík, Lukáš
- Committee members dc:contributor.committeemember
-
- Havlena, Vojtěch
- doc. Ing. Vladimír Janoušek, Ph.D. (předseda) doc. Ing. Lukáš Burget, Ph.D. (místopředseda) prof. Ing. Jan M. Honzík, CSc. (člen) doc. Ing. Vojtěch Mrázek, Ph.D. (člen) Ing. Jaroslav Rozman, Ph.D. (člen)
Subjects
dc:subject × 17Rights
dc:rights- Statement dc:rights
-
- Standardní licenční smlouva - přístup k plnému textu bez omezení
- Language dc:language.iso
- en, angličtina (English)
Identifiers
dc:identifier.*- Dc Identifier Citation
- ŠEDÝ, M. Redukce velikosti konečných automatů pomocí SAT solveru [online]. Brno: Vysoké učení technické v Brně. Fakulta informačních technologií. 2021.
- Dc Identifier Other
- 136460