The Ultimate Undecidability Result for the Halpern-Shoham Logic
作者： Jerzy Marcinkowski , Jakub Michaliszyn
DOI: 10.1109/LICS.2011.21
关键词: Multimodal logic 、 Substructural logic 、 Predicate logic 、 Mathematics 、 Intermediate logic 、 Discrete mathematics 、 Higher-order logic 、 Decidability 、 Many-valued logic 、 Dynamic logic (modal logic)
摘要: The Halpern-Shoham logic is a modal of time intervals. Some effort has been put in last ten years to classify fragments this beautiful with respect decidability its satisfiability problem. We complete classification by showing - what we believe quite an unexpected result that the subintervals, fragment Halpern -- Shoham where only operator ``during'', or D, allowed, undecidable over discrete structures. This surprising as this, apparently very simple, decidable dense orders and reflexive variant known be Our subsumes lot previous negative results for case, like undecidability ABE, BD, ADB, so on [2], [5].
ieeecomputersociety.org参考文章(18)
C. L. Hamblin, Instants and intervals. Studium generale; Zeitschrift fur die Einheit der Wissenschaften im Zusammenhang ihrer Begriffsbildungen und Forschungsmethoden. ,vol. 24, pp. 324- 331 ,(1972) , 10.1007/978-3-642-65387-2_23
Thomas Schwentick, Thomas Zeume, Two-Variable Logic with Two Order Relations (Extended Abstract) computer science logic. pp. 499- 513 ,(2010)
Kamal Lodaya, Sharpening the Undecidability of Interval Temporal Logic Lecture Notes in Computer Science. pp. 290- 298 ,(2000) , 10.1007/3-540-44464-5_21
Davide Bresolin, Angelo Montanari, Pietro Sala, Guido Sciavicco, Optimal Tableaux for Right Propositional Neighborhood Logic over Linear Orders european conference on logics in artificial intelligence. ,vol. 5293, pp. 62- 75 ,(2008) , 10.1007/978-3-540-87803-2_7
Angelo Montanari, Gabriele Puppis, Pietro Sala, Maximal Decidable Fragments of Halpern and Shoham’s Modal Logic of Intervals Automata, Languages and Programming. ,vol. 6199, pp. 345- 356 ,(2010) , 10.1007/978-3-642-14162-1_29
Angelo Montanari, Gabriele Puppis, Pietro Sala, A decidable spatial logic with cone-shaped cardinal directions computer science logic. ,vol. 5771, pp. 394- 408 ,(2009) , 10.1007/978-3-642-04027-6_29
Jerzy Marcinkowski, Jakub Michaliszyn, Emanuel Kieroński, B and D Are Enough to Make the Halpern–Shoham Logic Undecidable Automata, Languages and Programming. pp. 357- 368 ,(2010) , 10.1007/978-3-642-14162-1_30
Benjamin Charles Moszkowski, Reasoning about Digital Circuits ,(1983)
Davide Bresolin, Dario Della Monica, Valentin Goranko, Angelo Montanari, Guido Sciavicco, Decidable and Undecidable Fragments of Halpern and Shoham's Interval Temporal Logic: Towards a Complete Classification international conference on logic programming. ,vol. 5330, pp. 590- 604 ,(2008) , 10.1007/978-3-540-89439-1_41
Joseph Y. Halpern, Yoav Shoham, A propositional modal logic of time intervals Journal of the ACM. ,vol. 38, pp. 935- 962 ,(1991) , 10.1145/115234.115351