Bachelor's thesis
Awards: Dean's Award for an Outstanding Final Thesis

Simple Complementation of Generalized Büchi Automata

David Dokoupil, UČO 514619
Abstract

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 …more

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 …more

Keywords
complementation omega-automata transition-based generalized Büchi automata Spot
Thesis description
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).
Administrative information
The thesis has been checked:
19/5/2023 17:58, prof. RNDr. Jan Strejček, Ph.D., UČO 3366
Full text of thesis
1 MB / file PDF
Attachments (3)
Language used
English English
Defence date
27/6/2023
The thesis was defended successfully

Supervisor

prof. RNDr. Jan Strejček, Ph.D., UČO 3366
KTP FI MU

Reader

Ondřej Lengál
Cite this text
Masaryk University Faculty of Informatics
Programme
Plan
Informatics

Theses on a related topic

List of theses with an identical keyword.

Similar documents

  • 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.