Time Structures: Formal Description and Algorithmic Representation

Cover
Springer Science & Business Media, 20.03.1996 - 244 Seiten
The notion of time plays an important role in modern science. In computer science and artificial intelligence, the parameter of time is of particular importance, e.g. for planning robot activity, natural language processing, and time-varying scene analysis. This work investigates the relationship between classic, first-order theories of point- and interval-based time structures, modal logics of corresponding structures, and their algorithmic representations. To make this relationship complete, a formalisation of Allen's famous algorithm, applicable to various structures of time, is presented along with its translation to modal logics. All in all, the book is a competent and comprehensive analysis of logical descriptions and algorithmic representations of time structures.
 

Ausgewählte Seiten

Inhalt

Introduction
1
11 Basic time notions
3
112 Events
4
113 Actions
5
114 Processes
6
12 Time notions in artificial intelligence
8
122 Natural language processing
11
123 Timevarying scene analysis
15
433 Relativistic point time
118
434 Metric point time
119
435 Linear interval time
127
436 Nonlinear interval time
129
437 Linear intervalpoint time
136
44 Extensions and modifications of Allens constraint propagation algorithm
139
442 Metric information for intervalpoint time
141
443 Representing the present in the constraint propagation algorithm
142

124 Temporal databases
17
125 Program specification and verification
19
Description of time structures in the first order predicate calculus
21
21 Point structures
22
211 Nonlinear point time structures
23
212 Metric point time structures
26
213 Cyclic time structures
29
214 Defining intervals in point structures
30
22 Interval structures
32
222 Allen Hayess axiomatization
34
223 Tsangs axiomatization
38
224 Comparison of axiomatizations of interval structures
40
225 Nonlinear interval time structures
45
226 Defining points in interval structures
59
Modal temporal logics and description of time structures
61
31 Point time
62
312 Additional operators for structure specification
65
313 Operators Since and Until
68
314 Metric tense logic
71
32 Interval time
75
322 Halpern Shohams modal logic of time intervals
79
323 Comparison of extended tense logic and Halpern Shohams logic
89
324 Nonlinear time in extended tense logic
101
Temporal reasoning algorithms
107
42 Allens constraint propagation algorithm for relations between intervals
109
43 Application of the constraint propagation algorithm to different sets of relations
113
432 Nonlinear point time
114
444 Absolute duration of events
144
445 Relative duration of events
145
446 Interval relation network with distinguished transition chains
148
447 A more precise constraint propagation algorithm
151
45 Constraint propagation for a distinguished interval
155
46 Consistent Labeling Problem for interval relations
156
47 Efficient algorithms for representation of relations between points
158
48 Representation of collections of intervals
163
Formalization of the constraint propagation algorithm
167
52 The basis of direct formalization of constraint propagation algorithm
168
53 Point calculus for linear time
173
54 Dates in the point calculus
179
55 Point calculus for nonlinear time
180
56 Calculus of distances between points
182
57 Interval calculus for linear time
187
58 Interval calculus for nonlinear time
190
59 Calculus of points and intervals
193
510 A sketch of formalization of a more precise constraint propagation algorithm
195
Translations of Allens calculi into modal temporal logic
199
61 Translation of the point calculus for linear time into instant tense logic
200
62 Translation of the point calculus for nonlinear time into instant tense logic
208
63 Translation of the calculus of distances between points into metric tense logic
210
64 Translation of the interval calculus for linear time into extended tense logic
217
65 Translation of the interval calculus for linear time into Halpern Shohams logic
225
Bibliography
233
Urheberrecht

Andere Ausgaben - Alle anzeigen

Time Structures
Elzbieta Hajnicz
Keine Leseprobe verfügbar - 2014

Häufige Begriffe und Wortgruppen

Allen & Hayes's Artificial Intelligence axiom axiomatization Benthem branch COMP COMPP Computer Conference on Artificial considered constraint propagation algorithm countable set dates defined definition equals exists t₁ extended tense logic fact formalization formula ƒ Hajnicz Halpern & Shoham's Hayes's theory hence holds inference rules INFO International Joint Conference interval calculus interval structures inverse k₁ linear order means metric modal logics modal temporal logics Morgan Kaufmann Publishers non-linear occur operators order predicate calculus partial order point calculus point structure point time structure precedence relation predicate calculus presented in fig presented in section primitive relations Proceedings proof propositional variables r₁ reasoning is analogous relation composition relations between intervals relations between points representation represented rules of inference semantics sequence set of primitive set of relations Shoham's logic subintervals t₁ t₂ temporal databases theorem theory Th translation Tsang's well-formed formulas

Verweise auf dieses Buch

Bibliografische Informationen

TitelTime Structures: Formal Description and Algorithmic Representation
Ausgabe 1047 von Lecture Notes in Artificial Intelligence
Band 1047 von Lecture Notes in Computer Science, ISSN 0302-9743
Band 1047 von Lecture notes in computer science: Lecture notes in artificial intelligence, ISSN 0302-9743
Autor/inElzbieta Hajnicz
HerausgeberElzbieta Hajnicz
Ausgabeillustriert
VerlagSpringer Science & Business Media, 1996
ISBN3540609415, 9783540609414
Länge244 Seiten
  
Zitat exportierenBiBTeX EndNote RefMan