InforLorV4, Main, Exploration, bibRecordById, Pascal:00-0458290

SAT-Based Procedures for Temporal Reasoning

Identifieur interne : 009E35 ( Main/Exploration ); précédent : 009E34; suivant : 009E36

SAT-Based Procedures for Temporal Reasoning

Auteurs : Alessandro Armando [Italie, France] ; Claudio Castellini [Royaume-Uni] ; Enrico Giunchiglia [Italie]

Source :

Lecture Notes in Computer Science [ 0302-9743 ]

RBID : ISTEX:C445BAF63CB21DEA4CA38986AFA8063D779F222D

Descripteurs français

Pascal (Inist)
- Base donnée temporelle, Contrainte temporelle, Etude expérimentale, Forme disjonctive, Logique temporelle, Raisonnement, Ramification, SAT based procedure, Satisfiabilité, Sémantique, Vérification expérimentale.

English descriptors

KwdEn :
- Branching, Data warehouse, Disjunctive form, Experimental study, Experimental test, Reasoning, Satisfiability, Semantics, Temporal constraint, Temporal logic.

Abstract

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.

Url:

https://api.istex.fr/ark:/67375/HCB-Z6XFGM01-L/fulltext.pdf

DOI: 10.1007/10720246_8

Affiliations:

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">SAT-Based Procedures for Temporal Reasoning</title>
<author><name sortKey="Armando, Alessandro" sort="Armando, Alessandro" uniqKey="Armando A" first="Alessandro" last="Armando">Alessandro Armando</name>
</author>
<author><name sortKey="Castellini, Claudio" sort="Castellini, Claudio" uniqKey="Castellini C" first="Claudio" last="Castellini">Claudio Castellini</name>
</author>
<author><name sortKey="Giunchiglia, Enrico" sort="Giunchiglia, Enrico" uniqKey="Giunchiglia E" first="Enrico" last="Giunchiglia">Enrico Giunchiglia</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:C445BAF63CB21DEA4CA38986AFA8063D779F222D</idno>
<date when="2000" year="2000">2000</date>
<idno type="doi">10.1007/10720246_8</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-Z6XFGM01-L/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002E57</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002E57</idno>
<idno type="wicri:Area/Istex/Curation">002E19</idno>
<idno type="wicri:Area/Istex/Checkpoint">002088</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002088</idno>
<idno type="wicri:doubleKey">0302-9743:2000:Armando A:sat:based:procedures</idno>
<idno type="wicri:Area/Main/Merge">00A416</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:00-0458290</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000A25</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000057</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000971</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000971</idno>
<idno type="wicri:doubleKey">0302-9743:2000:Armando A:sat:based:procedures</idno>
<idno type="wicri:Area/Main/Merge">00A577</idno>
<idno type="wicri:Area/Main/Curation">009E35</idno>
<idno type="wicri:Area/Main/Exploration">009E35</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">SAT-Based Procedures for Temporal Reasoning</title>
<author><name sortKey="Armando, Alessandro" sort="Armando, Alessandro" uniqKey="Armando A" first="Alessandro" last="Armando">Alessandro Armando</name>
<affiliation wicri:level="1"><country xml:lang="fr">Italie</country>
<wicri:regionArea>DIST – Università di Genova, Viale Causa 13, 16145, Genova</wicri:regionArea>
<wicri:noRegion>Genova</wicri:noRegion>
</affiliation>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>LORIA-INRIA, 615, rue du Jardin Botanique, 54602, Villers les Nancy</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Villers les Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Castellini, Claudio" sort="Castellini, Claudio" uniqKey="Castellini C" first="Claudio" last="Castellini">Claudio Castellini</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Div. of Informatics, U. of Edinburgh, 80 South Bridge, EH1 1HN, Edinburgh</wicri:regionArea>
<placeName><settlement type="city">Édimbourg</settlement>
<region type="country">Écosse</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Giunchiglia, Enrico" sort="Giunchiglia, Enrico" uniqKey="Giunchiglia E" first="Enrico" last="Giunchiglia">Enrico Giunchiglia</name>
<affiliation wicri:level="1"><country xml:lang="fr">Italie</country>
<wicri:regionArea>DIST – Università di Genova, Viale Causa 13, 16145, Genova</wicri:regionArea>
<wicri:noRegion>Genova</wicri:noRegion>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<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>Base donnée temporelle</term>
<term>Contrainte temporelle</term>
<term>Etude expérimentale</term>
<term>Forme disjonctive</term>
<term>Logique temporelle</term>
<term>Raisonnement</term>
<term>Ramification</term>
<term>SAT based procedure</term>
<term>Satisfiabilité</term>
<term>Sémantique</term>
<term>Vérification expérimentale</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">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.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>Italie</li>
<li>Royaume-Uni</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Écosse</li>
</region>
<settlement><li>Villers les Nancy</li>
<li>Édimbourg</li>
</settlement>
</list>
<tree><country name="Italie"><noRegion><name sortKey="Armando, Alessandro" sort="Armando, Alessandro" uniqKey="Armando A" first="Alessandro" last="Armando">Alessandro Armando</name>
</noRegion>
<name sortKey="Giunchiglia, Enrico" sort="Giunchiglia, Enrico" uniqKey="Giunchiglia E" first="Enrico" last="Giunchiglia">Enrico Giunchiglia</name>
</country>
<country name="France"><region name="Grand Est"><name sortKey="Armando, Alessandro" sort="Armando, Alessandro" uniqKey="Armando A" first="Alessandro" last="Armando">Alessandro Armando</name>
</region>
</country>
<country name="Royaume-Uni"><region name="Écosse"><name sortKey="Castellini, Claudio" sort="Castellini, Claudio" uniqKey="Castellini C" first="Claudio" last="Castellini">Claudio Castellini</name>
</region>
</country>
</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 009E35 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 009E35 | 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é=     ISTEX:C445BAF63CB21DEA4CA38986AFA8063D779F222D
   |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

Serveur d'exploration sur la recherche en informatique en Lorraine

SAT-Based Procedures for Temporal Reasoning

SAT-Based Procedures for Temporal Reasoning

Source :

Descripteurs français

English descriptors

Abstract

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

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

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

	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.