Zobrazeno 1 - 10
of 18
pro vyhledávání: '"Knäuer, Simon"'
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:
http://arxiv.org/abs/2304.12871
Predicate logic is the premier choice for specifying classes of relational structures. Homomorphisms are key to describing correspondences between relational structures. Questions concerning the interdependencies between these two means of characteri
Externí odkaz:
http://arxiv.org/abs/2104.11955
We characterise the sentences in Monadic Second-order Logic (MSO) that are over finite structures equivalent to a Datalog program, in terms of an existential pebble game. We also show that for every class C of finite structures that can be expressed
Externí odkaz:
http://arxiv.org/abs/2010.05677
The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
Autor:
Bodirsky, Manuel, Knäuer, Simon
Publikováno v:
Journal of Artificial Intelligence Research (JAIR), 75, 2022
Robin Hirsch posed in 1996 the 'Really Big Complexity Problem': classify the computational complexity of the network satisfaction problem for all finite relation algebras A. We provide a complete classification for the case that A is symmetric and ha
Externí odkaz:
http://arxiv.org/abs/2008.11943
Amalgamation SNP (ASNP) is a fragment of existential second-order logic that strictly contains binary connected MMSNP of Feder and Vardi and binary guarded monotone SNP of Bienvenu, ten Cate, Lutz, and Wolter; it is a promising candidate for an expre
Externí odkaz:
http://arxiv.org/abs/2001.08190
Autor:
Bodirsky, Manuel, Knäuer, Simon
We study the computational complexity of the general network satisfaction problem for a finite relation algebra $A$ with a normal representation $B$. If $B$ contains a non-trivial equivalence relation with a finite number of equivalence classes, then
Externí odkaz:
http://arxiv.org/abs/1912.08482
Autor:
Knäuer, Simon
Network satisfaction problems (NSPs) for finite relation algebras are computational decision problems, studied intensively since the 1990s. The major open research challenge in this field is to understand which of these problems are solvable by polyn
Externí odkaz:
https://tud.qucosa.de/id/qucosa%3A85503
https://tud.qucosa.de/api/qucosa%3A85503/attachment/ATT-0/
https://tud.qucosa.de/api/qucosa%3A85503/attachment/ATT-0/
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
We characterise the sentences in Monadic Second-order Logic (MSO) that are over finite structures equivalent to a Datalog program, in terms of an existential pebble game. We also show that for every class C of finite structures that can be expressed
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=sygma_______::bdd9524468c6de3a55af6e23d9d65cfc
https://doi.org/10.4230/lipics.icalp.2021.120
https://doi.org/10.4230/lipics.icalp.2021.120
We characterise the sentences in Monadic Second-order Logic (MSO) that are over finite structures equivalent to a Datalog program, in terms of an existential pebble game. We also show that for every class C of finite structures that can be expressed
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bdd9524468c6de3a55af6e23d9d65cfc