Zobrazeno 1 - 10
of 69
pro vyhledávání: '"Dreier, Jan"'
A conjecture in algorithmic model theory predicts that the model-checking problem for first-order logic is fixed-parameter tractable on a hereditary graph class if and only if the class is monadically dependent. Originating in model theory, this noti
Externí odkaz:
http://arxiv.org/abs/2403.15201
It is known that first-order logic with some counting extensions can be efficiently evaluated on graph classes with bounded expansion, where depth-$r$ minors have constant density. More precisely, the formulas are $\exists x_1 ... x_k \#y \varphi(x_1
Externí odkaz:
http://arxiv.org/abs/2307.01832
Courcelle's theorem and its adaptations to cliquewidth have shaped the field of exact parameterized algorithms and are widely considered the archetype of algorithmic meta-theorems. In the past decade, there has been growing interest in developing par
Externí odkaz:
http://arxiv.org/abs/2305.02056
Autor:
Dreier, Jan, Tucker-Foltz, Jamie
We study pseudorandomness and pseudorandom generators from the perspective of logical definability. Building on results from ordinary derandomization and finite model theory, we show that it is possible to deterministically construct, in polynomial t
Externí odkaz:
http://arxiv.org/abs/2304.12109
A class of graphs is structurally nowhere dense if it can be constructed from a nowhere dense class by a first-order transduction. Structurally nowhere dense classes vastly generalize nowhere dense classes and constitute important examples of monadic
Externí odkaz:
http://arxiv.org/abs/2302.03527
Nowhere dense classes of graphs are classes of sparse graphs with rich structural and algorithmic properties, however, they fail to capture even simple classes of dense graphs. Monadically stable classes, originating from model theory, generalize now
Externí odkaz:
http://arxiv.org/abs/2206.14509
An indiscernible sequence $(\bar a_i)_{1\leq i\leq n}$ in a structure is an ordered sequence of tuples of elements which is very homogeneous in the sense that any two finite subsequences of the same length satisfy the same first-order formulas. We pr
Externí odkaz:
http://arxiv.org/abs/2206.13765
We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints ($\mathsf{A\&C~DN}$ for short) which extends existential $\mathsf{MSO_1}$ with predicates for querying neighborhoods of vertex sets and for verifying
Externí odkaz:
http://arxiv.org/abs/2202.13335
Autor:
Bonnet, Édouard, Dreier, Jan, Gajarský, Jakub, Kreutzer, Stephan, Mählmann, Nikolas, Simon, Pierre, Toruńczyk, Szymon
We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local cliquewidth. Notably, this includes interpretations of planar graphs, and more generally, of classes of bounded gen
Externí odkaz:
http://arxiv.org/abs/2202.13014
For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the linear-time tractability of Horn formulas (Aspvall, Plass, and Tarjan, 1979) and Kr
Externí odkaz:
http://arxiv.org/abs/2202.08326