Disertační práce

Structural and Geometric Graph Theory and Algorithmic Metatheorems

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

Základním algoritmickým problémem v teorii konečných modelů je ověřování modelů na relačních strukturách. V současné době se aktivně zkoumá nalezení podtříd grafů, na kterých je ověřování modelů prvního řádu (FO) fixně parametricky tractabilní (FPT), protože ověřování FO modelů na obecných grafech je AW[*]-těžké. Zaměřujeme se na složitost ověřování FO modelů různých tříd průnikových grafů (intervalové …více

Abstract

A fundamental algorithmic problem in finite model theory is model checking on relational structures. A currently active area of research focuses on finding graph subclasses on which first-order (FO) model checking is fixed-parameter tractable (FPT), since FO model checking on general graphs is AW[*]-hard. We focus on the complexity of FO model checking of various intersection graph classes (interval …více

Klíčová slova
FO model checking MSO model checking SAT fixed-parameter tractability twin-width clique-width point configurations
Administrativní informace
Práce zkontrolována:
30. 6. 2024 12:00, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
3,4 MB / soubor PDF
Přílohy (1)
Jazyk práce
angličtina angličtina
Termín obhajoby
8. 11. 2024
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU

Oponenti

Assoc. Prof. O-joung Kwon, Ph.D.
Department of Mathematics, Hanyang University
Assoc. Prof. Michal Pilipczuk, PhD
Institute of Informatics, University of Warsaw
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Fundamenty informatiky

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.