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

Minimality problems for promise versions of finite automata

Michal Ajdarów
Anotace

Tato práce se zabývá několika problémy týkající se minimality promise verze deterministického konečného automatu (pvDFA) vzhledem ke dvěma různým módům akceptování. Dokážeme jednoznačnost minimálního pvDFA pracujícího v rozhodujícím módu, a navrhneme nový algoritmus pro jeho minimalizaci. Poté ukážeme, že minimální pvDFA řešící daný promise problém není určen jednoznačně. Popíšeme algoritmy na zjištění …více

Abstract

In this paper we explore several minimality problems concerning promise version deterministic finite automata (pvDFA) with respect to two different modes of acceptance. In particular, we prove that the minimal pvDFA recognizing a promise problem is determined uniquely, and design a new algorithm for finding this minimal pvDFA. We then show that a minimal pvDFA solving a promise problem is not determined …více

Klíčová slova
Promise problems Finite automata Minimization Recognizability Solvability
Zadání práce
The task is to explore minimality issue, especially the uniqueness of minimal designs, for promise versions of finite deterministic automata, with respect to two modes of recognition.
Administrativní informace
Práce zkontrolována:
31. 5. 2016 12:35, prof. RNDr. Jozef Gruska, DrSc.
Plný text práce
593,1 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
20. 6. 2016
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Jozef Gruska, DrSc.
KTP FI MU

Oponent

RNDr. Matej Pivoluska, Ph.D.
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.