Arc and Path Consistency Revisited
Identifieur interne : 000252 ( Crin/Curation ); précédent : 000251; suivant : 000253Arc and Path Consistency Revisited
Auteurs : R. Mohr ; T. HendersonSource :
- Artificial Intelligence ; 1986.
English descriptors
Abstract
Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms. 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 ALICE (a general constraint satisfaction system) and local consistency methods.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000252
Links to Exploration step
CRIN:mohr85aLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="141">Arc and Path Consistency Revisited</title>
</titleStmt>
<publicationStmt><idno type="RBID">CRIN:mohr85a</idno>
<date when="1986" year="1986">1986</date>
<idno type="wicri:Area/Crin/Corpus">000252</idno>
<idno type="wicri:Area/Crin/Curation">000252</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">000252</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Arc and Path Consistency Revisited</title>
<author><name sortKey="Mohr, R" sort="Mohr, R" uniqKey="Mohr R" first="R." last="Mohr">R. Mohr</name>
</author>
<author><name sortKey="Henderson, T" sort="Henderson, T" uniqKey="Henderson T" first="T." last="Henderson">T. Henderson</name>
</author>
</analytic>
<series><title level="j">Artificial Intelligence</title>
<imprint><date when="1986" type="published">1986</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>arc consistency</term>
<term>consistency</term>
<term>constraint satisfaction</term>
<term>path consistency</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en" wicri:score="1784">Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms. 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 ALICE (a general constraint satisfaction system) and local consistency methods.</div>
</front>
</TEI>
<BibTex type="article"><ref>mohr85a</ref>
<crinnumber>85-R-065</crinnumber>
<category>1</category>
<equipe>INCONNUE</equipe>
<author><e>Mohr, R.</e>
<e>Henderson, T.</e>
</author>
<title>Arc and Path Consistency Revisited</title>
<journal>Artificial Intelligence</journal>
<year>1986</year>
<volume>28</volume>
<number>2</number>
<pages>225-233</pages>
<month>Mar</month>
<keywords><e>arc consistency</e>
<e>path consistency</e>
<e>consistency</e>
<e>constraint satisfaction</e>
</keywords>
<abstract>Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms. 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 ALICE (a general constraint satisfaction system) and local consistency methods.</abstract>
</BibTex>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Crin/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000252 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Crin/Curation/biblio.hfd -nk 000252 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Crin |étape= Curation |type= RBID |clé= CRIN:mohr85a |texte= Arc and Path Consistency Revisited }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |