SAT-based procedures for temporal reasoning
Identifieur interne :
000A25 ( PascalFrancis/Corpus );
précédent :
000A24;
suivant :
000A26
SAT-based procedures for temporal reasoning
Auteurs : A. Armando ;
C. Castellini ;
E. GiunchigliaSource :
-
Lecture notes in computer science [ 0302-9743 ] ; 2000.
RBID : Pascal:00-0458290
Descripteurs français
- Pascal (Inist)
- Raisonnement,
Vérification expérimentale,
Etude expérimentale,
Logique temporelle,
Forme disjonctive,
Sémantique,
Ramification,
SAT based procedure,
Contrainte temporelle,
Base donnée temporelle,
Satisfiabilité.
English descriptors
Abstract
In this paper we study the consistency problem for a set of disjunctive temporal constraints [Stergiou and Koubarakis, 1998]. We propose two SAT-based procedures, and show that-on sets of binary randomly generated disjunctive constraints-they perform up to 2 orders of magnitude less consistency checks than the best procedure presented in [Stergiou and Koubarakis, 1998]. On these tests, our experimental analysis confirms Stergiou and Koubarakis's result about the existence of an easy-hard-easy pattern whose peak corresponds to a value in between 6 and 7 of the ratio of clauses to variables.
Notice en format standard (ISO 2709)
Pour connaître la documentation sur le format Inist Standard.
| pA |
| A01 | 01 | 1 | | @0 0302-9743 |
|---|
| A05 | | | | @2 1809 |
|---|
| A08 | 01 | 1 | ENG | @1 SAT-based procedures for temporal reasoning |
|---|
| A09 | 01 | 1 | ENG | @1 Recent advances in AI planning : Durham, 8-10 September 1999 |
|---|
| A11 | 01 | 1 | | @1 ARMANDO (A.) |
|---|
| A11 | 02 | 1 | | @1 CASTELLINI (C.) |
|---|
| A11 | 03 | 1 | | @1 GIUNCHIGLIA (E.) |
|---|
| A12 | 01 | 1 | | @1 BIUNDO (Susanne) @9 ed. |
|---|
| A12 | 02 | 1 | | @1 FOX (Maria) @9 ed. |
|---|
| A14 | 01 | | | @1 DIST - Università di Genova, Viale Causa 13 @2 16145 Genova @3 ITA @Z 1 aut. @Z 3 aut. |
|---|
| A14 | 02 | | | @1 LORIA-INRIA, 615, rue du Jardin Botanique @2 54602 Villers les Nancy @3 FRA @Z 1 aut. |
|---|
| A14 | 03 | | | @1 Div. of Informatics, U. of Edinburgh, 80 South Bridge @2 Edinburgh EH1 1HN @3 GBR @Z 2 aut. |
|---|
| A20 | | | | @1 97-108 |
|---|
| A21 | | | | @1 2000 |
|---|
| A23 | 01 | | | @0 ENG |
|---|
| A26 | 01 | | | @0 3-540-67866-2 |
|---|
| A43 | 01 | | | @1 INIST @2 16343 @5 354000090077830080 |
|---|
| A44 | | | | @0 0000 @1 © 2000 INIST-CNRS. All rights reserved. |
|---|
| A45 | | | | @0 17 ref. |
|---|
| A47 | 01 | 1 | | @0 00-0458290 |
|---|
| A60 | | | | @1 P @2 C |
|---|
| A61 | | | | @0 A |
|---|
| A64 | 01 | 1 | | @0 Lecture notes in computer science |
|---|
| A66 | 01 | | | @0 DEU |
|---|
| A66 | 02 | | | @0 USA |
|---|
| C01 | 01 | | ENG | @0 In this paper we study the consistency problem for a set of disjunctive temporal constraints [Stergiou and Koubarakis, 1998]. We propose two SAT-based procedures, and show that-on sets of binary randomly generated disjunctive constraints-they perform up to 2 orders of magnitude less consistency checks than the best procedure presented in [Stergiou and Koubarakis, 1998]. On these tests, our experimental analysis confirms Stergiou and Koubarakis's result about the existence of an easy-hard-easy pattern whose peak corresponds to a value in between 6 and 7 of the ratio of clauses to variables. |
|---|
| C02 | 01 | X | | @0 001D02C05 |
|---|
| C03 | 01 | X | FRE | @0 Raisonnement @5 01 |
|---|
| C03 | 01 | X | ENG | @0 Reasoning @5 01 |
|---|
| C03 | 01 | X | SPA | @0 Razonamiento @5 01 |
|---|
| C03 | 02 | X | FRE | @0 Vérification expérimentale @5 02 |
|---|
| C03 | 02 | X | ENG | @0 Experimental test @5 02 |
|---|
| C03 | 02 | X | SPA | @0 Verificación experimental @5 02 |
|---|
| C03 | 03 | X | FRE | @0 Etude expérimentale @5 03 |
|---|
| C03 | 03 | X | ENG | @0 Experimental study @5 03 |
|---|
| C03 | 03 | X | SPA | @0 Estudio experimental @5 03 |
|---|
| C03 | 04 | X | FRE | @0 Logique temporelle @5 04 |
|---|
| C03 | 04 | X | ENG | @0 Temporal logic @5 04 |
|---|
| C03 | 04 | X | SPA | @0 Lógica temporal @5 04 |
|---|
| C03 | 05 | X | FRE | @0 Forme disjonctive @5 05 |
|---|
| C03 | 05 | X | ENG | @0 Disjunctive form @5 05 |
|---|
| C03 | 05 | X | SPA | @0 Forma disyuntiva @5 05 |
|---|
| C03 | 06 | X | FRE | @0 Sémantique @5 06 |
|---|
| C03 | 06 | X | ENG | @0 Semantics @5 06 |
|---|
| C03 | 06 | X | SPA | @0 Semántica @5 06 |
|---|
| C03 | 07 | X | FRE | @0 Ramification @5 07 |
|---|
| C03 | 07 | X | ENG | @0 Branching @5 07 |
|---|
| C03 | 07 | X | SPA | @0 Ramificación @5 07 |
|---|
| C03 | 08 | X | FRE | @0 SAT based procedure @4 INC @5 82 |
|---|
| C03 | 09 | X | FRE | @0 Contrainte temporelle @4 CD @5 96 |
|---|
| C03 | 09 | X | ENG | @0 Temporal constraint @4 CD @5 96 |
|---|
| C03 | 10 | X | FRE | @0 Base donnée temporelle @4 CD @5 97 |
|---|
| C03 | 10 | X | ENG | @0 Data warehouse @4 CD @5 97 |
|---|
| C03 | 11 | X | FRE | @0 Satisfiabilité @4 CD @5 98 |
|---|
| C03 | 11 | X | ENG | @0 Satisfiability @4 CD @5 98 |
|---|
| N21 | | | | @1 304 |
|---|
|
|---|
| pR |
| A30 | 01 | 1 | ENG | @1 ECP'99 : European conference on planning @2 5 @3 Durham GBR @4 1999-09-08 |
|---|
|
|---|
Format Inist (serveur)
| NO : | PASCAL 00-0458290 INIST |
|---|
| ET : | SAT-based procedures for temporal reasoning |
|---|
| AU : | ARMANDO (A.); CASTELLINI (C.); GIUNCHIGLIA (E.); BIUNDO (Susanne); FOX (Maria) |
|---|
| AF : | DIST - Università di Genova, Viale Causa 13 /16145 Genova/Italie (1 aut., 3 aut.); LORIA-INRIA, 615, rue du Jardin Botanique/54602 Villers les Nancy/France (1 aut.); Div. of Informatics, U. of Edinburgh, 80 South Bridge/Edinburgh EH1 1HN/Royaume-Uni (2 aut.) |
|---|
| DT : | Publication en série; Congrès; Niveau analytique |
|---|
| SO : | Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2000; Vol. 1809; Pp. 97-108; Bibl. 17 ref. |
|---|
| LA : | Anglais |
|---|
| EA : | In this paper we study the consistency problem for a set of disjunctive temporal constraints [Stergiou and Koubarakis, 1998]. We propose two SAT-based procedures, and show that-on sets of binary randomly generated disjunctive constraints-they perform up to 2 orders of magnitude less consistency checks than the best procedure presented in [Stergiou and Koubarakis, 1998]. On these tests, our experimental analysis confirms Stergiou and Koubarakis's result about the existence of an easy-hard-easy pattern whose peak corresponds to a value in between 6 and 7 of the ratio of clauses to variables. |
|---|
| CC : | 001D02C05 |
|---|
| FD : | Raisonnement; Vérification expérimentale; Etude expérimentale; Logique temporelle; Forme disjonctive; Sémantique; Ramification; SAT based procedure; Contrainte temporelle; Base donnée temporelle; Satisfiabilité |
|---|
| ED : | Reasoning; Experimental test; Experimental study; Temporal logic; Disjunctive form; Semantics; Branching; Temporal constraint; Data warehouse; Satisfiability |
|---|
| SD : | Razonamiento; Verificación experimental; Estudio experimental; Lógica temporal; Forma disyuntiva; Semántica; Ramificación |
|---|
| LO : | INIST-16343.354000090077830080 |
|---|
| ID : | 00-0458290 |
|---|
Links to Exploration step
Pascal:00-0458290
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">SAT-based procedures for temporal reasoning</title>
<author><name sortKey="Armando, A" sort="Armando, A" uniqKey="Armando A" first="A." last="Armando">A. Armando</name>
<affiliation><inist:fA14 i1="01"><s1>DIST - Università di Genova, Viale Causa 13 </s1>
<s2>16145 Genova</s2>
<s3>ITA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14><affiliation><inist:fA14 i1="02"><s1>LORIA-INRIA, 615, rue du Jardin Botanique</s1>
<s2>54602 Villers les Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Castellini, C" sort="Castellini, C" uniqKey="Castellini C" first="C." last="Castellini">C. Castellini</name>
<affiliation><inist:fA14 i1="03"><s1>Div. of Informatics, U. of Edinburgh, 80 South Bridge</s1>
<s2>Edinburgh EH1 1HN</s2>
<s3>GBR</s3>
<sZ>2 aut.</sZ>
</inist:fA14><author><name sortKey="Giunchiglia, E" sort="Giunchiglia, E" uniqKey="Giunchiglia E" first="E." last="Giunchiglia">E. Giunchiglia</name>
<affiliation><inist:fA14 i1="01"><s1>DIST - Università di Genova, Viale Causa 13 </s1>
<s2>16145 Genova</s2>
<s3>ITA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14><publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">00-0458290</idno>
<date when="2000">2000</date>
<idno type="stanalyst">PASCAL 00-0458290 INIST</idno>
<idno type="RBID">Pascal:00-0458290</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000A25</idno>
</publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">SAT-based procedures for temporal reasoning</title>
<author><name sortKey="Armando, A" sort="Armando, A" uniqKey="Armando A" first="A." last="Armando">A. Armando</name>
<affiliation><inist:fA14 i1="01"><s1>DIST - Università di Genova, Viale Causa 13 </s1>
<s2>16145 Genova</s2>
<s3>ITA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14><affiliation><inist:fA14 i1="02"><s1>LORIA-INRIA, 615, rue du Jardin Botanique</s1>
<s2>54602 Villers les Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Castellini, C" sort="Castellini, C" uniqKey="Castellini C" first="C." last="Castellini">C. Castellini</name>
<affiliation><inist:fA14 i1="03"><s1>Div. of Informatics, U. of Edinburgh, 80 South Bridge</s1>
<s2>Edinburgh EH1 1HN</s2>
<s3>GBR</s3>
<sZ>2 aut.</sZ>
</inist:fA14><author><name sortKey="Giunchiglia, E" sort="Giunchiglia, E" uniqKey="Giunchiglia E" first="E." last="Giunchiglia">E. Giunchiglia</name>
<affiliation><inist:fA14 i1="01"><s1>DIST - Università di Genova, Viale Causa 13 </s1>
<s2>16145 Genova</s2>
<s3>ITA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14><series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="2000">2000</date>
</imprint><seriesStmt><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
</seriesStmt><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Branching</term>
<term>Data warehouse</term>
<term>Disjunctive form</term>
<term>Experimental study</term>
<term>Experimental test</term>
<term>Reasoning</term>
<term>Satisfiability</term>
<term>Semantics</term>
<term>Temporal constraint</term>
<term>Temporal logic</term>
</keywords><keywords scheme="Pascal" xml:lang="fr"><term>Raisonnement</term>
<term>Vérification expérimentale</term>
<term>Etude expérimentale</term>
<term>Logique temporelle</term>
<term>Forme disjonctive</term>
<term>Sémantique</term>
<term>Ramification</term>
<term>SAT based procedure</term>
<term>Contrainte temporelle</term>
<term>Base donnée temporelle</term>
<term>Satisfiabilité</term>
</keywords><front><div type="abstract" xml:lang="en">In this paper we study the consistency problem for a set of disjunctive temporal constraints [Stergiou and Koubarakis, 1998]. We propose two SAT-based procedures, and show that-on sets of binary randomly generated disjunctive constraints-they perform up to 2 orders of magnitude less consistency checks than the best procedure presented in [Stergiou and Koubarakis, 1998]. On these tests, our experimental analysis confirms Stergiou and Koubarakis's result about the existence of an easy-hard-easy pattern whose peak corresponds to a value in between 6 and 7 of the ratio of clauses to variables.</div>
</front><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0>
</fA01><fA05><s2>1809</s2>
</fA05><fA08 i1="01" i2="1" l="ENG"><s1>SAT-based procedures for temporal reasoning</s1>
</fA08><fA09 i1="01" i2="1" l="ENG"><s1>Recent advances in AI planning : Durham, 8-10 September 1999</s1>
</fA09><fA11 i1="01" i2="1"><s1>ARMANDO (A.)</s1>
</fA11><fA11 i1="02" i2="1"><s1>CASTELLINI (C.)</s1>
</fA11><fA11 i1="03" i2="1"><s1>GIUNCHIGLIA (E.)</s1>
</fA11><fA12 i1="01" i2="1"><s1>BIUNDO (Susanne)</s1>
<s9>ed.</s9>
</fA12><fA12 i1="02" i2="1"><s1>FOX (Maria)</s1>
<s9>ed.</s9>
</fA12><fA14 i1="01"><s1>DIST - Università di Genova, Viale Causa 13 </s1>
<s2>16145 Genova</s2>
<s3>ITA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
</fA14><fA14 i1="02"><s1>LORIA-INRIA, 615, rue du Jardin Botanique</s1>
<s2>54602 Villers les Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14><fA14 i1="03"><s1>Div. of Informatics, U. of Edinburgh, 80 South Bridge</s1>
<s2>Edinburgh EH1 1HN</s2>
<s3>GBR</s3>
<sZ>2 aut.</sZ>
</fA14><fA20><s1>97-108</s1>
</fA20><fA21><s1>2000</s1>
</fA21><fA23 i1="01"><s0>ENG</s0>
</fA23><fA26 i1="01"><s0>3-540-67866-2</s0>
</fA26><fA43 i1="01"><s1>INIST</s1>
<s2>16343</s2>
<s5>354000090077830080</s5>
</fA43><fA44><s0>0000</s0>
<s1>© 2000 INIST-CNRS. All rights reserved.</s1>
</fA44><fA45><s0>17 ref.</s0>
</fA45><fA47 i1="01" i2="1"><s0>00-0458290</s0>
</fA47><fA60><s1>P</s1>
<s2>C</s2>
</fA60><fA64 i1="01" i2="1"><s0>Lecture notes in computer science</s0>
</fA64><fA66 i1="01"><s0>DEU</s0>
</fA66><fA66 i1="02"><s0>USA</s0>
</fA66><fC01 i1="01" l="ENG"><s0>In this paper we study the consistency problem for a set of disjunctive temporal constraints [Stergiou and Koubarakis, 1998]. We propose two SAT-based procedures, and show that-on sets of binary randomly generated disjunctive constraints-they perform up to 2 orders of magnitude less consistency checks than the best procedure presented in [Stergiou and Koubarakis, 1998]. On these tests, our experimental analysis confirms Stergiou and Koubarakis's result about the existence of an easy-hard-easy pattern whose peak corresponds to a value in between 6 and 7 of the ratio of clauses to variables.</s0>
</fC01><fC02 i1="01" i2="X"><s0>001D02C05</s0>
</fC02><fC03 i1="01" i2="X" l="FRE"><s0>Raisonnement</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="ENG"><s0>Reasoning</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="SPA"><s0>Razonamiento</s0>
<s5>01</s5>
</fC03><fC03 i1="02" i2="X" l="FRE"><s0>Vérification expérimentale</s0>
<s5>02</s5>
</fC03><fC03 i1="02" i2="X" l="ENG"><s0>Experimental test</s0>
<s5>02</s5>
</fC03><fC03 i1="02" i2="X" l="SPA"><s0>Verificación experimental</s0>
<s5>02</s5>
</fC03><fC03 i1="03" i2="X" l="FRE"><s0>Etude expérimentale</s0>
<s5>03</s5>
</fC03><fC03 i1="03" i2="X" l="ENG"><s0>Experimental study</s0>
<s5>03</s5>
</fC03><fC03 i1="03" i2="X" l="SPA"><s0>Estudio experimental</s0>
<s5>03</s5>
</fC03><fC03 i1="04" i2="X" l="FRE"><s0>Logique temporelle</s0>
<s5>04</s5>
</fC03><fC03 i1="04" i2="X" l="ENG"><s0>Temporal logic</s0>
<s5>04</s5>
</fC03><fC03 i1="04" i2="X" l="SPA"><s0>Lógica temporal</s0>
<s5>04</s5>
</fC03><fC03 i1="05" i2="X" l="FRE"><s0>Forme disjonctive</s0>
<s5>05</s5>
</fC03><fC03 i1="05" i2="X" l="ENG"><s0>Disjunctive form</s0>
<s5>05</s5>
</fC03><fC03 i1="05" i2="X" l="SPA"><s0>Forma disyuntiva</s0>
<s5>05</s5>
</fC03><fC03 i1="06" i2="X" l="FRE"><s0>Sémantique</s0>
<s5>06</s5>
</fC03><fC03 i1="06" i2="X" l="ENG"><s0>Semantics</s0>
<s5>06</s5>
</fC03><fC03 i1="06" i2="X" l="SPA"><s0>Semántica</s0>
<s5>06</s5>
</fC03><fC03 i1="07" i2="X" l="FRE"><s0>Ramification</s0>
<s5>07</s5>
</fC03><fC03 i1="07" i2="X" l="ENG"><s0>Branching</s0>
<s5>07</s5>
</fC03><fC03 i1="07" i2="X" l="SPA"><s0>Ramificación</s0>
<s5>07</s5>
</fC03><fC03 i1="08" i2="X" l="FRE"><s0>SAT based procedure</s0>
<s4>INC</s4>
<s5>82</s5>
</fC03><fC03 i1="09" i2="X" l="FRE"><s0>Contrainte temporelle</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03><fC03 i1="09" i2="X" l="ENG"><s0>Temporal constraint</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03><fC03 i1="10" i2="X" l="FRE"><s0>Base donnée temporelle</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03><fC03 i1="10" i2="X" l="ENG"><s0>Data warehouse</s0>
<s4>CD</s4>
<s5>97</s5>
</fC03><fC03 i1="11" i2="X" l="FRE"><s0>Satisfiabilité</s0>
<s4>CD</s4>
<s5>98</s5>
</fC03><fC03 i1="11" i2="X" l="ENG"><s0>Satisfiability</s0>
<s4>CD</s4>
<s5>98</s5>
</fC03><fN21><s1>304</s1>
</fN21><pR><fA30 i1="01" i2="1" l="ENG"><s1>ECP'99 : European conference on planning</s1>
<s2>5</s2>
<s3>Durham GBR</s3>
<s4>1999-09-08</s4>
</fA30><server><NO>PASCAL 00-0458290 INIST</NO>
<ET>SAT-based procedures for temporal reasoning</ET>
<AU>ARMANDO (A.); CASTELLINI (C.); GIUNCHIGLIA (E.); BIUNDO (Susanne); FOX (Maria)</AU>
<AF>DIST - Università di Genova, Viale Causa 13 /16145 Genova/Italie (1 aut., 3 aut.); LORIA-INRIA, 615, rue du Jardin Botanique/54602 Villers les Nancy/France (1 aut.); Div. of Informatics, U. of Edinburgh, 80 South Bridge/Edinburgh EH1 1HN/Royaume-Uni (2 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2000; Vol. 1809; Pp. 97-108; Bibl. 17 ref.</SO>
<LA>Anglais</LA>
<EA>In this paper we study the consistency problem for a set of disjunctive temporal constraints [Stergiou and Koubarakis, 1998]. We propose two SAT-based procedures, and show that-on sets of binary randomly generated disjunctive constraints-they perform up to 2 orders of magnitude less consistency checks than the best procedure presented in [Stergiou and Koubarakis, 1998]. On these tests, our experimental analysis confirms Stergiou and Koubarakis's result about the existence of an easy-hard-easy pattern whose peak corresponds to a value in between 6 and 7 of the ratio of clauses to variables.</EA>
<CC>001D02C05</CC>
<FD>Raisonnement; Vérification expérimentale; Etude expérimentale; Logique temporelle; Forme disjonctive; Sémantique; Ramification; SAT based procedure; Contrainte temporelle; Base donnée temporelle; Satisfiabilité</FD>
<ED>Reasoning; Experimental test; Experimental study; Temporal logic; Disjunctive form; Semantics; Branching; Temporal constraint; Data warehouse; Satisfiability</ED>
<SD>Razonamiento; Verificación experimental; Estudio experimental; Lógica temporal; Forma disyuntiva; Semántica; Ramificación</SD>
<LO>INIST-16343.354000090077830080</LO>
<ID>00-0458290</ID>
</server>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000A25 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000A25 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Corpus
|type= RBID
|clé= Pascal:00-0458290
|texte= SAT-based procedures for temporal reasoning
}}
| 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 |  |
