Bakalářská práce
Získaná ocenění: Cena děkana FI za vynikající závěrečnou práci

Simple Complementation of Generalized Büchi Automata

David Dokoupil, učo 514619
Anotace

Hlavným predmetom tejto práce je rožšírenie existujúcej komplementačnej konštrukcie pre Büchiho automaty s akceptáciou na hranách. Prezentované rožšírenie sa nazýva Simple and General, alebo SaG skrátene. Rožširenie je založené na transformácií pôvodnej konštrukcie s účelom komplementovať Büchiho automaty s akceptáciou na hranách. Následne, je transformácia upravená aby umožnila komplementáciu generalizovaných …více

Abstract

The main focus of this thesis is an extension of an existing complementation construction for state-based Büchi automata. The presented extension is called Simple and General, or SaG for short. The extension is based on transforming the original construction to work with transition-based Büchi automata. The transformation is then modified further to allow the complementation of transition-based generalized …více

Klíčová slova
complementation omega-automata transition-based generalized Büchi automata Spot
Zadání práce
The goal of this thesis is to understand the complementation algorithm for Büchi automata introduced by Allred and Ultes-Nitsche in their paper "A Simple and Optimal Complementation Algorithm for Büchi Automata" published at LICS 2018 and to extend this algorithm to transition-based generalized Büchi automata (TGBA). The correctness of the extended algoirthm will be proven. Further, the extended algorithm will be implemented and evaluated against state of the art tools that are able to complement TGBA either directly or after degeneralization (in particular, against Spot, Seminator 2, and Kofola).
Administrativní informace
Práce zkontrolována:
19. 5. 2023 17:58, prof. RNDr. Jan Strejček, Ph.D., učo 3366
Plný text práce
1 MB / soubor PDF
Přílohy (3)
Jazyk práce
angličtina angličtina
Termín obhajoby
27. 6. 2023
Práce byla úspěšně obhájena

Vedoucí

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

Oponent

Ondřej Lengál
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Informatika

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.