{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:50Z","timestamp":1760202650391,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642294136"},{"type":"electronic","value":"9783642294143"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29414-3_6","type":"book-chapter","created":{"date-parts":[[2012,4,24]],"date-time":"2012-04-24T21:45:41Z","timestamp":1335303941000},"page":"79-102","source":"Crossref","is-referenced-by-count":2,"title":["The Importance of the Past in Interval Temporal Logics: The Case of Propositional Neighborhood Logic"],"prefix":"10.1007","author":[{"given":"Dario","family":"Della Monica","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelo","family":"Montanari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pietro","family":"Sala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"11","key":"6_CR1","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"J. Allen","year":"1983","unstructured":"Allen, J.: Maintaining knowledge about temporal intervals. Communications of the ACM\u00a026(11), 832\u2013843 (1983)","journal-title":"Communications of the ACM"},{"key":"6_CR2","volume-title":"Modal Logic","author":"P. Blackburn","year":"2002","unstructured":"Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. Cambridge University Press, Cambridge (2002)"},{"key":"6_CR3","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1007\/978-3-540-89439-1_41","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"D. Bresolin","year":"2008","unstructured":"Bresolin, D., Della Monica, D., Goranko, V., Montanari, A., Sciavicco, G.: Decidable and Undecidable Fragments of Halpern and Shoham\u2019s Interval Temporal Logic: Towards a Complete Classification. In: Cervesato, I., Veith, H., Voronkov, A. (eds.) LPAR 2008. LNCS (LNAI), vol.\u00a05330, pp. 590\u2013604. Springer, Heidelberg (2008)"},{"issue":"1","key":"6_CR4","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1093\/logcom\/exn063","volume":"20","author":"D. Bresolin","year":"2010","unstructured":"Bresolin, D., Goranko, V., Montanari, A., Sala, P.: Tableaux for logics of subinterval structures over dense orderings. Journal of Logic and Computation\u00a020(1), 133\u2013166 (2010)","journal-title":"Journal of Logic and Computation"},{"issue":"3","key":"6_CR5","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.apal.2009.07.003","volume":"161","author":"D. Bresolin","year":"2009","unstructured":"Bresolin, D., Goranko, V., Montanari, A., Sciavicco, G.: Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions. Annals of Pure and Applied Logic\u00a0161(3), 289\u2013304 (2009)","journal-title":"Annals of Pure and Applied Logic"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/978-3-540-70918-3_47","volume-title":"STACS 2007","author":"D. Bresolin","year":"2007","unstructured":"Bresolin, D., Montanari, A., Sala, P.: An Optimal Tableau-Based Decision Algorithm for Propositional Neighborhood Logic. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 549\u2013560. Springer, Heidelberg (2007)"},{"key":"6_CR7","series-title":"LNAI","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-642-22119-4_8","volume-title":"Automated Reasoning with Analytic Tableaux and Related Methods","author":"D. Bresolin","year":"2011","unstructured":"Bresolin, D., Montanari, A., Sala, P., Sciavicco, G.: Optimal Tableau Systems for Propositional Neighborhood Logic over All, Dense, and Discrete Linear Orders. In: Br\u00fcnnler, K., Metcalfe, G. (eds.) TABLEAUX 2011. LNCS (LNAI), vol.\u00a06793, pp. 73\u201387. Springer, Heidelberg (2011)"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Bresolin, D., Montanari, A., Sala, P., Sciavicco, G.: What\u2019s decidable about Halpern and Shoham\u2019s interval logic? The maximal fragment $\\mathsf{AB \\overline{BL}}$ . In: Proc. of the 26th Symposium on Logic in Computer Science, pp. 387\u2013396. IEEE Computer Society Press (2011)","DOI":"10.1109\/LICS.2011.35"},{"issue":"1-3","key":"6_CR9","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s10817-006-9051-0","volume":"38","author":"D. Bresolin","year":"2007","unstructured":"Bresolin, D., Montanari, A., Sciavicco, G.: An optimal decision procedure for Right Propositional Neighborhood Logic. Journal of Automated Reasoning\u00a038(1-3), 173\u2013199 (2007)","journal-title":"Journal of Automated Reasoning"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Emerson, E.A.: Temporal and modal logic. In: Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pp. 995\u20131072. Elsevier, MIT Press (1990)","DOI":"10.1016\/B978-0-444-88074-1.50021-4"},{"key":"6_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/3-540-51803-7_36","volume-title":"Temporal Logic in Specification","author":"D.M. Gabbay","year":"1989","unstructured":"Gabbay, D.M.: The Declarative Past and Imperative Future: Executable Temporal Logic for Interactive Systems. In: Banieqbal, B., Pnueli, A., Barringer, H. (eds.) Temporal Logic in Specification. LNCS, vol.\u00a0398, pp. 409\u2013448. Springer, Heidelberg (1989)"},{"key":"6_CR12","series-title":"Lecture Notes in Logic","first-page":"89","volume-title":"Logic Colloquium 90","author":"D.M. Gabbay","year":"1993","unstructured":"Gabbay, D.M., Hodkinson, I.M., Reynolds, M.A.: Temporal expressive completeness in the presence of gaps. In: V\u00e4\u00e4n\u00e4nen, J., Oikkonen, J. (eds.) Logic Colloquium 90. Lecture Notes in Logic, vol.\u00a02, pp. 89\u2013121. Springer, Heidelberg (1993)"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Gabbay, D.M., Pnueli, A., Shelah, S., Stavi, J.: On the temporal basis of fairness. In: Proc. of the 7th Annual ACM Symposium on Principles of Programming Languages, pp. 163\u2013173 (1980)","DOI":"10.1145\/567446.567462"},{"issue":"1-2","key":"6_CR14","doi-asserted-by":"publisher","first-page":"9","DOI":"10.3166\/jancl.14.9-54","volume":"14","author":"V. Goranko","year":"2004","unstructured":"Goranko, V., Montanari, A., Sciavicco, G.: A road map of interval temporal logics and duration calculi. Journal of Applied Non-Classical Logics\u00a014(1-2), 9\u201354 (2004)","journal-title":"Journal of Applied Non-Classical Logics"},{"issue":"4","key":"6_CR15","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1145\/115234.115351","volume":"38","author":"J. Halpern","year":"1991","unstructured":"Halpern, J., Shoham, Y.: A propositional modal logic of time intervals. Journal of the ACM\u00a038(4), 935\u2013962 (1991)","journal-title":"Journal of the ACM"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Laroussinie, F., Markey, N., Schnoebelen, P.: Temporal logic with forgettable past. In: Proc. of the 17th Symposium on Logic in Computer Science, pp. 383\u2013392. IEEE Computer Society Press (2002)","DOI":"10.1109\/LICS.2002.1029846"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/3-540-15648-8_16","volume-title":"Logics of Programs","author":"O. Lichtenstein","year":"1985","unstructured":"Lichtenstein, O., Pnueli, A., Zuck, L.D.: The Glory of the Past. In: Parikh, R. (ed.) Logic of Programs 1985. LNCS, vol.\u00a0193, pp. 196\u2013218. Springer, Heidelberg (1985)"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/3-540-44464-5_21","volume-title":"Advances in Computing Science - ASIAN 2000","author":"K. Lodaya","year":"2000","unstructured":"Lodaya, K.: Sharpening the Undecidability of Interval Temporal Logic. In: Kleinberg, R.D., Sato, M. (eds.) ASIAN 2000. LNCS, vol.\u00a01961, pp. 290\u2013298. Springer, Heidelberg (2000)"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Maler, O., Pnueli, A.: Tight bounds on the complexity of cascaded decomposition of automata. In: Proc. of the 31st Annual Symposium on Foundations of Computer Science, vol.\u00a0II, pp. 672\u2013682. IEEE Computer Society Press (1990)","DOI":"10.1109\/FSCS.1990.89589"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Marcinkowski, J., Michaliszyn, J.: The ultimate undecidability result for the Halpern-Shoham logic. In: Proc. of the 26th Symposium on Logic in Computer Science, pp. 377\u2013386. IEEE Computer Society Press (2011)","DOI":"10.1109\/LICS.2011.21"},{"key":"6_CR21","first-page":"122","volume":"79","author":"N. Markey","year":"2003","unstructured":"Markey, N.: Temporal logic with past is exponentially more succinct. Bulletin of the EATCS\u00a079, 122\u2013128 (2003)","journal-title":"Bulletin of the EATCS"},{"key":"6_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-642-04027-6_29","volume-title":"Computer Science Logic","author":"A. Montanari","year":"2009","unstructured":"Montanari, A., Puppis, G., Sala, P.: A Decidable Spatial Logic with Cone-Shaped Cardinal Directions. In: Gr\u00e4del, E., Kahle, R. (eds.) CSL 2009. LNCS, vol.\u00a05771, pp. 394\u2013408. Springer, Heidelberg (2009)"},{"key":"6_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-642-14162-1_29","volume-title":"Automata, Languages and Programming","author":"A. Montanari","year":"2010","unstructured":"Montanari, A., Puppis, G., Sala, P.: Maximal Decidable Fragments of Halpern and Shoham\u2019s Modal Logic of Intervals. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part II. LNCS, vol.\u00a06199, pp. 345\u2013356. Springer, Heidelberg (2010)"},{"key":"6_CR24","unstructured":"Moszkowski, B.: Reasoning about digital circuits. Tech. rep. stan-cs-83-970, Dept. of Computer Science, Stanford University, Stanford, CA (1983)"},{"issue":"2","key":"6_CR25","doi-asserted-by":"publisher","first-page":"685","DOI":"10.2307\/2695037","volume":"66","author":"M. Otto","year":"2001","unstructured":"Otto, M.: Two variable first-order logic over ordered domains. Journal of Symbolic Logic\u00a066(2), 685\u2013702 (2001)","journal-title":"Journal of Symbolic Logic"},{"issue":"8","key":"6_CR26","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1016\/j.apal.2010.01.002","volume":"161","author":"M. Reynolds","year":"2010","unstructured":"Reynolds, M.: The complexity of temporal logic over the reals. Annals of Pure and Applied Logic\u00a0161(8), 1063\u20131096 (2010)","journal-title":"Annals of Pure and Applied Logic"},{"key":"6_CR27","unstructured":"Shapirovsky, I.: On PSPACE-decidability in Transitive Modal Logic. In: Advances in Modal Logic, vol.\u00a05, pp. 269\u2013287. King\u2019s College Publications (2005)"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Automata on infinite objects. In: Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pp. 133\u2013192. Elsevier, MIT Press (1990)","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"issue":"3","key":"6_CR29","doi-asserted-by":"publisher","first-page":"549","DOI":"10.2307\/2272895","volume":"39","author":"S.K. Thomason","year":"1974","unstructured":"Thomason, S.K.: Reduction of tense logic to modal logic I. Journal of Symbolic Logic\u00a039(3), 549\u2013551 (1974)","journal-title":"Journal of Symbolic Logic"},{"issue":"3","key":"6_CR30","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1111\/j.1755-2567.1975.tb00555.x","volume":"41","author":"S.K. Thomason","year":"1975","unstructured":"Thomason, S.K.: Reduction of tense logic to modal logic II. Theoria\u00a041(3), 154\u2013169 (1975)","journal-title":"Theoria"},{"issue":"4","key":"6_CR31","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1093\/logcom\/1.4.453","volume":"1","author":"Y. Venema","year":"1991","unstructured":"Venema, Y.: A modal logic for chopping intervals. Journal of Logic and Computation\u00a01(4), 453\u2013476 (1991)","journal-title":"Journal of Logic and Computation"}],"container-title":["Lecture Notes in Computer Science","Logic Programs, Norms and Action"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29414-3_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T14:40:30Z","timestamp":1743000030000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29414-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642294136","9783642294143"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29414-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}