The complexity of temporal constraint satisfaction problems
From MaRDI portal
Publication:3578192
DOI10.1145/1667053.1667058zbMath1327.68125OpenAlexW1967190838MaRDI QIDQ3578192
Publication date: 14 July 2010
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.422.896
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
On a stronger reconstruction notion for monoids and clones, Constraint satisfaction and semilinear expansions of addition over the rationals and the reals, Tractability in constraint satisfaction problems: a survey, Constraint Satisfaction Problems over the Integers with Successor, Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic, When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's, Constraint satisfaction problem: what makes the problem easy, Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees, Enumerating homomorphisms, Reconstructing the topology of clones, Solving infinite-domain CSPs using the patchwork property, Unnamed Item, Erdős-Szekeres theorem for multidimensional arrays, On Weighted Graph Separation Problems and Flow Augmentation, Unnamed Item, General lower bounds and improved algorithms for infinite-domain CSPs, The wonderland of reflections, Reducts of the random partial order, Constraint Satisfaction Problems over Numeric Domains, Quantified Constraints in Twenty Seventeen, 𝜔-categorical structures avoiding height 1 identities, An initial study of time complexity in infinite-domain constraint satisfaction, Constants and finite unary relations in qualitative constraint reasoning, Tractability conditions for numeric CSPs, Tractability of quantified temporal constraints to the max, Unnamed Item, Unnamed Item, Permutation groups with small orbit growth, Unnamed Item, Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures, An algebraic view on p-admissible concrete domains for lightweight description logics, Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems), Constraint Satisfaction Problems for Reducts of Homogeneous Graphs, Time Complexity of Constraint Satisfaction via Universal Algebra, A Dichotomy for First-Order Reducts of Unary Structures, Computational complexity of hybrid interval temporal logics, Using model theory to find decidable and tractable description logics with concrete domains, Unnamed Item, Computational Short Cuts in Infinite Domain Constraint Satisfaction, The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom, Distance constraint satisfaction problems
