Identifying tractable quantified temporal constraints within Ord-Horn

DOI10.4230/LIPICS.ICALP.2024.151MaRDI QIDQ6875025zbMATH OpenFDO

Authors Jakub Rydval, Žaneta Semanišinová, Michał Wrona

Publication date 14 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2024.151

zbMATH Keywords

constraint satisfaction problemsdichotomyOrd-Hornquantifierstemporal reasoning

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A proof of the CSP dichotomy conjecture
• Complexity of infinite-domain constraint satisfaction
• Datalog and constraint satisfaction with infinite templates
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• On the descriptive complexity of temporal constraint satisfaction problems
• QCSP Monsters and the Demise of the Chen Conjecture
• Quantified Equality Constraints
• Quantified Positive Temporal Constraints
• Reasoning about temporal relations
• Reasoning about temporal relations, the tractable subalgebras of Allen's interval algebra
• The complete classification for quantified equality constraints
• The complexity of equality constraint languages
• The complexity of temporal constraint satisfaction problems
• Theory of computation.
• Tractability frontier for dually-closed Ord-Horn quantified constraint satisfaction problems
• Tractability of quantified temporal constraints to the max
• Tractable Quantified Constraint Satisfaction Problems over Positive Temporal Templates

This page was built for publication: Identifying tractable quantified temporal constraints within Ord-Horn

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875025)