The complexity of temporal constraint satisfaction problems
From MaRDI portal
Recommendations
- Tractable Quantified Constraint Satisfaction Problems over Positive Temporal Templates
- Discrete temporal constraint satisfaction problems
- Quantified Positive Temporal Constraints
- Complexity classification in qualitative temporal constraint reasoning
- The complexity of constraint satisfaction problems (invited talk)
Cited in
(81)- Tractability frontier for dually-closed Ord-Horn quantified constraint satisfaction problems
- Tractability conditions for numeric CSPs
- Tractability of quantified temporal constraints to the max
- Temporal constraints: A survey
- Erdős-Szekeres theorem for multidimensional arrays
- Algebraic approach to approximation
- On classifying continuous constraint satisfaction problems
- On the descriptive complexity of temporal constraint satisfaction problems
- Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
- Tractability in constraint satisfaction problems: a survey
- scientific article; zbMATH DE number 7378350 (Why is no real title available?)
- scientific article; zbMATH DE number 1222101 (Why is no real title available?)
- Enumerating homomorphisms
- A brief history of Timed CSP
- Reconstructing the topology of clones
- Time complexity of constraint satisfaction via universal algebra
- Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
- Computational Short Cuts in Infinite Domain Constraint Satisfaction
- On a stronger reconstruction notion for monoids and clones
- Constants and finite unary relations in qualitative constraint reasoning
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- Tractable combinations of temporal CSPs
- Quantified Constraints in Twenty Seventeen
- Experimental analysis of numeric and symbolic constraint satisfaction techniques for temporal reasoning
- Efficient Temporal Satisfiability
- The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- A complexity dichotomy in spatial reasoning via Ramsey theory
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- Solving infinite-domain CSPs using the patchwork property
- Constraint satisfaction problems over the integers with successor
- Temporal constraint satisfaction problems in fixed-point logic
- Tractable Quantified Constraint Satisfaction Problems over Positive Temporal Templates
- The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
- A dichotomy for first-order reducts of unary structures
- Permutation groups with small orbit growth
- scientific article; zbMATH DE number 7199580 (Why is no real title available?)
- Reducts of the random partial order
- An order out of nowhere: a new algorithm for infinite-domain CSPs
- Discrete geometry. Abstracts from the workshop held January 21--26, 2024
- Exponential Erdős-Szekeres theorem for matrices
- \( \omega \)-categorical structures avoiding height 1 identities
- Constraint satisfaction problems over numeric domains
- Generalized completion problems with forbidden tournaments
- An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
- On Weighted Graph Separation Problems and Flow Augmentation
- Hrushovski's encoding and -categorical CSP monsters
- Complexity classification transfer for CSPs via algebraic products
- Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees
- Robust Approximation of Temporal CSP
- Quantified Positive Temporal Constraints
- When symmetries are not enough: a hierarchy of hard constraint satisfaction problems
- Solving non-linear constraint satisfaction problems involving time-dependent functions
- Temporal induction by incremental SAT solving
- Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
- An algebraic view on p-admissible concrete domains for lightweight description logics
- Parameterized complexity of MinCSP over the point algebra
- Complexity of combinations of qualitative constraint satisfaction problems
- Using model theory to find decidable and tractable description logics with concrete domains
- Smooth approximations and CSPs over finitely bounded homogeneous structures
- The complexity of finding temporal separators under waiting time constraints
- Identifying tractable quantified temporal constraints within Ord-Horn
- Homogeneity and homogenizability: hard problems for the logic SNP
- A logarithmic approximation of linearly-ordered colourings
- The wonderland of reflections
- A topological version of Schaefer's dichotomy theorem
- The language of stratified sets is confluent and strongly normalising
- A complexity dichotomy for poset constraint satisfaction
- A complexity dichotomy for poset constraint satisfaction
- Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
- Parameterised temporal exploration problems
- General lower bounds and improved algorithms for infinite-domain CSPs
- \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's
- Parameterized complexity classification for interval constraints
- Computational complexity of hybrid interval temporal logics
- An initial study of time complexity in infinite-domain constraint satisfaction
- Discrete temporal constraint satisfaction problems
- Complexity classification in qualitative temporal constraint reasoning
- scientific article; zbMATH DE number 7376042 (Why is no real title available?)
- Constraint satisfaction problem: what makes the problem easy
- Constraint satisfaction problems for reducts of homogeneous graphs
This page was built for publication: The complexity of temporal constraint satisfaction problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3578192)
