liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Tractability Frontier for Dually-Closed Ord-Horn Quantified Constraint Satisfaction Problems
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
Number of Authors: 1
2014 (English)In: MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2014, PT I, Springer Berlin/Heidelberg, 2014, Vol. 8634, 535-546 p.Conference paper (Refereed)
Abstract [en]

A temporal constraint language is a relational structure with a first-order definition in the rational numbers with the order. We study here the complexity of the Quantified Constraint Satisfaction Problem (QCSP) for Ord-Horn languages: probably the most widely studied family of all temporal constraint languages.

We restrict ourselves to a natural subclass that we call dually-closed Ord-Horn languages. The main result of the paper states that the QCSP for a dually-closed Ord-Horn language is either in P or it is coNP-hard.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2014. Vol. 8634, 535-546 p.
National Category
Computer and Information Science
URN: urn:nbn:se:liu:diva-112901ISI: 000349856300045ISBN: 978-3-662-44522-8; 978-3-662-44521-1OAI: diva2:773647
39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014)
Available from: 2014-12-19 Created: 2014-12-19 Last updated: 2015-03-20

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Wrona, Michal
By organisation
Software and SystemsThe Institute of Technology
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 22 hits
ReferencesLink to record
Permanent link

Direct link