A Characterisation of First-Order Constraint Satisfaction Problems

We characterise finite relational core structures admitting finitely many obstructions, in terms of special near unanimity functions, and in terms of dismantling properties of their square. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first...

Full description

Saved in:
Bibliographic Details
Main Authors: Larose, B., Loten, C., Tardif, C.
Format: Conference Proceeding
Language:English
Subjects:
Character recognition
Combinatorial mathematics
Computer science
Constraint theory
Educational institutions
Graph theory
Logic
Polynomials
Relational databases
Statistics
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 210
container_issue
container_start_page 201
container_title
container_volume
creator Larose, B.
Loten, C.
Tardif, C.
description We characterise finite relational core structures admitting finitely many obstructions, in terms of special near unanimity functions, and in terms of dismantling properties of their square. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores
doi_str_mv 10.1109/LICS.2006.6
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_1691231</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>1691231</ieee_id><sourcerecordid>1691231</sourcerecordid><originalsourceid>FETCH-LOGICAL-i175t-9f7591440151529c509fa6c9bbf66dc503c42dba913c554567a111e8f6ff648e3</originalsourceid><addsrcrecordid>eNotzE1LxDAUheHgBziMXbl00z_Qmpvk3iTLsTg6UBhhdD2kbYKRmVaSbvz3VnR1eOHhMHYHvAbg9qHdNYdacE41XbCVQI0VojCXrLDacE0WBUnQV2wFXMmKjIYbVuT8yTkHSwa1WbHHTdl8uOT62aeY3RynsZxCuY0pz9U-DT6VzTTmObk4zuVhATks-Je9pqk7-XO-ZdfBnbIv_nfN3rdPb81L1e6fd82mrSJonCsbNFpQigMCCtsjt8FRb7suEA1Lyl6JoXMWZI-okLQDAG8ChUDKeLlm93-_0Xt__Erx7NL3EciCkCB_AM_DSx0</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>A Characterisation of First-Order Constraint Satisfaction Problems</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Larose, B. ; Loten, C. ; Tardif, C.</creator><creatorcontrib>Larose, B. ; Loten, C. ; Tardif, C.</creatorcontrib><description>We characterise finite relational core structures admitting finitely many obstructions, in terms of special near unanimity functions, and in terms of dismantling properties of their square. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores</description><identifier>ISSN: 1043-6871</identifier><identifier>ISBN: 9780769526317</identifier><identifier>ISBN: 0769526314</identifier><identifier>EISSN: 2575-5528</identifier><identifier>DOI: 10.1109/LICS.2006.6</identifier><language>eng</language><publisher>IEEE</publisher><subject>Character recognition ; Combinatorial mathematics ; Computer science ; Constraint theory ; Educational institutions ; Graph theory ; Logic ; Polynomials ; Relational databases ; Statistics</subject><ispartof>21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006, p.201-210</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/1691231$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2056,4048,4049,27924,54554,54919,54931</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/1691231$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Larose, B.</creatorcontrib><creatorcontrib>Loten, C.</creatorcontrib><creatorcontrib>Tardif, C.</creatorcontrib><title>A Characterisation of First-Order Constraint Satisfaction Problems</title><title>21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)</title><addtitle>LICS</addtitle><description>We characterise finite relational core structures admitting finitely many obstructions, in terms of special near unanimity functions, and in terms of dismantling properties of their square. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores</description><subject>Character recognition</subject><subject>Combinatorial mathematics</subject><subject>Computer science</subject><subject>Constraint theory</subject><subject>Educational institutions</subject><subject>Graph theory</subject><subject>Logic</subject><subject>Polynomials</subject><subject>Relational databases</subject><subject>Statistics</subject><issn>1043-6871</issn><issn>2575-5528</issn><isbn>9780769526317</isbn><isbn>0769526314</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2006</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotzE1LxDAUheHgBziMXbl00z_Qmpvk3iTLsTg6UBhhdD2kbYKRmVaSbvz3VnR1eOHhMHYHvAbg9qHdNYdacE41XbCVQI0VojCXrLDacE0WBUnQV2wFXMmKjIYbVuT8yTkHSwa1WbHHTdl8uOT62aeY3RynsZxCuY0pz9U-DT6VzTTmObk4zuVhATks-Je9pqk7-XO-ZdfBnbIv_nfN3rdPb81L1e6fd82mrSJonCsbNFpQigMCCtsjt8FRb7suEA1Lyl6JoXMWZI-okLQDAG8ChUDKeLlm93-_0Xt__Erx7NL3EciCkCB_AM_DSx0</recordid><startdate>2006</startdate><enddate>2006</enddate><creator>Larose, B.</creator><creator>Loten, C.</creator><creator>Tardif, C.</creator><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope></search><sort><creationdate>2006</creationdate><title>A Characterisation of First-Order Constraint Satisfaction Problems</title><author>Larose, B. ; Loten, C. ; Tardif, C.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i175t-9f7591440151529c509fa6c9bbf66dc503c42dba913c554567a111e8f6ff648e3</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2006</creationdate><topic>Character recognition</topic><topic>Combinatorial mathematics</topic><topic>Computer science</topic><topic>Constraint theory</topic><topic>Educational institutions</topic><topic>Graph theory</topic><topic>Logic</topic><topic>Polynomials</topic><topic>Relational databases</topic><topic>Statistics</topic><toplevel>online_resources</toplevel><creatorcontrib>Larose, B.</creatorcontrib><creatorcontrib>Loten, C.</creatorcontrib><creatorcontrib>Tardif, C.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE Xplore</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Larose, B.</au><au>Loten, C.</au><au>Tardif, C.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>A Characterisation of First-Order Constraint Satisfaction Problems</atitle><btitle>21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)</btitle><stitle>LICS</stitle><date>2006</date><risdate>2006</risdate><spage>201</spage><epage>210</epage><pages>201-210</pages><issn>1043-6871</issn><eissn>2575-5528</eissn><isbn>9780769526317</isbn><isbn>0769526314</isbn><abstract>We characterise finite relational core structures admitting finitely many obstructions, in terms of special near unanimity functions, and in terms of dismantling properties of their square. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores</abstract><pub>IEEE</pub><doi>10.1109/LICS.2006.6</doi><tpages>10</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 1043-6871
ispartof 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006, p.201-210
issn 1043-6871
2575-5528
language eng
recordid cdi_ieee_primary_1691231
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Character recognition
Combinatorial mathematics
Computer science
Constraint theory
Educational institutions
Graph theory
Logic
Polynomials
Relational databases
Statistics
title A Characterisation of First-Order Constraint Satisfaction Problems
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-10T09%3A25%3A41IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=A%20Characterisation%20of%20First-Order%20Constraint%20Satisfaction%20Problems&rft.btitle=21st%20Annual%20IEEE%20Symposium%20on%20Logic%20in%20Computer%20Science%20(LICS'06)&rft.au=Larose,%20B.&rft.date=2006&rft.spage=201&rft.epage=210&rft.pages=201-210&rft.issn=1043-6871&rft.eissn=2575-5528&rft.isbn=9780769526317&rft.isbn_list=0769526314&rft_id=info:doi/10.1109/LICS.2006.6&rft_dat=%3Cieee_6IE%3E1691231%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i175t-9f7591440151529c509fa6c9bbf66dc503c42dba913c554567a111e8f6ff648e3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=1691231&rfr_iscdi=true