| dc.contributor.author | Chen, Hubert Ming | |
| dc.date.accessioned | 2016-03-03T13:19:24Z | |
| dc.date.available | 2016-03-03T13:19:24Z | |
| dc.date.issued | 2014 | |
| dc.identifier.citation | Logical Methods in Computer Science 10(4) : (2014) // Article ID 14 | es |
| dc.identifier.issn | 1860-5974 | |
| dc.identifier.uri | http://hdl.handle.net/10810/17494 | |
| dc.description.abstract | We consider the quanti fied constraint satisfaction problem (QCSP) which is to decide, given a structure and a first-order sentence (not assumed here to be in prenex form) built from conjunction and quanti fication, whether or not the sentence is true on the structure. We present a proof system for certifying the falsity of QCSP instances and develop its basic theory; for instance, we provide an algorithmic interpretation of its behavior. Our proof system places the established Q-resolution proof system in a broader context, and also allows us to derive QCSP tractability results. | es |
| dc.description.sponsorship | The author thanks Moritz Muller and Friedrich Slivovsky for useful comments. This work was supported by the Spanish project TIN2013-46181-C2-2-R, by the Basque project GIU12/26, and by the Basque grant UFI11/45. | es |
| dc.language.iso | eng | es |
| dc.publisher | Technische Universität Braunschweig, Institute of Theoretical Computer Science | es |
| dc.rights | info:eu-repo/semantics/openAccess | es |
| dc.subject | Q-resolution | es |
| dc.subject | proof system | es |
| dc.subject | quantified constraint satisfaction | es |
| dc.subject | boolean-formulas | es |
| dc.subject | QBFS | es |
| dc.title | Beyond Q-Resolution and Prenex Form: a Proof System for Quantified Constraint Satisfaction | es |
| dc.type | info:eu-repo/semantics/article | es |
| dc.rights.holder | This work is licensed under the Creative Commons Attribution-NoDerivs License. To view
a copy of this license, visit http://creativecommons.org/licenses/by-nd/2.0/ or send a
letter to Creative Commons, 171 Second St, Suite 300, San Francisco, CA 94105, USA, or
Eisenacher Strasse 2, 10777 Berlin, Germany | es |
| dc.relation.publisherversion | http://www.lmcs-online.org/ojs/viewarticle.php?id=1627 | es |
| dc.identifier.doi | 10.2168/LMCS-10(4:14)2014 | |
| dc.departamentoes | Lenguajes y sistemas informáticos | es_ES |
| dc.departamentoeu | Hizkuntza eta sistema informatikoak | es_ES |
| dc.subject.categoria | COMPUTER SCIENCE, MULTIDISCIPLINARY | |
| dc.subject.categoria | THEORETICAL COMPUTER SCIENCE | |
Back