The Undecidability of the Logic of Subintervals

• Autorzy: Marcinkowski J. , Michaliszyn J.

Identyfikatory

DOI

10.3233/FI-2014-1011

• Języki publikacji: EN

Abstrakty

EN

The Halpern–Shoham logic is a modal logic of time intervals. Some effort has been put in last ten years to classify fragments of this beautiful logic with respect to decidability of its satisfiability problem. We complete this classification by showing — what we believe is quite an unexpected result—that the logic of subintervals, the fragment of the Halpern–Shoham logic where only the operator “during”, or D, is allowed, is undecidable over discrete structures. This is surprising as this, apparently very simple, logic is decidable over dense orders and its reflexive variant is known to be decidable over discrete structures. Our result subsumes a lot of previous undecidability results of fragments that include D.

Słowa kluczowe

EN

Halpern–Shoham logic; logic of subintervals; undecidable logic

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 131, nr 2
• Strony: 217--240
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Marcinkowski J.

• Institute of Computer Science, University Of Wrocław, Poland

autor

Michaliszyn J.

• Institute of Computer Science, University Of Wrocław, Poland

Bibliografia

• [1] Allen, J. F.: Maintaining knowledge about temporal intervals, Commun. ACM, 26(11), November 1983, 832–843, ISSN 0001-0782.
• [2] Berger, R.: The undecidability of the domino problem, Mem. AMS, 66, 1966.
• [3] Bresolin, D., Della Monica, D., Goranko, V., Montanari, A., Sciavicco, G.: Decidable and Undecidable Fragments of Halpern and Shohams Interval Temporal Logic: Towards a Complete Classification, in: Logic for Programming, Artificial Intelligence, and Reasoning, vol. 5330 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2008, 590–604, 10.1007/978-3-540-89439-1 41.
• [4] Bresolin, D., Goranko, V., Montanari, A., Sala, P.: Tableau-based decision procedures for the logics of subinterval structures over dense orderings, Journal of Logic and Computation, 2008.
• [5] Bresolin, D., Goranko, V., Montanari, A., Sciavicco, G.: Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions, Annals of Pure and Applied Logic, 161, 2009, 289–304.
• [6] Bresolin, D., Monica, D. D., Goranko, V., Montanari, A., Sciavicco, G.: The Dark Side of Interval Temporal Logic: Sharpening the Undecidability Border, Proceedings of the 2011 Eighteenth International Symposium on Temporal Representation and Reasoning, TIME ’11, IEEE Computer Society, Washington, DC, USA, 2011, ISBN 978-0-7695-4508-0.
• [7] Bresolin, D., Montanari, A., Sala, P., Sciavicco, G.: Optimal Tableaux for Right Propositional Neighborhood Logic over Linear Orders, Logics in Artificial Intelligence, 2008.
• [8] Goranko, V., Montanari, A., Sciavicco, G.: A Road Map of Interval Temporal Logics and Duration Calculi, Journal of Applied Non-classical Logics, 14, 2004, 9–54.
• [9] Goranko, V., Passy, S.: Using the Universal Modality: Gains and Questions, Journal of Logic and Computation, 2(1), 1992, 5–30.
• [10] Gurevich, Y. S., Koryakov, I. O.: Remarks on Berger’s paper on the domino problem, Siberian Mathematical Journal, 13, 1972, 319–321.
• [11] Halpern, J. Y., Shoham, Y.: A propositional modal logic of time intervals, Journal of The ACM, 38, 1991, 935–962.
• [12] Hamblin, C. L.: Instants and intervals, Studium Generale, 27, 1971, 127–134.
• [13] Hemaspaandra, E.: The Price of Universality, Notre Dame Journal of Formal Logic, 37, 1996, 174–203.
• [14] Lodaya, K.: Sharpening the Undecidability of Interval Temporal Logic, Asian Computing Science Conference, 2000.
• [15] Marcinkowski, J., Michaliszyn, J., Kieronski, E.: B and D Are Enough to Make the Halpern-Shoham Logic Undecidable, ICALP (2) (S. Abramsky, C. Gavoille, C. Kirchner, F. M. auf der Heide, P. G. Spirakis, Eds.), 6199, Springer, 2010.
• [16] Monica, D. D., Goranko, V., Montanari, A., Sciavicco, G.: Expressiveness of the interval logics of Allen’s relations on the class of all linear orders: complete classification, Proceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume Two, IJCAI’11, AAAI Press, 2011, ISBN 978-1-57735-514-4.
• [17] Montanari, A., Pratt-Hartmann, I., Sala, P.: Decidability of the Logics of the Reflexive Sub-interval and Super-interval Relations over Finite Linear Orders, International Syposium on Temporal Representation and Reasoning, 2010, 27–34, ISSN 1530-1311.
• [18] Montanari, A., Puppis, G., Sala, P.: A decidable spatial logic with cone-shaped cardinal directions, Proceedings of the 23rd CSL international conference and 18th EACSL Annual conference on Computer science logic, CSL’09/EACSL’09, Springer-Verlag, Berlin, Heidelberg, 2009, ISBN 3-642-04026-8, 978-3-642-04026-9.
• [19] Montanari, A., Puppis, G., Sala, P.: Maximal Decidable Fragments of Halpern and Shoham’s Modal Logic of Intervals., ICALP (2) (S. Abramsky, C. Gavoille, C. Kirchner, F. M. auf der Heide, P. G. Spirakis, Eds.), 6199, Springer, 2010, ISBN 978-3-642-14161-4.
• [20] Moszkowski, B. C.: Reasoning about digital circuits, Ph.D. Thesis, Stanford University, Stanford, CA, USA, 1983.
• [21] Parikh, R.: A decidability result for a second order process logic, Proceedings of the 19th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA, 1978.
• [22] Pratt, V. R.: Process logic: preliminary report, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, POPL ’79, ACM, New York, NY, USA, 1979.
• [23] Schwentick, T., Zeume, T.: Two-Variable Logic with Two Order Relations, in: Computer Science Logic (A. Dawar, H. Veith, Eds.), vol. 6247 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2010, 499–513, 10.1007/978-3-642-15205-4 38.