Arc and Path Consistency Revisited
Identifieur interne : 000F73 ( Hal/Corpus ); précédent : 000F72; suivant : 000F74Arc and Path Consistency Revisited
Auteurs : Roger Mohr ; Thomas HendersonSource :
- Artificial Intelligence [ 0004-3702 ] ; 1986-03.
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:
DOI: 10.1016/0004-3702(86)90083-4
Links to Exploration step
Hal:inria-00548487Le 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><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>
</affiliation>
</author>
<author><name sortKey="Henderson, Thomas" sort="Henderson, Thomas" uniqKey="Henderson T" first="Thomas" last="Henderson">Thomas Henderson</name>
<affiliation><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>
</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>
</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><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>
</affiliation>
</author>
<author><name sortKey="Henderson, Thomas" sort="Henderson, Thomas" uniqKey="Henderson T" first="Thomas" last="Henderson">Thomas Henderson</name>
<affiliation><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>
</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/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000F73 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/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= Corpus |type= RBID |clé= Hal:inria-00548487 |texte= Arc and Path Consistency Revisited }}
This area was generated with Dilib version V0.6.33. |