{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:31Z","timestamp":1760202691915},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,5,14]],"date-time":"2015-05-14T00:00:00Z","timestamp":1431561600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s00236-015-0231-4","type":"journal-article","created":{"date-parts":[[2015,5,13]],"date-time":"2015-05-13T16:48:50Z","timestamp":1431535730000},"page":"207-246","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["A complete classification of the expressiveness of interval logics of Allen\u2019s relations: the general and the dense cases"],"prefix":"10.1007","volume":"53","author":[{"given":"Luca","family":"Aceto","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dario","family":"Della Monica","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentin","family":"Goranko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Ing\u00f3lfsd\u00f3ttir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelo","family":"Montanari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guido","family":"Sciavicco","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,5,14]]},"reference":[{"key":"231_CR1","doi-asserted-by":"crossref","unstructured":"Aceto, L., Della Monica, D., Ing\u00f3lfsd\u00f3ttir, A., Montanari, A., Sciavicco, G.: An algorithm for enumerating maximal models of Horn theories with an application to modal logics. In: Proceedings of the 19th LPAR, LNCS, vol. 8312, pp. 1\u201317. Springer (2013)","DOI":"10.1007\/978-3-642-45221-5_1"},{"key":"231_CR2","doi-asserted-by":"crossref","unstructured":"Aceto, L., Della Monica, D., Ing\u00f3lfsd\u00f3ttir, A., Montanari, A., Sciavicco, G.: A complete classification of the expressiveness of interval logics of Allen\u2019s relations over dense linear orders. In: Proceedings of the 20th TIME, pp. 65\u201372. IEEE Computer Society (2013)","DOI":"10.1109\/TIME.2013.16"},{"key":"231_CR3","doi-asserted-by":"crossref","unstructured":"Aceto, L., Della Monica, D., Ing\u00f3lfsd\u00f3ttir, A., Montanari, A., Sciavicco, G.: On the expressiveness of the interval logic of Allen\u2019s relations over finite and discrete linear orders. In: Ferm\u00e9, E., Leite, J. (eds.) Proceedings of the 14th JELIA, LNAI, vol. 8761, pp. 267\u2013281. Springer (2014)","DOI":"10.1007\/978-3-319-11558-0_19"},{"issue":"11","key":"231_CR4","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"JF Allen","year":"1983","unstructured":"Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832\u2013843 (1983)","journal-title":"Commun. ACM"},{"issue":"2","key":"231_CR5","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0004-3702(84)90008-0","volume":"23","author":"JF Allen","year":"1984","unstructured":"Allen, J.F.: Towards a general theory of action and time. Artif. Intell. 23(2), 123\u2013154 (1984)","journal-title":"Artif. Intell."},{"key":"231_CR6","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.entcs.2011.10.004","volume":"278","author":"P Balbiani","year":"2011","unstructured":"Balbiani, P., Goranko, V., Sciavicco, G.: Two-sorted point-interval temporal logics. Electron. Notes Theor. Comput. Sci. 278, 31\u201345 (2011)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"231_CR7","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":"231_CR8","doi-asserted-by":"crossref","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: Proceedings of the 15th LPAR, LNCS, vol. 5330, pp. 590\u2013604. Springer (2008)","DOI":"10.1007\/978-3-540-89439-1_41"},{"issue":"2","key":"231_CR9","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10270-011-0195-y","volume":"12","author":"D Bresolin","year":"2013","unstructured":"Bresolin, D., Della Monica, D., Goranko, V., Montanari, A., Sciavicco, G.: Metric propositional neighborhood interval logics on natural numbers. Softw. Syst. Model. 12(2), 245\u2013264 (2013)","journal-title":"Softw. Syst. Model."},{"issue":"1\u20133","key":"231_CR10","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s10472-013-9376-4","volume":"71","author":"D Bresolin","year":"2014","unstructured":"Bresolin, D., Della Monica, D., Goranko, V., Montanari, A., Sciavicco, G.: The dark side of interval temporal logic: marking the undecidability border. Ann. Math. Artif. Intell. 71(1\u20133), 41\u201383 (2014)","journal-title":"Ann. Math. Artif. Intell."},{"key":"231_CR11","doi-asserted-by":"crossref","unstructured":"Bresolin, D., Della Monica, D., Montanari, A., Sala, P., Sciavicco, G.: Interval temporal logics over finite linear orders: the complete picture. In: Proceedings of the 20th ECAI, pp. 199\u2013204 (2012)","DOI":"10.4204\/EPTCS.96.12"},{"key":"231_CR12","doi-asserted-by":"crossref","unstructured":"Bresolin, D., Della Monica, D., Montanari, A., Sala, P., Sciavicco, G.: Interval temporal logics over strongly discrete linear orders: the complete picture. In: Proceedings of the 3rd GandALF, vol. 96, pp. 155\u2013168. EPTCS (2012)","DOI":"10.4204\/EPTCS.96.12"},{"issue":"1","key":"231_CR13","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1093\/logcom\/exn063","volume":"20","author":"D Bresolin","year":"2010","unstructured":"Bresolin, D., Goranko, V., Montanari, A., Sala, P.: Tableau-based decision procedures for the logics of subinterval structures over dense orderings. J. Log. Comput. 20(1), 133\u2013166 (2010)","journal-title":"J. Log. Comput."},{"issue":"3","key":"231_CR14","doi-asserted-by":"crossref","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. Ann. Pure Appl. Log. 161(3), 289\u2013304 (2009)","journal-title":"Ann. Pure Appl. Log."},{"key":"231_CR15","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 abbl. In: Proceedings of the 26th LICS, pp. 387\u2013396. IEEE Computer Society (2011)","DOI":"10.1109\/LICS.2011.35"},{"issue":"3","key":"231_CR16","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1142\/S012905411240028X","volume":"23","author":"D Bresolin","year":"2012","unstructured":"Bresolin, D., Sala, P., Sciavicco, G.: On begins, meets, and before. Int. J. Found. Comput. Sci. 23(3), 559\u2013583 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"231_CR17","doi-asserted-by":"crossref","unstructured":"Conradie, W., Sciavicco, G.: On the expressive power of first order-logic extended with Allen\u2019s relations in the strict case. In: Proceedings of the 14th CAEPIA, LNCS, vol. 7023, pp. 173\u2013182. Springer (2011)","DOI":"10.1007\/978-3-642-25274-7_18"},{"key":"231_CR18","unstructured":"Della Monica, D., Goranko, V., Montanari, A., Sciavicco, G.: Expressiveness of the interval logics of Allen\u2019s relations on the class of all linear orders: complete classification. In: Proceedings of the 22nd IJCAI, pp. 845\u2013850 (2011)"},{"key":"231_CR19","first-page":"73","volume":"105","author":"D Monica","year":"2011","unstructured":"Monica, D., Goranko, V., Montanari, A., Sciavicco, G.: Interval temporal logics: a journey. Bull. Eur. Assoc. Theor. Comput. Sci. 105, 73\u201399 (2011)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"231_CR20","first-page":"995","volume-title":"Handbook of Theoretical Computer Science, vol. B: Formal Models and Semantics","author":"EA Emerson","year":"1990","unstructured":"Emerson, E.A.: Temporal and modal logic. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. B: Formal Models and Semantics, pp. 995\u20131072. MIT Press, Cambridge (1990)"},{"key":"231_CR21","doi-asserted-by":"crossref","unstructured":"Gennari, R., Tonelli, S., Vittorini, P.: An AI-based process for generating games from flat stories. In: Proceedings of the 33rd SGAI, pp. 337\u2013350 (2013)","DOI":"10.1007\/978-3-319-02621-3_25"},{"issue":"4","key":"231_CR22","doi-asserted-by":"crossref","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. J. ACM 38(4), 935\u2013962 (1991)","journal-title":"J. ACM"},{"issue":"1","key":"231_CR23","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/2455.2460","volume":"32","author":"M Hennessy","year":"1985","unstructured":"Hennessy, M., Milner, R.: Algebraic laws for nondeterminism and concurrency. J. ACM 32(1), 137\u2013161 (1985)","journal-title":"J. ACM"},{"key":"231_CR24","unstructured":"Laban, S., El-Desouky, A.: RISMA: A rule-based interval state machine algorithm for alerts generation, performance analysis and monitoring real-time data processing. In: Proceedings of the EGU General Assembly 2013, Geophysical Research Abstracts, vol. 15 (2013)"},{"issue":"2","key":"231_CR25","doi-asserted-by":"crossref","first-page":"217","DOI":"10.3233\/FI-2014-1011","volume":"131","author":"J Marcinkowski","year":"2014","unstructured":"Marcinkowski, J., Michaliszyn, J.: The undecidability of the logic of subintervals. Fundam. Inform. 131(2), 217\u2013240 (2014)","journal-title":"Fundam. Inform."},{"key":"231_CR26","doi-asserted-by":"crossref","unstructured":"Montanari, A., Puppis, G., Sala, P.: Maximal decidable fragments of Halpern and Shoham\u2019s modal logic of intervals. In: Proceedings of the 37th ICALP, LNCS, vol. 6199, pp. 345\u2013356. Springer (2010)","DOI":"10.1007\/978-3-642-14162-1_29"},{"key":"231_CR27","unstructured":"Montanari, A., Puppis, G., Sala, P., Sciavicco, G.: Decidability of the interval temporal logic $${\\sf AB} \\overline{{\\sf B}}$$ AB B \u00af over the natural numbers. In: Proceedings of the 31st STACS, pp. 597\u2013608 (2010)"},{"key":"231_CR28","unstructured":"Moszkowski, B.: Reasoning About Digital Circuits. Technical report. stan-cs-83-970, Dept. of Computer Science, Stanford University, Stanford, CA (1983)"},{"issue":"1\u20132","key":"231_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2005.04.003","volume":"166","author":"I Pratt-Hartmann","year":"2005","unstructured":"Pratt-Hartmann, I.: Temporal prepositions and their logic. Artif. Intell. 166(1\u20132), 1\u201336 (2005)","journal-title":"Artif. Intell."},{"key":"231_CR30","volume-title":"Linear Orderings","author":"J Rosenstein","year":"1982","unstructured":"Rosenstein, J.: Linear Orderings. Academic Press, Waltham (1982)"},{"key":"231_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3550-5","volume-title":"Modal and temporal properties of processes","author":"C Stirling","year":"2001","unstructured":"Stirling, C.: Modal and temporal properties of processes. Springer, Berlin (2001)"},{"issue":"5","key":"231_CR32","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1109\/TKDE.2004.1277816","volume":"16","author":"P Terenziani","year":"2004","unstructured":"Terenziani, P., Snodgrass, R.T.: Reconciling point-based and interval-based semantics in temporal relational databases: a treatment of the telic\/atelic distinction. IEEE Trans. Knowl. Data Eng. 16(5), 540\u2013551 (2004)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"4","key":"231_CR33","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1305\/ndjfl\/1093635589","volume":"31","author":"Y Venema","year":"1990","unstructured":"Venema, Y.: Expressiveness and completeness of an interval tense logic. Notre Dame J. Form. Log. 31(4), 529\u2013547 (1990)","journal-title":"Notre Dame J. Form. Log."},{"key":"231_CR34","volume-title":"Duration Calculus: A Formal Approach to Real-Time Systems. EATCS Monographs in Theoretical Computer Science","author":"C Zhou","year":"2004","unstructured":"Zhou, C., Hansen, M.R.: Duration Calculus: A Formal Approach to Real-Time Systems. EATCS Monographs in Theoretical Computer Science. Springer, Berlin (2004)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-015-0231-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-015-0231-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-015-0231-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,2]],"date-time":"2020-09-02T04:26:30Z","timestamp":1599020790000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-015-0231-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,14]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["231"],"URL":"https:\/\/doi.org\/10.1007\/s00236-015-0231-4","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,14]]}}}