Diplomová práce

Straubingova-Thérienova hierarchie jazyků

Straubing-Thérien hierarchy of star-free languages

Bc. Jana Bartoňová
Anotace

Tato diplomová práce se zabývá jednou z tzv. zřetězovacích hierarchií star-free jazyků - Straubingovou-Thérienovou hierarchií. Je zaměřena především na seznámení s prostředky, které byly použity při charakterizaci stupňů 5/2, 2 a 7/2 této hierarchie. Hlavním zkoumaným nástrojem je speciální typ Ehrenfeuchtových-Fraissého her.

Abstract

In this thesis we study one of so-called concatenation hierarchies of star-free languages - Straubing-Thérien hierarchy. The thesis is aimed primarily at investigating tools which were used to obtain decidable characterizations of levels 5/2, 2, and 7/2 of this hierarchy. The main examined tool is a special type of Ehrenfeucht-Fraissé games.

Klíčová slova
monoid uspořádaný monoid star-free jazyk predikátová logika hierarchie ordered monoid star-free language first-order logic hierarchy
Zadání práce
Téma patří do algebraické teorie regulárních jazyků. Straubinova-Thérienova hierarchie je analogií tzv. dot-depth hierarchie star-free jazyků. Pouze několik málo úrovní této hierarchie má efektivní charakterizaci. Kromě první úrovně charakterizované Simonem je to především úroveň 3/2, kde se při charakterizaci použil netriviální Factorization Forest Theorem. V dalších dílčích výsledcích o této hierarchii se požívají zejména profinitní metody konečné teorie pologrup. Studentka zpracuje přehled známých výsledků včetně vybraných důkazů.
Administrativní informace
Práce zkontrolována:
18. 5. 2015 08:23, doc. Mgr. Ondřej Klíma, Ph.D., učo 3868
Plný text práce
576,7 KB / soubor PDF
Jazyk práce
čeština čeština
Termín obhajoby
16. 6. 2015
Práce byla úspěšně obhájena

Vedoucí

doc. Mgr. Ondřej Klíma, Ph.D., učo 3868
ÚMS Ústavy PřF MU

Oponent

doc. Mgr. Michal Kunc, Ph.D., učo 2906
ÚMS Ústavy PřF MU

Literatura

  • ALMEIDA, Jorge. Finite semigroups and universal algebra. Singapore: World Scientific, 1994, xvi, 511 s. ISBN 981-02-1895-8.
  • PIN, J.-E. a H. STRAUBING. Monoids of upper triangular boolean matrices. 1981, s. 259-272.
  • PIN, J.-E. Algebraic tools for the concatenation product. Theoretical Computer Science. 2003, roč. 292/2003, s. 317-342.
  • KLÍMA, Ondřej a Jorge ALMEIDA. A counterexample to a conjecture concerning concatenation hierarchies. Information Processing Letters. Elsevier, 2009, roč. 110, č. 1, s. 4 - 7. ISSN 0020-0190.
Citovat tuto práci
Masarykova univerzita Přírodovědecká fakulta
Studijní program
Matematika
Obor

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

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

Podobné práce
 
Název
Vložil
Vloženo
Práva
Archiv závěrečné práce Jana Bartoňová PřF N-MA ALG mv6cm/6
Mitášová, I.
27. 11. 2013
Složky
Soubory
Anotace anglicky annotation_english.txt
Bartoňová, J.
13. 5. 2015
Anotace česky annotation.txt
Bartoňová, J.
13. 5. 2015
Klíčová slova keywords.txt
Bartoňová, J.
13. 5. 2015
Plný text práce Diplomka.pdf
Bartoňová, J.
13. 5. 2015
Posudek oponenta Bartonova15.pdf
Kunc, M.
10. 6. 2015
Posudek vedoucího bartonova-cer15.pdf
Klíma, O.
6. 6. 2015

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