File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Algorithms for quantified constraint satisfaction problems

TitleAlgorithms for quantified constraint satisfaction problems
Authors
Issue Date2004
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3258, p. 752-756 How to Cite?
AbstractMany propagation and search algorithms have been developed for constraint satisfaction problems (CSPs). In a standard CSP all variables are existentially quantified. The CSP formalism can be extended to allow universally quantified variables, in which case the complexity of the basic reasoning tasks rises from NP-complete to PSPACE-complete. Such problems have, so far, been studied mainly in the context of quantified Boolean formulae. Little work has been done on problems with discrete non-Boolean domains. We attempt to fill this gap by extending propagation and search algorithms from standard CSPs to the quantified case. We also show how the notion of value interchangeability can be exploited to break symmetries and speed up search by orders of magnitude. Finally, we test experimentally the algorithms and methods proposed. © Springer-Verlag Berlin Heidelberg 2004.
Persistent Identifierhttp://hdl.handle.net/10722/93257
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorMamoulis, Nen_HK
dc.contributor.authorStergiou, Ken_HK
dc.date.accessioned2010-09-25T14:55:38Z-
dc.date.available2010-09-25T14:55:38Z-
dc.date.issued2004en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3258, p. 752-756en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93257-
dc.description.abstractMany propagation and search algorithms have been developed for constraint satisfaction problems (CSPs). In a standard CSP all variables are existentially quantified. The CSP formalism can be extended to allow universally quantified variables, in which case the complexity of the basic reasoning tasks rises from NP-complete to PSPACE-complete. Such problems have, so far, been studied mainly in the context of quantified Boolean formulae. Little work has been done on problems with discrete non-Boolean domains. We attempt to fill this gap by extending propagation and search algorithms from standard CSPs to the quantified case. We also show how the notion of value interchangeability can be exploited to break symmetries and speed up search by orders of magnitude. Finally, we test experimentally the algorithms and methods proposed. © Springer-Verlag Berlin Heidelberg 2004.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleAlgorithms for quantified constraint satisfaction problemsen_HK
dc.typeArticleen_HK
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_HK
dc.identifier.authorityMamoulis, N=rp00155en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-33750291991en_HK
dc.identifier.hkuros103372en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33750291991&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3258en_HK
dc.identifier.spage752en_HK
dc.identifier.epage756en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridMamoulis, N=6701782749en_HK
dc.identifier.scopusauthoridStergiou, K=35575234700en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats