Bakalářská práce

Simulation-Based Reduction of Modal Omega-Automata

Dávid Smolka
Anotace

V tejto práci zavádzame modálne automaty (automaty pracujúce s dvomi množinami prechodov) a zovšeobecňujeme koncepty simulácii, prerezávania a kvocientovanie tak, aby využívali modalitu týchto automatov. Pre určité podmnožiny modálnych simulácii charaktrizujeme tie, ktoré je možno použiť s modálnym prerezávaním alebo modálnym kvocientovaním. Potom ukážeme, ako redukovať problém výpočtu konkrétnej triedy …více

Abstract

In this thesis we introduce modal automata (automata utilizing two sets of transitions) and generalize the concepts of simulations, pruning and quotienting to make use of the modality of such automata. For particular subset of modal simulations, we characterize those that can be used with the modal pruning and modal quotienting. We then show how to reduce the problem of computing particular class these …více

Zadání práce
This thesis will study modal omega-automata, i.e. omega-automata that have besides standard transitions also may-transitions. A modal omega-automaton describes two languages: the language Low of words acceptable with standard transitions and the language High of words acceptable with all transitions. Alternative semantics is that the automaton describes each language that is a superset of Low and a subset of High. Modal omega-automata can be produced by development versions of tools Seminator and Spot. The goal of this thesis is to explore possibilities for state-space reduction of modal automata based on the concepts of automata pruning and quotienting. More precisely, the author will generalize the concepts of pruning and quotienting to modal omega-automata, define some simulations for these automata, and prove or disprove the correctness of pruning and quotienting based on these simulations. For the correct cases, the author will implement computation of the respective simulations and reductions by pruning and quotienting. The reductions will be experimentally evaluated against reductions by Spot applied to omega-automata without may-transitions and with may-transitions transformed to standard ones.
Práce zkontrolována:
20. 5. 2023 11:31, prof. RNDr. Jan Strejček, Ph.D., učo 3366
Jazyk práce
angličtina angličtina
Termín obhajoby
28. 6. 2023
Práce byla úspěšně obhájena

Vedoucí

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

Oponent

prof. Dr. rer. nat. RNDr. Mgr. Bc. Jan Křetínský, Ph.D., učo 139914
KTP FI MU

Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Informatika
  • 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.