Automatically assigned DDC number: 0063
Manually assigned DDC number: 00633
Number of references: 4
Title: Solving Hard Qualitative Temporal Reasoning Problems: Evaluating the Efficiency of Using the ORD-Horn Class
Author:
Subject: Bernhard Nebel Solving Hard Qualitative Temporal Reasoning Problems: Evaluating the Efficiency of Using the ORD-Horn Class
Description: . While the worst-case computational properties of Allen's calculus for qualitative temporal reasoning have been analyzed quite extensively, the determination of the empirical efficiency of algorithms for solving the consistency problem in this calculus has received only little research attention. In this paper, we will demonstrate that using the ORD-Horn class in Ladkin and Reinefeld's backtracking algorithm leads to performance improvements when deciding consistency of hard instances in Allen's calculus. For this purpose, we prove that Ladkin and Reinefeld's algorithm is complete when using the ORD-Horn class, we identify phase transition regions of the reasoning problem, and compare the improvements of ORD-Horn with other heuristic methods when applied to instances in the phase transition region. Finally, we give evidence that combining search methods orthogonally can dramatically improve the performance of the backtracking algorithm. Keywords: Qualitative temporal reasoning, Allen...
Contributor: The Pennsylvania State University CiteSeer Archives
Publisher: unknown
Date: 1996-09-12
Pubyear: 1997
Format: ps
Identifier: http://citeseer.ist.psu.edu/150602.html
Source: ftp://ftp.informatik.uni-freiburg.de/documents/papers/ki/nebel-constraints-96.ps.gz
Language: en
Relation:
Relation:
Relation:
Relation:
Rights: unrestricted
<?xml version="1.0" encoding="UTF-8"?>
<references_metadata>
<rec ID="/310461.html" Type="article" CiteSeer_Book="Journal of the ACM" CiteSeer_Volume="40" Title="Complexity and Algorithms for Reasoning about Time: {A} Graph-Theoretic Approach,">
<identifier Org="ISBN:026251091X" Paper_ID="/310461.html" Extracted="026251091X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0262731444" Paper_ID="/310461.html" Extracted="0262731444" DDC="153.03" Normalized_DDC="15303" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:038724347X" Paper_ID="/310461.html" Extracted="038724347X" DDC="511/.5" Normalized_DDC="5115" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0821806114" Paper_ID="/310461.html" Extracted="0821806114" DDC="006.3/0151" Normalized_DDC="00630151" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:0821831976" Paper_ID="/310461.html" Extracted="0821831976" DDC="570/.15/1" Normalized_DDC="570151" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:1558604804" Paper_ID="/310461.html" Extracted="1558604804" />
<identifier Org="ISBN:354024087X" Paper_ID="/310461.html" Extracted="354024087X" DDC="004" Normalized_DDC="004" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540413855" Paper_ID="/310461.html" Extracted="3540413855" DDC="510 s" Normalized_DDC="51" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540438653" Paper_ID="/310461.html" Extracted="3540438653" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540555536" Paper_ID="/310461.html" Extracted="3540555536" DDC="004" Normalized_DDC="004" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540578994" Paper_ID="/310461.html" Extracted="3540578994" DDC="004/.01/5115" Normalized_DDC="004015115" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540594086" Paper_ID="/310461.html" Extracted="3540594086" DDC="519.7/7" Normalized_DDC="51977" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540603131" Paper_ID="/310461.html" Extracted="3540603131" DDC="004/.01/5118" Normalized_DDC="004015118" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540645756" Paper_ID="/310461.html" Extracted="3540645756" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540649921" Paper_ID="/310461.html" Extracted="3540649921" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:354064993X" Paper_ID="/310461.html" Extracted="354064993X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540652248" Paper_ID="/310461.html" Extracted="3540652248" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540667318" Paper_ID="/310461.html" Extracted="3540667318" DDC="004.0151" Normalized_DDC="0040151" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540749691" Paper_ID="/310461.html" Extracted="3540749691" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.05555555555555555" />
<identifier Org="ISBN:3540769269" Paper_ID="/310461.html" Extracted="3540769269" />
</rec>
<rec ID="/624109.html" Type="article" CiteSeer_Book="Journal of the ACM" CiteSeer_Volume="41" Title="On Binary Constraint Problems,">
<identifier Org="ISBN:0262511290" Paper_ID="/624109.html" Extracted="0262511290" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0444527265" Paper_ID="/624109.html" Extracted="0444527265" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.0625" />
<identifier Org="ISBN:0821806114" Paper_ID="/624109.html" Extracted="0821806114" DDC="006.3/0151" Normalized_DDC="00630151" Normalized_Weight="0.0625" />
<identifier Org="ISBN:1586030132" Paper_ID="/624109.html" Extracted="1586030132" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:1586034529" Paper_ID="/624109.html" Extracted="1586034529" />
<identifier Org="ISBN:3540198520" Paper_ID="/624109.html" Extracted="3540198520" DDC="005.101512" Normalized_DDC="005101512" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540228179" Paper_ID="/624109.html" Extracted="3540228179" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540250484" Paper_ID="/624109.html" Extracted="3540250484" DDC="006.3/32" Normalized_DDC="006332" Normalized_Weight="0.0625" />
<identifier Org="ISBN:354028964X" Paper_ID="/624109.html" Extracted="354028964X" DDC="910.285" Normalized_DDC="910285" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540410538" Paper_ID="/624109.html" Extracted="3540410538" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540573224" Paper_ID="/624109.html" Extracted="3540573224" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540578021" Paper_ID="/624109.html" Extracted="3540578021" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540637532" Paper_ID="/624109.html" Extracted="3540637532" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540677976" Paper_ID="/624109.html" Extracted="3540677976" DDC="004/.01/5113" Normalized_DDC="004015113" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540735399" Paper_ID="/624109.html" Extracted="3540735399" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.0625" />
<identifier Org="ISBN:3540749144" Paper_ID="/624109.html" Extracted="3540749144" DDC="004.01/5113" Normalized_DDC="004015113" Normalized_Weight="0.0625" />
<identifier Org="ISBN:427490525X" Paper_ID="/624109.html" Extracted="427490525X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.0625" />
</rec>
<rec ID="/188359.html" Type="techreport" CiteSeer_Book="" CiteSeer_Volume="" Title="Reasoning about Temporal Relations: {A} Maximal Tractable Subclass of Allen's Interval Algebra,">
<identifier Org="ISBN:0262611023" Paper_ID="/188359.html" Extracted="0262611023" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0444527265" Paper_ID="/188359.html" Extracted="0444527265" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1558604804" Paper_ID="/188359.html" Extracted="1558604804" />
<identifier Org="ISBN:3540250484" Paper_ID="/188359.html" Extracted="3540250484" DDC="006.3/32" Normalized_DDC="006332" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540287612" Paper_ID="/188359.html" Extracted="3540287612" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540325298" Paper_ID="/188359.html" Extracted="3540325298" DDC="511.313" Normalized_DDC="511313" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540410538" Paper_ID="/188359.html" Extracted="3540410538" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540424644" Paper_ID="/188359.html" Extracted="3540424644" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540578021" Paper_ID="/188359.html" Extracted="3540578021" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:354064993X" Paper_ID="/188359.html" Extracted="354064993X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:354066548X" Paper_ID="/188359.html" Extracted="354066548X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540666265" Paper_ID="/188359.html" Extracted="3540666265" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540734198" Paper_ID="/188359.html" Extracted="3540734198" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540735798" Paper_ID="/188359.html" Extracted="3540735798" DDC="004" Normalized_DDC="004" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540769269" Paper_ID="/188359.html" Extracted="3540769269" />
<identifier Org="ISBN:427490525X" Paper_ID="/188359.html" Extracted="427490525X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
</rec>
<rec ID="/15309.html" Type="article" CiteSeer_Book="Journal of Artificial Intelligence Research" CiteSeer_Volume="4" Title="The Design and Experimental Analysis of Algorithms for Temporal Reasoning,">
<identifier Org="ISBN:0444514937" Paper_ID="/15309.html" Extracted="0444514937" DDC="005.75" Normalized_DDC="00575" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0444527265" Paper_ID="/15309.html" Extracted="0444527265" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:0792347161" Paper_ID="/15309.html" Extracted="0792347161" />
<identifier Org="ISBN:0819457981" Paper_ID="/15309.html" Extracted="0819457981" DDC="621.36/7" Normalized_DDC="621367" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1586034847" Paper_ID="/15309.html" Extracted="1586034847" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:1605666181" Paper_ID="/15309.html" Extracted="1605666181" DDC="006.7/6" Normalized_DDC="00676" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540228179" Paper_ID="/15309.html" Extracted="3540228179" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540325298" Paper_ID="/15309.html" Extracted="3540325298" DDC="511.313" Normalized_DDC="511313" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540404554" Paper_ID="/15309.html" Extracted="3540404554" DDC="670/.285/63" Normalized_DDC="67028563" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540422196" Paper_ID="/15309.html" Extracted="3540422196" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540433465" Paper_ID="/15309.html" Extracted="3540433465" DDC="003/.54" Normalized_DDC="00354" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:354064993X" Paper_ID="/15309.html" Extracted="354064993X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540673504" Paper_ID="/15309.html" Extracted="3540673504" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540745726" Paper_ID="/15309.html" Extracted="3540745726" DDC="004.6" Normalized_DDC="0046" Normalized_Weight="0.07142857142857142" />
<identifier Org="ISBN:3540749691" Paper_ID="/15309.html" Extracted="3540749691" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.07142857142857142" />
</rec>
<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Solving Hard Qualitative Temporal Reasoning Problems: Evaluating the Efficiency of Using the ORD-Horn Class">
<identifier Org="ISBN:0444514937" Paper_ID="SELF" Extracted="0444514937" DDC="005.75" Normalized_DDC="00575" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:0444527265" Paper_ID="SELF" Extracted="0444527265" DDC="005.1/16" Normalized_DDC="005116" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:0792347161" Paper_ID="SELF" Extracted="0792347161" />
<identifier Org="ISBN:1558604804" Paper_ID="SELF" Extracted="1558604804" />
<identifier Org="ISBN:3486272128" Paper_ID="SELF" Extracted="3486272128" />
<identifier Org="ISBN:3540228179" Paper_ID="SELF" Extracted="3540228179" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540426132" Paper_ID="SELF" Extracted="3540426132" DDC="910./285" Normalized_DDC="910285" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540429603" Paper_ID="SELF" Extracted="3540429603" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540433465" Paper_ID="SELF" Extracted="3540433465" DDC="003/.54" Normalized_DDC="00354" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540646035" Paper_ID="SELF" Extracted="3540646035" DDC="003/.54" Normalized_DDC="00354" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:354064993X" Paper_ID="SELF" Extracted="354064993X" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540673504" Paper_ID="SELF" Extracted="3540673504" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.1111111111111111" />
<identifier Org="ISBN:3540769269" Paper_ID="SELF" Extracted="3540769269" />
</rec>
</references_metadata>