Ontology type: schema:Chapter
2014
AUTHORSAchref El Mouelhi , Philippe Jégou , Cyril Terrioux
ABSTRACTThe CSP formalism has shown, for many years, its interest for the representation of numerous kinds of problems, and also often provide effective resolution methods in practice. This formalism has also provided a useful framework for the knowledge representation as well as to implement efficient methods for reasoning about knowledge. The data of a CSP are usually expressed in terms of a constraint network. This network is a (constraints) graph when the arity of the constraints is equal to two (binary constraints), or a (constraint) hypergraph in the case of constraints of arbitrary arity, which is generally the case for problems of real life. The study of the structural properties of these networks has made it possible to highlight certain properties, which led to the definition of new tractable classes, but in most cases, they have been defined for the restricted case of binary constraints. So, several representations by graphs have been proposed for the study of constraint hypergraphs to extend the known results to the binary case. Another approach, finer, is interested in the study of the microstructure of CSP, which is defined by graphs. This helped, offering a new theoretical framework to propose other tractable classes. In this paper, we propose to extend the notion of microstructure to any type of CSP. For this, we propose three kinds of graphs that can take into account the constraints of arbitrary arity. We show how these new theoretical tools can already provide a framework for developing new tractable classes for CSPs. We think that these new representations should be of interest for the community, firstly for the generalization of existing results, but also to obtain original results. More... »
PAGES21-38
Graph Structures for Knowledge Representation and Reasoning
ISBN
978-3-319-04533-7
978-3-319-04534-4
http://scigraph.springernature.com/pub.10.1007/978-3-319-04534-4_3
DOIhttp://dx.doi.org/10.1007/978-3-319-04534-4_3
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1032420536
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 CNRS 7296, Aix-Marseille Universit\u00e9, Avenue Escadrille Normandie-Niemen, 13397\u00a0Marseille Cedex 20, France"
],
"type": "Organization"
},
"familyName": "Mouelhi",
"givenName": "Achref El",
"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 CNRS 7296, Aix-Marseille Universit\u00e9, Avenue Escadrille Normandie-Niemen, 13397\u00a0Marseille Cedex 20, 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 CNRS 7296, Aix-Marseille Universit\u00e9, Avenue Escadrille Normandie-Niemen, 13397\u00a0Marseille Cedex 20, 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(87)90002-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002613155"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0004-3702(87)90002-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002613155"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.ejc.2011.04.001",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006132503"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0004-3702(02)00400-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007778118"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0020-0190(97)00044-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017636959"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45193-8_57",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018588447",
"https://doi.org/10.1007/978-3-540-45193-8_57"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45193-8_57",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018588447",
"https://doi.org/10.1007/978-3-540-45193-8_57"
],
"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": "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": "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(89)90037-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029979336"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0004-3702(89)90037-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029979336"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45193-8_6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032292320",
"https://doi.org/10.1007/978-3-540-45193-8_6"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-45193-8_6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032292320",
"https://doi.org/10.1007/978-3-540-45193-8_6"
],
"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": "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": "sg:pub.10.1007/s10601-006-8059-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043939739",
"https://doi.org/10.1007/s10601-006-8059-8"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10601-006-8059-8",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043939739",
"https://doi.org/10.1007/s10601-006-8059-8"
],
"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/0004-3702(80)90051-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1045789426"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0004-3702(80)90051-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1045789426"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10601-008-9057-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1045825986",
"https://doi.org/10.1007/s10601-008-9057-9"
],
"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.1137/0210059",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062841612"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tai.1989.65349",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1086170535"
],
"type": "CreativeWork"
}
],
"datePublished": "2014",
"datePublishedReg": "2014-01-01",
"description": "The CSP formalism has shown, for many years, its interest for the representation of numerous kinds of problems, and also often provide effective resolution methods in practice. This formalism has also provided a useful framework for the knowledge representation as well as to implement efficient methods for reasoning about knowledge. The data of a CSP are usually expressed in terms of a constraint network. This network is a (constraints) graph when the arity of the constraints is equal to two (binary constraints), or a (constraint) hypergraph in the case of constraints of arbitrary arity, which is generally the case for problems of real life. The study of the structural properties of these networks has made it possible to highlight certain properties, which led to the definition of new tractable classes, but in most cases, they have been defined for the restricted case of binary constraints. So, several representations by graphs have been proposed for the study of constraint hypergraphs to extend the known results to the binary case. Another approach, finer, is interested in the study of the microstructure of CSP, which is defined by graphs. This helped, offering a new theoretical framework to propose other tractable classes. In this paper, we propose to extend the notion of microstructure to any type of CSP. For this, we propose three kinds of graphs that can take into account the constraints of arbitrary arity. We show how these new theoretical tools can already provide a framework for developing new tractable classes for CSPs. We think that these new representations should be of interest for the community, firstly for the generalization of existing results, but also to obtain original results.",
"editor": [
{
"familyName": "Croitoru",
"givenName": "Madalina",
"type": "Person"
},
{
"familyName": "Rudolph",
"givenName": "Sebastian",
"type": "Person"
},
{
"familyName": "Woltran",
"givenName": "Stefan",
"type": "Person"
},
{
"familyName": "Gonzales",
"givenName": "Christophe",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-04534-4_3",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-319-04533-7",
"978-3-319-04534-4"
],
"name": "Graph Structures for Knowledge Representation and Reasoning",
"type": "Book"
},
"name": "Different Classes of Graphs to Represent Microstructures for CSPs",
"pagination": "21-38",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-04534-4_3"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"9a727736be38635a2177040a5692207a67d5a39cc9681f233c78a05ae4472765"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1032420536"
]
}
],
"publisher": {
"location": "Cham",
"name": "Springer International Publishing",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-04534-4_3",
"https://app.dimensions.ai/details/publication/pub.1032420536"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-15T23:53",
"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_8697_00000263.jsonl",
"type": "Chapter",
"url": "http://link.springer.com/10.1007/978-3-319-04534-4_3"
}
]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/978-3-319-04534-4_3'
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/978-3-319-04534-4_3'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-04534-4_3'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-04534-4_3'
This table displays all metadata directly associated to this object as RDF triples.
164 TRIPLES
23 PREDICATES
48 URIs
20 LITERALS
8 BLANK NODES