Bakalářská práce

Semi-Determinization of Omega-Automata

Mikuláš Klokočka
Anotace

Tato bakalářská práce se zabývá tématem semi-deterministických omega-automatů. Jako první mapuje různé definice semi-determinismu Büchiho automatů a ukazuje jejich hierarchii. Práce dále popisuje upravený algoritmus pro semi-determinizaci. Tento algoritmus je implementovaný v nástroji nazvaném Seminator. Seminator je porovnán s ostatními nástroji pro tvorbu semi-deterministických automatů. Výsledky …více

Abstract

This bachelor's thesis deals with the topic of semi-deterministic omega-automata. It first maps the definitions of semi-deterministic Büchi automata and shows a hierarchy of them. The thesis also describes a revised algorithm for semi-determinization. This algorithm is implemented in a tool called Seminator. Seminator is evaluated against other tools producing semi-deterministic automata. The results …více

Klíčová slova
Büchi automata semi-deterministic probabilistic model-checking
Zadání práce
The first goal of this thesis is to map all definitions of semi-deterministic and limit-deterministic omega-automata and describe their relations. The second goal is to study algorithms for semi-determinization and cut-determinization of nondeterministic omega-automata and map existing tools for producing semi-deterministic automata. The third goal is to implement selected algorithms in a tool and then compare the sizes of the produced semi- and cut-deterministic automata, and also compare the sizes of those automata with automata produced by ltl2ldba.
Administrativní informace
Práce zkontrolována:
30. 5. 2017 09:02, prof. RNDr. Jan Strejček, Ph.D., učo 3366
Plný text práce
528,5 KB / soubor PDF
Přílohy (2)
Jazyk práce
angličtina angličtina
Termín obhajoby
29. 6. 2017
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Jan Strejček, Ph.D., učo 3366
ITI FI MU

Oponent

Dr. rer. nat. Achim Blumensath, učo 237782
KTP FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.