No Cover Image

Journal article 1092 views

Constraint satisfaction problems in clausal form I: Autarkies and deficiency.

Oliver Kullmann Orcid Logo

Fundamenta Informaticae, Volume: 109, Issue: 1, Pages: 27 - 81

Swansea University Author: Oliver Kullmann Orcid Logo

Full text not available from this repository: check for access using links below.

Check full text

DOI (Published version): 10.3233/FI-2011-428

Abstract

We consider the problem of generalising boolean formulas in conjunctive normal form by allowing non-boolean variables, with the goal of maintaining combinatorial properties. Requiring that a literal involves only a single variable, the most general form of literals are the wellknown “signed literals...

Full description

Published in: Fundamenta Informaticae
ISSN: 0169-2968
Published: 2011
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa5283
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2013-07-23T11:52:11Z
last_indexed 2018-02-09T04:31:28Z
id cronfa5283
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2015-10-15T10:19:13.0549929</datestamp><bib-version>v2</bib-version><id>5283</id><entry>2012-02-23</entry><title>Constraint satisfaction problems in clausal form I: Autarkies and deficiency.</title><swanseaauthors><author><sid>2b410f26f9324d6b06c2b98f67362d05</sid><ORCID>0000-0003-3021-0095</ORCID><firstname>Oliver</firstname><surname>Kullmann</surname><name>Oliver Kullmann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2012-02-23</date><deptcode>SCS</deptcode><abstract>We consider the problem of generalising boolean formulas in conjunctive normal form by allowing non-boolean variables, with the goal of maintaining combinatorial properties. Requiring that a literal involves only a single variable, the most general form of literals are the wellknown &#x201C;signed literals&#x201D;, corresponding to unary constraints in CSP. However we argue that only the restricted form of &#x201C;negative monosigned literals&#x201D; and the resulting generalised clause-sets, corresponding to &#x201C;sets of no-goods&#x201D; in the AI literature, maintain the essential properties of boolean conjunctive normal forms. In this first part of a mini-series of two articles, we build up a solid foundation for (generalised) clause-sets, including the notion of autarky systems, the interplay between autarkies and resolution, and basic notions of (DP-)reductions. As a basic combinatorial parameter of generalised clause-sets we introduce the (generalised) notion of deficiency, which in the boolean case is the difference between the number of clauses and the number of variables. Autarky theory plays a fundamental role here, and we concentrate especially on matching autarkies (based on matching theory). A natural task is to determine the structure of (matching) lean clause-sets, which do not admit non-trivial (matching) autarkies. A central result is the computation of the lean kernel (the largest lean subset) of a (generalised) clause-set in polynomial time for bounded maximal deficiency.</abstract><type>Journal Article</type><journal>Fundamenta Informaticae</journal><volume>109</volume><journalNumber>1</journalNumber><paginationStart>27</paginationStart><paginationEnd>81</paginationEnd><publisher/><issnPrint>0169-2968</issnPrint><issnElectronic/><keywords/><publishedDay>22</publishedDay><publishedMonth>9</publishedMonth><publishedYear>2011</publishedYear><publishedDate>2011-09-22</publishedDate><doi>10.3233/FI-2011-428</doi><url>http://www.cs.swan.ac.uk/~csoliver/papers.html#ClausalFormI</url><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2015-10-15T10:19:13.0549929</lastEdited><Created>2012-02-23T17:01:57.0000000</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Oliver</firstname><surname>Kullmann</surname><orcid>0000-0003-3021-0095</orcid><order>1</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2015-10-15T10:19:13.0549929 v2 5283 2012-02-23 Constraint satisfaction problems in clausal form I: Autarkies and deficiency. 2b410f26f9324d6b06c2b98f67362d05 0000-0003-3021-0095 Oliver Kullmann Oliver Kullmann true false 2012-02-23 SCS We consider the problem of generalising boolean formulas in conjunctive normal form by allowing non-boolean variables, with the goal of maintaining combinatorial properties. Requiring that a literal involves only a single variable, the most general form of literals are the wellknown “signed literals”, corresponding to unary constraints in CSP. However we argue that only the restricted form of “negative monosigned literals” and the resulting generalised clause-sets, corresponding to “sets of no-goods” in the AI literature, maintain the essential properties of boolean conjunctive normal forms. In this first part of a mini-series of two articles, we build up a solid foundation for (generalised) clause-sets, including the notion of autarky systems, the interplay between autarkies and resolution, and basic notions of (DP-)reductions. As a basic combinatorial parameter of generalised clause-sets we introduce the (generalised) notion of deficiency, which in the boolean case is the difference between the number of clauses and the number of variables. Autarky theory plays a fundamental role here, and we concentrate especially on matching autarkies (based on matching theory). A natural task is to determine the structure of (matching) lean clause-sets, which do not admit non-trivial (matching) autarkies. A central result is the computation of the lean kernel (the largest lean subset) of a (generalised) clause-set in polynomial time for bounded maximal deficiency. Journal Article Fundamenta Informaticae 109 1 27 81 0169-2968 22 9 2011 2011-09-22 10.3233/FI-2011-428 http://www.cs.swan.ac.uk/~csoliver/papers.html#ClausalFormI COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2015-10-15T10:19:13.0549929 2012-02-23T17:01:57.0000000 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Oliver Kullmann 0000-0003-3021-0095 1
title Constraint satisfaction problems in clausal form I: Autarkies and deficiency.
spellingShingle Constraint satisfaction problems in clausal form I: Autarkies and deficiency.
Oliver Kullmann
title_short Constraint satisfaction problems in clausal form I: Autarkies and deficiency.
title_full Constraint satisfaction problems in clausal form I: Autarkies and deficiency.
title_fullStr Constraint satisfaction problems in clausal form I: Autarkies and deficiency.
title_full_unstemmed Constraint satisfaction problems in clausal form I: Autarkies and deficiency.
title_sort Constraint satisfaction problems in clausal form I: Autarkies and deficiency.
author_id_str_mv 2b410f26f9324d6b06c2b98f67362d05
author_id_fullname_str_mv 2b410f26f9324d6b06c2b98f67362d05_***_Oliver Kullmann
author Oliver Kullmann
author2 Oliver Kullmann
format Journal article
container_title Fundamenta Informaticae
container_volume 109
container_issue 1
container_start_page 27
publishDate 2011
institution Swansea University
issn 0169-2968
doi_str_mv 10.3233/FI-2011-428
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
url http://www.cs.swan.ac.uk/~csoliver/papers.html#ClausalFormI
document_store_str 0
active_str 0
description We consider the problem of generalising boolean formulas in conjunctive normal form by allowing non-boolean variables, with the goal of maintaining combinatorial properties. Requiring that a literal involves only a single variable, the most general form of literals are the wellknown “signed literals”, corresponding to unary constraints in CSP. However we argue that only the restricted form of “negative monosigned literals” and the resulting generalised clause-sets, corresponding to “sets of no-goods” in the AI literature, maintain the essential properties of boolean conjunctive normal forms. In this first part of a mini-series of two articles, we build up a solid foundation for (generalised) clause-sets, including the notion of autarky systems, the interplay between autarkies and resolution, and basic notions of (DP-)reductions. As a basic combinatorial parameter of generalised clause-sets we introduce the (generalised) notion of deficiency, which in the boolean case is the difference between the number of clauses and the number of variables. Autarky theory plays a fundamental role here, and we concentrate especially on matching autarkies (based on matching theory). A natural task is to determine the structure of (matching) lean clause-sets, which do not admit non-trivial (matching) autarkies. A central result is the computation of the lean kernel (the largest lean subset) of a (generalised) clause-set in polynomial time for bounded maximal deficiency.
published_date 2011-09-22T03:06:20Z
_version_ 1763749690276315136
score 11.014067

Similar Items