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

Graph

<?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>

www.000webhost.com