Rigorózní práce

Structural and geometric graph theory and algorithmic metatheorems

Mgr. Filip Pokrývka, učo 433705
Anotace

Základným problémom v teórií konečných modelov je problém overovania vlastností relačných štruktúr. V súčastnosti sa výskum sústredí na hľadanie podtried grafov, na ktorých je problém overovania vlastností definovaných logikou prvého rádu (FO) parametrizovateľný (FPT), pretože vo všeobecnosti je tento ptoblém AW[*]-úplný. Táto téza sa sústredí na problém overovania FO vlastností na grafoch, ktoré …více

Abstract

A fundamental problem in finite model theory is model checking on relational structures. The current main points of research focus on finding subclasses of graphs on which first-order (FO) model checking is fixed-parameter tractable (FPT), since FO model checking on general graphs is AW[*]-complete. This thesis proposal focuses on the complexity of FO model checking on graphs with geometrical representation …více

Klíčová slova
first-order model checking intersection graphs fixed-paramerer tractability FPT twin-width clique-width order type of point configurations
Administrativní informace
Práce zkontrolována:
25. 9. 2021 17:35, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
728,5 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
18. 1. 2022
Práce byla úspěšně obhájena

Oponenti

Dr. rer. nat. Achim Blumensath, učo 237782
KTP FI MU
Maria Saumell Mendiola, M.Sc., Ph.D.
FIT ČVUT v Praze
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Teoretická 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.