×

Allen-like theory of time for tree-like structures. (English) Zbl 1436.03122

Summary: Allen’s Interval Algebra is among the leading formalisms in the area of qualitative temporal reasoning. However, its applications are restricted to linear flows of time. While there is some recent work studying relations between intervals on branching structures, there is no rigorous study of the first-order theory of branching time. In this paper, we approach this problem under a general definition of time structures, namely, tree-like lattices. Allen’s work proved that meets is expressively complete in the linear case. We also prove that, surprisingly, it remains complete for all unbounded tree-like lattices. This does not generalize to the case of all tree-like lattices, for which we prove that the smallest complete set of relations has cardinality three. We provide in this paper a sound and complete axiomatic system for both the unbounded and general case, in Allen’s style, and we classify minimally complete and maximally incomplete sets of relations.

MSC:

03B44 Temporal logic
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Allen, J., Maintaining knowledge about temporal intervals, Commun. ACM, 26, 11, 832-843 (1983) · Zbl 0519.68079
[2] Conradie, W.; Durhan, S.; Sciavicco, G., An integrated first-order theory of points and intervals: expressive power in the class of all linear orders, (Proc. of the 19th International Symposium on Temporal Representation and Reasoning. Proc. of the 19th International Symposium on Temporal Representation and Reasoning, TIME (2012), IEEE), 47-51
[3] Ragni, M.; Wölfl, S., Branching Allen, (Proc. of the 4th International Conference on Spatial Cognition. Proc. of the 4th International Conference on Spatial Cognition, Lect. Notes Comput. Sci., vol. 3343 (2004), Springer), 323-343
[4] Reich, A., Intervals, points, and branching time, (Proc. of the 9th International Symposium on Temporal Representation and Reasoning. Proc. of the 9th International Symposium on Temporal Representation and Reasoning, TIME (1994), IEEE), 121-133
[5] Ladkin, P., Models of axioms for time intervals, (Proc. of the 6th National Conference on Artificial Intelligence (1987), Morgan Kaufmann), 234-239
[6] Galton, A., Note on a lemma of Ladkin, J. Log. Comput., 6, 1, 1-4 (1996) · Zbl 0838.03014
[7] Ligozat, G., On generalized interval calculi, (Proc. of the 9th National Conference on Artificial Intelligence. Proc. of the 9th National Conference on Artificial Intelligence, AAAI (1991)), 234-240
[8] Molinari, A.; Montanari, A.; Murano, A.; Perelli, G.; Peron, A., Checking interval properties of computations, Acta Inform., 56, 6-8, 587-619 (2016) · Zbl 1350.68184
[9] van Benthem, J., The Logic of Time (1991), Kluwer Academic Press
[10] Allen, J.; Hayes, P., A common-sense theory of time, (Proc. of the 9th International Joint Conference on Artificial Intelligence (1985), Morgan Kaufmann), 528-531
[11] Ladkin, P., The Logic of Time Representation (1978), University of California: University of California Berkeley, Ph.D. thesis
[12] Venema, Y., A modal logic for chopping intervals, J. Log. Comput., 1, 4, 453-476 (1991) · Zbl 0744.03022
[13] Goranko, V.; Montanari, A.; Sciavicco, G., Propositional interval neighborhood temporal logics, J. Univers. Comput. Sci., 9, 9, 1137-1167 (2003)
[14] Bochman, A., Concerted instant-interval temporal semantics I: temporal ontologies, Notre Dame J. Form. Log., 31, 3, 403-414 (1990) · Zbl 0718.03018
[15] Coetzee, C. J., Representation Theorems for Classes of Interval Structures (2009), Department of Mathematics, University of Johannesburg, Master’s thesis
[16] Thomason, R., Combination of tense and modality, (Gabbay, D.; Guenthner, F., Handbook of Philosophical Logic, Vol. II (1984)), 135-165 · Zbl 0875.03047
[17] Alur, R.; Henzinger, T.; Kupferman, O., Alternating-time temporal logic, J. ACM, 49, 5, 672-713 (2002) · Zbl 1326.68181
[18] Emerson, E. A., Temporal and modal logic, (Handbook of Theoretical Computer Science, vol. B: Formal Models and Semantics (B) (1990), MIT Press), 995-1072 · Zbl 0900.03030
[19] Bresolin, D.; Montanari, A.; Sala, P., An optimal tableau for right propositional neighborhood logic over trees, (Proc. of the 15th International Symposium on Temporal Representation and Reasoning. Proc. of the 15th International Symposium on Temporal Representation and Reasoning, TIME (2008), IEEE), 110-117
[20] van Kutshera, F., Sebastian’s strolls, Grazer Philosophisce Studien, 45, 75-88 (1993)
[21] Allen, J.; Hayes, P. J., Short time periods, (Proc. of the 10th International Joint Conference on Artificial Intelligence (1987)), 981-983
[22] Conradie, W.; Sciavicco, G., On the expressive power of first order-logic extended with Allen’s relations in the strict case, (Proc. of the 2011 Conferencia Española para la Inteligencia Artificial. Proc. of the 2011 Conferencia Española para la Inteligencia Artificial, CAEPIA. Proc. of the 2011 Conferencia Española para la Inteligencia Artificial. Proc. of the 2011 Conferencia Española para la Inteligencia Artificial, CAEPIA, Lect. Notes Comput. Sci., vol. 7023 (2011), Springer), 173-182
[23] Condotta, J., Tractable sets of the generalized interval algebra, (Proc. of the 14th European Conference on Artificial Intelligence. Proc. of the 14th European Conference on Artificial Intelligence, ECAI (2000)), 78-82
[24] Balbiani, P.; Condotta, J.; Ligozat, G., Reasoning about generalized intervals: Horn representability and tractability, (Proc. of the 7th International Workshop on Temporal Representation and Reasoning. Proc. of the 7th International Workshop on Temporal Representation and Reasoning, TIME (2000)), 23-29
[25] Navarrete, I.; Sattar, A.; Marín, R., Deciding consistency of a point-duration network with metric constraints, (Proc of the 10th International Symposium on Temporal Representation and Reasoning. Proc of the 10th International Symposium on Temporal Representation and Reasoning, TIME (2003)), 147-154
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.