Zobrazeno 1 - 10
of 42
pro vyhledávání: '"Obdrzalek, Jan"'
Autor:
Óbdržálek, Jan
In this thesis we add to the body of work on parity games. We start by presenting parity games and explaining the concepts behind them, giving a survey of known algorithms, and show their relationship to other problems. In the second part of the thes
Externí odkaz:
http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.664254
Autor:
Tušil, Jan, Obdržálek, Jan
Programming language frameworks allow us to generate language tools (e.g., interpreters) just from a formal description of the syntax and semantics of a programming language. As these frameworks tend to be quite complex, an issue arises whether we ca
Externí odkaz:
http://arxiv.org/abs/2409.11530
We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give a structural characterization of the graph classes which are FO interp
Externí odkaz:
http://arxiv.org/abs/1805.01823
Publikováno v:
Logical Methods in Computer Science, Volume 15, Issue 1 (January 31, 2019) lmcs:3798
The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogously useful "depth" notion also for dense graphs (say; one which is stabl
Externí odkaz:
http://arxiv.org/abs/1707.00359
Autor:
Gajarsky, Jakub, Hlineny, Petr, Kaiser, Tomas, Kral, Daniel, Kupec, Martin, Obdrzalek, Jan, Ordyniak, Sebastian, Tuma, Vojtech
Nesetril and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeli
Externí odkaz:
http://arxiv.org/abs/1504.08122
Autor:
Gajarský, Jakub, Hliněný, Petr, Lokshtanov, Daniel, Obdržálek, Jan, Ordyniak, Sebastian, Ramanujan, M. S., Saurabh, Saket
Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classe
Externí odkaz:
http://arxiv.org/abs/1504.04115
Publikováno v:
Logical Methods in Computer Science, Volume 11, Issue 4 (December 11, 2015) lmcs:1609
We prove that the model checking problem for the existential fragment of first-order (FO) logic on partially ordered sets is fixed-parameter tractable (FPT) with respect to the formula and the width of a poset (the maximum size of an antichain). Whil
Externí odkaz:
http://arxiv.org/abs/1409.4433
In a recent paper, Kwon and Oum claim that every graph of bounded rank-width is a pivot-minor of a graph of bounded tree-width (while the converse has been known true already before). We study the analogous questions for "depth" parameters of graphs,
Externí odkaz:
http://arxiv.org/abs/1403.7024
Autor:
Ganian, Robert, Obdržálek, Jan
We combine integer linear programming and recent advances in Monadic Second-Order model checking to obtain two new algorithmic meta-theorems for graphs of bounded vertex-cover. The first shows that cardMSO1, an extension of the well-known Monadic Sec
Externí odkaz:
http://arxiv.org/abs/1306.5571
Autor:
Gajarský, Jakub, Hliněný, Petr, Obdržálek, Jan, Ordyniak, Sebastian, Reidl, Felix, Rossmanith, Peter, Villaamil, Fernando Sánchez, Sikdar, Somnath
Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, meta-theorems for linear kernels exist on graphs of bounded genus, $H$-minor-free graphs, and $H$-topological-minor-fre
Externí odkaz:
http://arxiv.org/abs/1302.6863