Back to search

Vysoké učení technické v Brně. Fakulta informačních technologií

Redukce velikosti konečných automatů pomocí SAT solveru

Abstract

dc:description.abstract

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.

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 × 17

Rights

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

Chain of custody

source
Harvested from
Brno University of Technology
Base URL
dspace.vut.cz/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Šedý, Michal. Redukce velikosti konečných automatů pomocí SAT solveru. Bakalářský thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, http://hdl.handle.net/11012/199331