Efektivní automatové techniky a jejich aplikace
Autor: | Havlena, Vojtěch |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2021 |
Předmět: |
approximate reduction
komplementace Buchiho automatů rank-based komplementace teorie řetězců quadratic word equations rank-based complementation Buchi automata complementation rozhodovací procedury minimalizace kvadratické rovnice nad slovy theory of strings Konečné automaty minimization antiprenexní forma decision procedures stromové automaty tree automata Finite automata WSkS antiprenexing automata terms automatové termy přibližná redukce |
Druh dokumentu: | Doctoral Thesis |
Popis: | Tato práce se zabývá vývojem efektivních technik pro konečné automaty a jejich aplikace. Zejména se věnujeme konečným automatům použitých pří detekci útoků v síťovém provozu a automatům v rozhodovacích procedurách a verifikaci. V první části práce navrhujeme techniky přibližné redukce nedeterministických automatů, které snižují spotřebu zdrojů v hardwarově akcelerovaném zkoumání obsahu paketů. Druhá část práce je je věnována automatům v rozhodovacích procedurách, zejména slabé monadické logice druhého řádů k následníků (WSkS) a teorie nad řetězci. Navrhujeme novou rozhodovací proceduru pro WS2S založenou na automatových termech, umožňující efektivně prořezávat stavový prostor. Dále studujeme techniky předzpracování WSkS formulí za účelem snížení velikosti konstruovaných automatů. Automaty jsme také aplikovali v rozhodovací proceduře teorie nad řetězci pro efektivní reprezentaci důkazového stromu. V poslední části práce potom navrhujeme optimalizace rank-based komplementace Buchiho automatů, které snižuje počet generovaných stavů během konstrukce komplementu. |
Databáze: | Networked Digital Library of Theses & Dissertations |
Externí odkaz: |