InforLorV4, Hal, Curation, bibRecord, 000F73

Arc and Path Consistency Revisited

Identifieur interne : 000F73 ( Hal/Curation ); précédent : 000F72; suivant : 000F74

Arc and Path Consistency Revisited

Auteurs : Roger Mohr [France] ; Thomas Henderson [États-Unis]

Source :

Artificial Intelligence [ 0004-3702 ] ; 1986-03.

RBID : Hal:inria-00548487

Abstract

Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms [5]. We present here new algorithms for arc and path consistency and show that the arc consistency algorithm is optimal in time complexity and of the same-order space complexity as the earlier algorithms. A refined solution for the path consistency problem is proposed. However, the space complexity of the path consistency algorithm makes it practicable only for small problems. These algorithms are the result of the synthesis techniques used in Image (a general constraint satisfaction system) and local consistency methods [3].

Url:

https://hal.inria.fr/inria-00548487

DOI: 10.1016/0004-3702(86)90083-4

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000F73

Links to Exploration step

Hal:inria-00548487

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Arc and Path Consistency Revisited</title>
<author><name sortKey="Mohr, Roger" sort="Mohr, Roger" uniqKey="Mohr R" first="Roger" last="Mohr">Roger Mohr</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-133218" status="OLD"><orgName>Centre de Recherche en Informatique de Nancy</orgName>
<orgName type="acronym">CRIN</orgName>
<desc><address><addrLine>CRIN RFIA Campus Scientifique B.P. 239 54506 Vandoeuvre-Les-Nancy</addrLine>
<country key="FR"></country>
</address>
</desc>
<listRelation><relation active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Henderson, Thomas" sort="Henderson, Thomas" uniqKey="Henderson T" first="Thomas" last="Henderson">Thomas Henderson</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-135164" status="OLD"><orgName>Department of Computer Science</orgName>
<desc><address><addrLine>The University of Utah 50 S. Central Campus Drive, Room 3190, Salt Lake City, UT 84112</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.cs.utah.edu/</ref>
</desc>
<listRelation><relation active="#struct-300863" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300863" type="direct"><org type="institution" xml:id="struct-300863" status="VALID"><orgName>University of Utah</orgName>
<desc><address><addrLine>201 Presidents Cir, Salt Lake City, UT 84112</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.utah.edu/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00548487</idno>
<idno type="halId">inria-00548487</idno>
<idno type="halUri">https://hal.inria.fr/inria-00548487</idno>
<idno type="url">https://hal.inria.fr/inria-00548487</idno>
<idno type="doi">10.1016/0004-3702(86)90083-4</idno>
<date when="1986-03">1986-03</date>
<idno type="wicri:Area/Hal/Corpus">000F73</idno>
<idno type="wicri:Area/Hal/Curation">000F73</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Arc and Path Consistency Revisited</title>
<author><name sortKey="Mohr, Roger" sort="Mohr, Roger" uniqKey="Mohr R" first="Roger" last="Mohr">Roger Mohr</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-133218" status="OLD"><orgName>Centre de Recherche en Informatique de Nancy</orgName>
<orgName type="acronym">CRIN</orgName>
<desc><address><addrLine>CRIN RFIA Campus Scientifique B.P. 239 54506 Vandoeuvre-Les-Nancy</addrLine>
<country key="FR"></country>
</address>
</desc>
<listRelation><relation active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Henderson, Thomas" sort="Henderson, Thomas" uniqKey="Henderson T" first="Thomas" last="Henderson">Thomas Henderson</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-135164" status="OLD"><orgName>Department of Computer Science</orgName>
<desc><address><addrLine>The University of Utah 50 S. Central Campus Drive, Room 3190, Salt Lake City, UT 84112</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.cs.utah.edu/</ref>
</desc>
<listRelation><relation active="#struct-300863" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300863" type="direct"><org type="institution" xml:id="struct-300863" status="VALID"><orgName>University of Utah</orgName>
<desc><address><addrLine>201 Presidents Cir, Salt Lake City, UT 84112</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.utah.edu/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1016/0004-3702(86)90083-4</idno>
<series><title level="j">Artificial Intelligence</title>
<idno type="ISSN">0004-3702</idno>
<imprint><date type="datePub">1986-03</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms [5]. We present here new algorithms for arc and path consistency and show that the arc consistency algorithm is optimal in time complexity and of the same-order space complexity as the earlier algorithms. A refined solution for the path consistency problem is proposed. However, the space complexity of the path consistency algorithm makes it practicable only for small problems. These algorithms are the result of the synthesis techniques used in Image (a general constraint satisfaction system) and local consistency methods [3].</div>
</front>
</TEI>
<hal api="V3"><titleStmt><title xml:lang="en">Arc and Path Consistency Revisited</title>
<author role="aut"><persName><forename type="first">Roger</forename>
<surname>Mohr</surname>
</persName>
<email></email>
<idno type="halauthor">100382</idno>
<affiliation ref="#struct-133218"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Thomas</forename>
<surname>Henderson</surname>
</persName>
<email></email>
<idno type="halauthor">104781</idno>
<affiliation ref="#struct-135164"></affiliation>
</author>
<editor role="depositor"><persName><forename>Team</forename>
<surname>Lear</surname>
</persName>
<email>jakob.verbeek@inria.fr</email>
</editor>
</titleStmt>
<editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2010-12-20 08:49:39</date>
<date type="whenWritten">1986</date>
<date type="whenModified">2011-01-05 12:05:30</date>
<date type="whenReleased">2010-12-20 08:49:39</date>
<date type="whenProduced">1986-03</date>
</edition>
<respStmt><resp>contributor</resp>
<name key="156804"><persName><forename>Team</forename>
<surname>Lear</surname>
</persName>
<email>jakob.verbeek@inria.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt><distributor>CCSD</distributor>
<idno type="halId">inria-00548487</idno>
<idno type="halUri">https://hal.inria.fr/inria-00548487</idno>
<idno type="halBibtex">mohr:inria-00548487</idno>
<idno type="halRefHtml">Artificial Intelligence, Elsevier, 1986, 28, pp.225--233. <10.1016/0004-3702(86)90083-4></idno>
<idno type="halRef">Artificial Intelligence, Elsevier, 1986, 28, pp.225--233. <10.1016/0004-3702(86)90083-4></idno>
</publicationStmt>
<seriesStmt><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="UNIV-NANCY1">Université Henri Poincaré - Nancy I</idno>
<idno type="stamp" n="UNIV-NANCY2">Université Nancy II</idno>
</seriesStmt>
<notesStmt><note type="audience" n="2">International</note>
<note type="popular" n="0">No</note>
<note type="peer" n="1">Yes</note>
</notesStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Arc and Path Consistency Revisited</title>
<author role="aut"><persName><forename type="first">Roger</forename>
<surname>Mohr</surname>
</persName>
<idno type="halAuthorId">100382</idno>
<affiliation ref="#struct-133218"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Thomas</forename>
<surname>Henderson</surname>
</persName>
<idno type="halAuthorId">104781</idno>
<affiliation ref="#struct-135164"></affiliation>
</author>
</analytic>
<monogr><idno type="halJournalId" status="VALID">3197</idno>
<idno type="issn">0004-3702</idno>
<title level="j">Artificial Intelligence</title>
<imprint><publisher>Elsevier</publisher>
<biblScope unit="volume">28</biblScope>
<biblScope unit="pp">225--233</biblScope>
<date type="datePub">1986-03</date>
</imprint>
</monogr>
<idno type="doi">10.1016/0004-3702(86)90083-4</idno>
</biblStruct>
</sourceDesc>
<profileDesc><langUsage><language ident="en">English</language>
</langUsage>
<textClass><classCode scheme="halDomain" n="info.info-cv">Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV]</classCode>
<classCode scheme="halTypology" n="ART">Journal articles</classCode>
</textClass>
<abstract xml:lang="en">Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms [5]. We present here new algorithms for arc and path consistency and show that the arc consistency algorithm is optimal in time complexity and of the same-order space complexity as the earlier algorithms. A refined solution for the path consistency problem is proposed. However, the space complexity of the path consistency algorithm makes it practicable only for small problems. These algorithms are the result of the synthesis techniques used in Image (a general constraint satisfaction system) and local consistency methods [3].</abstract>
</profileDesc>
</hal>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Curation

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000F73 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Hal/Curation/biblio.hfd -nk 000F73 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Hal
   |étape=   Curation
   |type=    RBID
   |clé=     Hal:inria-00548487
   |texte=   Arc and Path Consistency Revisited
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Arc and Path Consistency Revisited

Arc and Path Consistency Revisited

Source :

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri