Paper Info
Title
The Point Algebra for Branching Time Revisited
Abstract
Temporal reasoning with nonlinear models of time have been used in many areas of artificial intelligence. In this paper we focus on the model of branching time which has been proven successful for problems such as planning. We investigate the computational complexity of the point algebra for branching time extended with disjunctions and show that there are exactly five maximal tractable sets of relations. We also give an improved algorithm for deciding satisfiability of the point algebra with a time complexity comparable to that of path consistency checking algorithms.
Year
DOI
Venue
2001
10.1007/3-540-45422-5_9
KI/ÖGAI
Keywords
Field
DocType
nonlinear model,maximal tractable set,artificial intelligence,point algebra,improved algorithm,branching time revisited,temporal reasoning,path consistency checking algorithm,computational complexity,time complexity,satisfiability,artificial intelligent
Discrete mathematics,Interval algebra,Nonlinear system,Algebra,Computer science,Satisfiability,Decidability,Temporal logic,Time complexity,Computational complexity theory,Branching (version control)
Conference
ISBN
Citations 
PageRank 
3-540-42612-4
2
0.40
References 
Authors
13
1
Name
Order
Citations
PageRank
Mathias Broxvall130125.54