Exploration
Accueil
Racine
Exploration
Accueil
Racine

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.

Arc and Path Consistency Revisited

Identifieur interne : 00E767 ( Main/Exploration ); précédent : 00E766; suivant : 00E768

Arc and Path Consistency Revisited

Auteurs : R. Mohr ; T. Henderson

Source :

RBID : CRIN:mohr85a

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.


Affiliations:

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

Le 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>
<idno type="wicri:Area/Crin/Checkpoint">004272</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">004272</idno>
<idno type="wicri:Area/Main/Merge">00F055</idno>
<idno type="wicri:Area/Main/Curation">00E767</idno>
<idno type="wicri:Area/Main/Exploration">00E767</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>
<affiliations>
<list></list>
<tree>
<noCountry>
<name sortKey="Henderson, T" sort="Henderson, T" uniqKey="Henderson T" first="T." last="Henderson">T. Henderson</name>
<name sortKey="Mohr, R" sort="Mohr, R" uniqKey="Mohr R" first="R." last="Mohr">R. Mohr</name>
</noCountry>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00E767 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00E767 | SxmlIndent | more

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

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     CRIN:mohr85a
   |texte=   Arc and Path Consistency Revisited
}}
Wicri

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