2015-10
AUTHORSAchref El Mouelhi, Philippe Jégou, Cyril Terrioux
ABSTRACTFind new islands of tractability, that is classes of CSP instances for which polytime algorithms exist, is a fundamental task in the study of constraint satisfaction problems. The concept of hybrid tractable class, which allows to deal simultaneously with the restrictions of languages and, for example, the satisfaction of structural properties, is an approach which has already shown its interest in this domain. Here we study a hybrid class for non-binary CSP instances. With this aim in view, we consider the Broken Triangle Property (BTP) introduced in Cooper et al. (Artificial Intelligence, 174, 570–584 2010). While this tractable class has been defined for binary instances, the authors have suggested to extend it to instances with constraints of arbitrary arities, using the dual representation of such CSPs. We develop this idea by proposing a new definition without exploiting the dual representation, but using a semantic property associated to the compatibility relations of the constraints. This class is called DBTP for Dual Broken Triangle Property. We study it in depth, firstly to show that it is tractable. Then we compare it to some known classes. In particular, we prove that DBTP is incomparable with BTP and that it includes some well known tractable classes of CSPs such as β-acyclic CSPs. Then, we compare it with the Hyper-k-Consistency, which allows us to also present new results for BTP. Finally, we analyse DBTP from a practical viewpoint, by first highlighting that some benchmarks which are classically used to compare the solvers are included in DBTP and then by explaining the efficiency of solvers of the state of the art on such instances thanks to their membership of the DBTP class. More... »
PAGES383-413
http://scigraph.springernature.com/pub.10.1007/s10601-015-9185-y
DOIhttp://dx.doi.org/10.1007/s10601-015-9185-y
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1017742435
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Aix-Marseille University",
"id": "https://www.grid.ac/institutes/grid.5399.6",
"name": [
"LSIS UMR 7296, Aix-Marseille Universit\u00e9, CNRS, ENSAM, Universit\u00e9 de Toulon, 13397, Marseille, France"
],
"type": "Organization"
},
"familyName": "El Mouelhi",
"givenName": "Achref",
"id": "sg:person.013774213003.86",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013774213003.86"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Aix-Marseille University",
"id": "https://www.grid.ac/institutes/grid.5399.6",
"name": [
"LSIS UMR 7296, Aix-Marseille Universit\u00e9, CNRS, ENSAM, Universit\u00e9 de Toulon, 13397, Marseille, France"
],
"type": "Organization"
},
"familyName": "J\u00e9gou",
"givenName": "Philippe",
"id": "sg:person.01255044273.53",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01255044273.53"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Aix-Marseille University",
"id": "https://www.grid.ac/institutes/grid.5399.6",
"name": [
"LSIS UMR 7296, Aix-Marseille Universit\u00e9, CNRS, ENSAM, Universit\u00e9 de Toulon, 13397, Marseille, France"
],
"type": "Organization"
},
"familyName": "Terrioux",
"givenName": "Cyril",
"id": "sg:person.014232365062.45",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014232365062.45"
],
"type": "Person"
}
],
"citation": [
{
"id": "https://doi.org/10.1016/0004-3702(95)00107-7",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006761391"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-23786-7_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007535280",
"https://doi.org/10.1007/978-3-642-23786-7_14"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-23786-7_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007535280",
"https://doi.org/10.1007/978-3-642-23786-7_14"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-38171-3_5",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018820029",
"https://doi.org/10.1007/978-3-642-38171-3_5"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.artint.2010.03.002",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1020699779"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0196-6774(86)90023-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1021500239"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4613-8788-6_9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1023111840",
"https://doi.org/10.1007/978-1-4613-8788-6_9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-58601-6_86",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026133979",
"https://doi.org/10.1007/3-540-58601-6_86"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2402.322389",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027593069"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0004-3702(94)90021-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033682903"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0004-3702(94)90021-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1033682903"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.ipl.2012.05.005",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037650527"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-85958-1_35",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041159679",
"https://doi.org/10.1007/978-3-540-85958-1_35"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-85958-1_35",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041159679",
"https://doi.org/10.1007/978-3-540-85958-1_35"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/322290.322292",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1042825214"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2402.322390",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1044132642"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s1574-6526(06)80007-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1045077828"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/210346.210347",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1045651250"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.artint.2007.10.016",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053162424"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/0201013",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062841176"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tai.1989.65349",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1086170535"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/ictai.2014.73",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1094203319"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/ictai.2013.144",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095157122"
],
"type": "CreativeWork"
}
],
"datePublished": "2015-10",
"datePublishedReg": "2015-10-01",
"description": "Find new islands of tractability, that is classes of CSP instances for which polytime algorithms exist, is a fundamental task in the study of constraint satisfaction problems. The concept of hybrid tractable class, which allows to deal simultaneously with the restrictions of languages and, for example, the satisfaction of structural properties, is an approach which has already shown its interest in this domain. Here we study a hybrid class for non-binary CSP instances. With this aim in view, we consider the Broken Triangle Property (BTP) introduced in Cooper et al. (Artificial Intelligence, 174, 570\u2013584 2010). While this tractable class has been defined for binary instances, the authors have suggested to extend it to instances with constraints of arbitrary arities, using the dual representation of such CSPs. We develop this idea by proposing a new definition without exploiting the dual representation, but using a semantic property associated to the compatibility relations of the constraints. This class is called DBTP for Dual Broken Triangle Property. We study it in depth, firstly to show that it is tractable. Then we compare it to some known classes. In particular, we prove that DBTP is incomparable with BTP and that it includes some well known tractable classes of CSPs such as \u03b2-acyclic CSPs. Then, we compare it with the Hyper-k-Consistency, which allows us to also present new results for BTP. Finally, we analyse DBTP from a practical viewpoint, by first highlighting that some benchmarks which are classically used to compare the solvers are included in DBTP and then by explaining the efficiency of solvers of the state of the art on such instances thanks to their membership of the DBTP class.",
"genre": "research_article",
"id": "sg:pub.10.1007/s10601-015-9185-y",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1043977",
"issn": [
"1383-7133",
"1572-9354"
],
"name": "Constraints",
"type": "Periodical"
},
{
"issueNumber": "4",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "20"
}
],
"name": "A hybrid tractable class for non-binary CSPs",
"pagination": "383-413",
"productId": [
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"54896007275c0bf810e0f6096c6f5b9c46c473863dc57af6f41365a64ea5f9a3"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10601-015-9185-y"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1017742435"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10601-015-9185-y",
"https://app.dimensions.ai/details/publication/pub.1017742435"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-10T14:54",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8663_00000487.jsonl",
"type": "ScholarlyArticle",
"url": "http://link.springer.com/10.1007/s10601-015-9185-y"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10601-015-9185-y'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10601-015-9185-y'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10601-015-9185-y'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10601-015-9185-y'
This table displays all metadata directly associated to this object as RDF triples.
140 TRIPLES
21 PREDICATES
47 URIs
19 LITERALS
7 BLANK NODES