Abstract
We consider a new fragment of first-order logic with two variables. This logic is defined over interval structures. It constitutes unary predicates, a binary predicate and a function symbol. Considering such a fragment of first-order logic is motivated by defining a general framework for event-based interval temporal logics. In this paper, we present a sound, complete and terminating decision procedure for this logic. We show that the logic is decidable, and provide a NEXPTIME complexity bound for satisfiability. This result shows that even a simple decidable fragment of first-order logic has NEXPTIME complexity.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andreka, H., van Benthem, J., & Nemeti, I. (1996). Modal languges and Bounded Fragments of Predicate Logic. Research Report ML-96-03, IILC.
Dechter R., Meiri I., Pearl J. (1991) Temporal constraint networks. Artificial Intelligence 49: 61–95
Goranko V., Montanari A., Sciavicco G. (2003) Propositional interval neighborhood temporal logics. Journal of Universal Computer Science 9(9): 1137–1167
Goranko V., Montanari A., Sciavicco G., Sala P. (2006) A general Tableau method for propositional interval temporal logics: Theory and implementation. Journal of Applied Logic 4(3): 305–330
Grädel E. (1999) On the restraining power of guards. Journal of Symbolic Logic 64: 1719–1742
Grädel E., Kolaitis P., Vardi M. (1997) On the decision problem for two-variable first-order logic. Bulletin of Symbolic Logic 3: 53–69
Grädel E., Otto M. (1999) On logics with two variables. Theoretical Computer Science 224: 73–113
Halpern J.Y., Shoham Y. (1991) A propositional modal logic of time intervals. Journal of the ACM 38(4): 935–962
Konur S. (2008) An interval logic for natural language semantics. Advances in Modal Logic 7: 177–191
Mortimer M. (1975) On languages with two variables. Zeitschr. f. math. Logik u. Grundlagen d. Math. 21: 135–140
Moszkowski, B. (1983). Reasoning about digital circuits. Stanford University: PhD Thesis, Department of Computer Science.
Otto M. (2001) Two variable first-order logic over ordered domains. Journal of Symbolic Logic 66(2): 685–702
Pratt-Hartmann I. (2005) Temporal prepositions and their logic. Artificial Intelligence 166(1–2): 1–36
van Benthem, J. (1997). Dynamic Bits and Pieces. Research Report, ILLC.
Venema Y. (1991) A modal logic for choppping intervals. Journal of Logic and Computation 1: 453–476
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Konur, S. An Event-Based Fragment of First-Order Logic over Intervals. J of Log Lang and Inf 20, 49–68 (2011). https://doi.org/10.1007/s10849-010-9126-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10849-010-9126-5