Network Satisfaction Problems Solved by k-Consistency
Publikation: Vorabdruck/Dokumentation/Bericht › Vorabdruck (Preprint)
Beitragende
Abstract
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 relation algebras A with a normal representation, however, the decidability of this problem remains open. We show that if A is symmetric and has a flexible atom, then the question whether NSP(A) can be solved by k-consistency, for some natural number k, is decidable (even in polynomial time in the number of atoms of A). This result follows from a more general sufficient condition for the correctness of the k-consistency procedure for finite symmetric relation algebras. In our proof we make use of a result of Alexandr Kazda about finite binary conservative structures.
Details
Originalsprache | Englisch |
---|---|
Band | abs/2304.12871 |
Publikationsstatus | Veröffentlicht - 25 Apr. 2023 |
No renderer: customAssociatesEventsRenderPortal,dk.atira.pure.api.shared.model.researchoutput.WorkingPaper
Externe IDs
ArXiv | http://arxiv.org/abs/2304.12871v1 |
---|---|
ORCID | /0000-0001-8228-3611/work/142659299 |
Schlagworte
Schlagwörter
- math.LO, cs.CC, cs.LO, math.RA