Abstract
We consider the languages of first order-logic (with equality) extended with Allen’s relations for temporal intervals. We give a complete classification of such languages in terms of relative expressive power, thus determining how many, and which, are the intrinsically different extensions of first-order logic with one or more of Allen’s relations. Classifications are obtained for three different classes of interval structures, namely those based on arbitrary, discrete, and dense linear orders. The strict semantics (where point-intervals are excluded) is assumed throughout.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Allen, J.F., Hayes, P.J.: A common-sense theory of time. In: Proceedings of the 9th International Joint Conference on Artificial Intelligence, pp. 528–531. Morgan Kaufmann (1985)
Allen, J.F.: Maintaining knowledge about temporal intervals. Communications of the ACM 26, 832–843 (1983)
Coetzee, C.J.: Representation theorems for classes of interval structures. Master’s thesis, Department of Mathematics, University of Johannesburg (2009)
Goranko, V., Montanari, A.: Sciavicco G. Propositional interval neighborhood temporal logics. Journal of Universal computer science 9(9), 1137–1167 (2003)
Goranko, V., Montanari, A., Sciavicco, G.: A road map of interval temporal logics and duration calculi. Journal of Applied Non-Classical Logics 14(1-2), 9–54 (2004)
Ladkin, P.: The Logic of Time Representation. PhD thesis, University of California, Berkeley (1978)
van Benthem, J.F.A.K.: The logic of time. Synthese Library, vol. 156. D. Reidel Publishing Co., Dordrecht (1983); A model-theoretic investigation into the varieties of temporal ontology and temporal discourse
Venema, Y.: Expressiveness and completeness of an interval tense logic. Notre Dame Journal of Formal Logic 31(4), 529–547 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Conradie, W., Sciavicco, G. (2011). On the Expressive Power of First Order-Logic Extended with Allen’s Relations in the Strict Case. In: Lozano, J.A., Gámez, J.A., Moreno, J.A. (eds) Advances in Artificial Intelligence. CAEPIA 2011. Lecture Notes in Computer Science(), vol 7023. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25274-7_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-25274-7_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25273-0
Online ISBN: 978-3-642-25274-7
eBook Packages: Computer ScienceComputer Science (R0)