Solving infinite-domain CSPs using the patchwork property
From MaRDI portal
Publication:6157211
DOI10.1016/j.artint.2023.103880arXiv2107.01428OpenAlexW3176144513MaRDI QIDQ6157211
Sebastian Ordyniak, Konrad K. Dabrowski, George Osipov, Peter Jonsson
Publication date: 19 June 2023
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2107.01428
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maintaining knowledge about temporal intervals
- Homogenizable structures and model completeness
- Decomposition and tractability in qualitative spatial and temporal reasoning
- Fundamentals of parameterized complexity
- Graph minors. III. Planar tree-width
- Point algebras for temporal reasoning: Algorithms and complexity
- Constraint satisfaction with bounded treewidth revisited
- A tableau algorithm for description logics with concrete domains and general TBoxes
- Homogenizable relational structures
- Temporal constraint networks
- The complexity of reconstructing trees from qualitative characters and subtrees
- Reasoning about partially ordered events
- On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
- Satisfiability problems on intervals and unit intervals
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Which problems have strongly exponential complexity?
- Constants and finite unary relations in qualitative constraint reasoning
- Datalog and constraint satisfaction with infinite templates
- The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees
- Branching interval algebra: an almost complete picture
- Description logics with concrete domains and general concept inclusions revisited
- Relation algebras of intervals
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- A survey of homogeneous structures
- Parametrized complexity theory.
- Nonserial dynamic programming
- Graph Theory
- Extension Properties of Boolean Contact Algebras
- A Model-Theoretic View on Qualitative Constraint Reasoning
- Complexity of Infinite-Domain Constraint Satisfaction
- Non-dichotomies in Constraint Satisfaction Complexity
- The complexity of temporal constraint satisfaction problems
- Complexity of Finding Embeddings in a k-Tree
- “Sometimes” and “not never” revisited
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
- Expressive power and complexity in algebraic logic
- Reasoning about temporal relations
- Computational Phylogenetics
- Scheduling with AND/OR Precedence Constraints
- Constraint Satisfaction Problems on Intervals and Lengths
- The universal homogeneous binary tree
- Tractability Results in the Block Algebra
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- A Proof of the CSP Dichotomy Conjecture
- Complexities of Relational Structures
- Non-Homogenizable Classes of Finite Structures
- The Complexity of Phylogeny Constraint Satisfaction Problems
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Slightly Superexponential Parameterized Problems
- The mutual exclusion problem
- Recursive conditioning
