Tractability of quantified temporal constraints to the max

DOI10.1142/S0218196714500507zbMath1320.68097arXiv2104.11442MaRDI QIDQ5175605

Michał Wrona, Manuel Bodirsky, Hubie Chen

Publication date: 24 February 2015

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2104.11442

zbMATH Keywords

constraint satisfaction problemsmax-closed constraintsquantified constraint satisfactionhighly set-transitive structurestemporal constraint languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Related Items (2)

Quantified Constraints in Twenty Seventeen ⋮ Unnamed Item

Cites Work

• Unnamed Item
• The complexity of constraint satisfaction games and QCSP
• Relatively quantified constraint satisfaction
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A survey of homogeneous structures
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Meditations on Quantified Constraint Satisfaction
• A fast algorithm and datalog inexpressibility for temporal reasoning
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• The complexity of temporal constraint satisfaction problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Quantified Equality Constraints
• Tractable Quantified Constraint Satisfaction Problems over Positive Temporal Templates
• Tractable constraints on ordered domains

This page was built for publication: Tractability of quantified temporal constraints to the max