Zobrazeno 1 - 10
of 44
pro vyhledávání: '"Theory of computation → Finite Model Theory"'
Autor:
Bodirsky, Manuel, Knäuer, Simon
We show that the problem of deciding for a given finite relation algebra A whether the network satisfaction problem for A can be solved by the k-consistency procedure, for some natural number k, is undecidable. For the important class of finite relat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::22e64d37a071d5c9fa5510bbb5a822e3
http://arxiv.org/abs/2304.12871
http://arxiv.org/abs/2304.12871
Autor:
Hella, Lauri
A generalized quantifier Q_𝒦 is called a CSP-quantifier if its defining class 𝒦 consists of all structures that can be homomorphically mapped to a fixed finite template structure. For all positive integers n ≥ 2 and k, we define a pebble game
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8f02fda176c5c9f3269252d4fc005df3
https://trepo.tuni.fi/handle/10024/147466
https://trepo.tuni.fi/handle/10024/147466
We define the adjacent fragment AF of first-order logic, obtained by restricting the sequences of variables occurring as arguments in atomic formulas. The adjacent fragment generalizes (after a routine renaming) two-variable logic as well as the flut
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::03e8db5b34b2514f45f3148ece199999
Autor:
Grange, Julien
We study the expressive power of the two-variable fragment of order-invariant first-order logic. This logic departs from first-order logic in two ways: first, formulas are only allowed to quantify over two variables. Second, formulas can use an addit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4c9a4ce3081cb878d5a563f07bbb222f
We prove that for any monotone class of finite relational structures, the first-order theory of the class is NIP in the sense of stability theory if, and only if, the collection of Gaifman graphs of structures in this class is nowhere dense. This gen
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7c7ea8ecbc34a58656eb2fe0a7baa7c2
Autor:
Lichter, Moritz
At the core of the quest for a logic for PTime is a mismatch between algorithms making arbitrary choices and isomorphism-invariant logics. One approach to overcome this problem is witnessed symmetric choice. It allows for choices from definable orbit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5aa1507b2531308b26251389219e2251
Autor:
Gajarský, Jakub, Mählmann, Nikolas, McCarty, Rose, Ohlmann, Pierre, Pilipczuk, Michał, Przybyszewski, Wojciech, Siebertz, Sebastian, Sokołowski, Marek, Toruńczyk, Szymon
A class of graphs C is monadically stable if for every unary expansion Ĉ of C, one cannot encode - using first-order transductions - arbitrarily long linear orders in graphs from C. It is known that nowhere dense graph classes are monadically stabl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9a5d5c7dd0528de4b5872108bbe86adb
We use model-theoretic tools originating from stability theory to derive a result we call the Finitary Substitute Lemma, which intuitively says the following. Suppose we work in a stable graph class C, and using a first-order formula {\phi} with para
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8ba08e6397dc273025c13b754a76c661
Monadically stable and monadically NIP classes of structures were initially studied in the context of model theory and defined in logical terms. They have recently attracted attention in the area of structural graph theory, as they generalize notions
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7d102d48b288f3825dc8520cb9b7a29f
We demonstrate some novel links between entropy and description complexity, a notion referring to the minimal formula length for specifying given properties. Let MLU be the logic obtained by extending propositional logic with the universal modality,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::78a08285b4aaed9565a23f7575cf3ae5
http://arxiv.org/abs/2209.12564
http://arxiv.org/abs/2209.12564