{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T23:45:03Z","timestamp":1791935103054,"version":"4.3.4"},"reference-count":20,"publisher":"Duke University Press","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Notre Dame J. Formal Logic"],"published-print":{"date-parts":[[1996,4,1]]},"abstract":"<jats:p>We study the decidability problem for metric and layered temporal logics. The logics we consider are suitable to model time granularity in various contexts, and they allow one to build granular temporal models by referring to the \"natural scale\" in any component of the model and by properly constraining the interactions between differently-grained components. A monadic second-order language combining operators such as temporal contextualization and projection, together with the usual displacement operator of metric temporal logics, is considered, and the theory of finitely-layered metric temporal structures is shown to be decidable.<\/jats:p>","DOI":"10.1305\/ndjfl\/1040046089","type":"journal-article","created":{"date-parts":[[2003,2,25]],"date-time":"2003-02-25T16:11:13Z","timestamp":1046189473000},"page":"260-282","source":"Crossref","is-referenced-by-count":16,"title":["Decidability Results for Metric and Layered Temporal Logics"],"prefix":"10.1215","volume":"37","author":[{"given":"Angelo","family":"Montanari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alberto","family":"Policriti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"73","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"Alur, R., and T. A. Henzinger, \u201cReal-time logics: complexity and expressiveness,\u201d <i>Information and Computation<\/i>, vol. 104 (1993), pp. 35\u201377. Zbl 0791.68103 MR 94c:03036","DOI":"10.1006\/inco.1993.1025"},{"key":"2","doi-asserted-by":"crossref","unstructured":"B\u00fcchi, J. R., \u201cWeak second-order arithmetic and finite automata,\u201d <i>Zeitschrift f\u00fcr mathematishce Logik und Grundlagen der Mathematik<\/i>, vol. 6 (1960), pp. 66\u201392. MR 23:A2317","DOI":"10.1002\/malq.19600060105"},{"key":"3","unstructured":"B\u00fcchi, J. R., \u201cOn a decision method in restricted second-order arithmetic,\u201d pp. 1\u201311 in <i>Proceedings of 1st International Congress on Logic, Methodology, and Philosophy of Science<\/i> edited by E. Nagel, P. Suppes, and A. Tarski, Stanford University Press, Stanford, 1962. MR 32:1116"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Ciapessoni, E., E. Corsetti, A. Montanari, and P. San Pietro, \u201cEmbedding time granularity in a logical specification language for synchronous real-time systems,\u201d <i>Science of Computer Programming<\/i>, vol. 20 (1993), pp. 141\u2013171. Zbl 0781.68083 MR 94j:68196","DOI":"10.1016\/0167-6423(93)90025-K"},{"key":"5","doi-asserted-by":"crossref","unstructured":"D'Agostino, G., A. Montanari, and A. Policriti, \u201cA set-theoretic translation method for polymodal logics,\u201d <i>Journal of Automated Reasoning<\/i>, vol. 15 (1995), pp. 317\u2013337. Zbl 0840.03015 MR 96j:03024","DOI":"10.1007\/BF00881803"},{"key":"6","doi-asserted-by":"crossref","unstructured":"Ershov, Y. L., I. A. Lavrov, A. D. Taimanov, and M. A. Taitslin, \u201cElementary theories,\u201d <i>Russian Mathematical Surveys<\/i>, vol. 20 (1965), pp. 35\u2013105. Zbl 0199.03001","DOI":"10.1070\/RM1965v020n04ABEH001188"},{"key":"7","unstructured":"Euzenat, J., \u201cAn algebraic approach for granularity in qualitative space and time representation,\u201d pp. 894\u2013900 in <i>Proceedings of IJCAI '95<\/i>, Morgan Kaufmann, San Mateo, 1995."},{"key":"8","doi-asserted-by":"crossref","unstructured":"Fiadeiro, J. and T. Maibaum, \u201cSometimes `Tomorrow' is `Sometimes'\u2013action refinement in a temporal logic of objects,\u201d pp. 48\u201366 in <i>Proceedings of ICTL '94<\/i>, LNAI 827, Springer-Verlag, Berlin, 1992.","DOI":"10.1007\/BFb0013980"},{"key":"9","doi-asserted-by":"crossref","unstructured":"Finger, M., and D. Gabbay, \u201cCombining temporal logic systems,\u201d <i>Notre Dame Journal of Formal Logic<\/i>, vol. 37 (1996), pp. 204\u2013232. Zbl 0857.03008 MR 97d:03011","DOI":"10.1305\/ndjfl\/1040046087"},{"key":"10","doi-asserted-by":"crossref","unstructured":"Gabbay, D., A. Pnueli, S. Shelah, and J. Stavi, \u201cOn the temporal analysis of fairness,\u201d pp. 163\u2013173 in <i>Proceedings of the 7th Annual Symposium on Principles of Programming Languages<\/i>, ACM Press, New York, 1980.","DOI":"10.1145\/567446.567462"},{"key":"11","doi-asserted-by":"crossref","unstructured":"Koymans, R., \u201cSpecifying message passing and time-critical systems with temporal logic,\u201d LNCS 651, Springer-Verlag, Berlin, 1992. Zbl 0806.68074 MR 94c:68138","DOI":"10.1007\/3-540-56283-4"},{"key":"12","doi-asserted-by":"crossref","unstructured":"Manna, Z., and A. Pnueli, <i>The Temporal Logic of Reactive and Concurrent Systems<\/i>, Springer-Verlag, Berlin, 1992. Zbl 0753.68003 MR 93e:68073","DOI":"10.1007\/978-1-4612-0931-7"},{"key":"13","unstructured":"Montanari, A., \u201cA metric and layered temporal logic for time granularity, synchrony and asynchrony,\u201d pp. 49\u201358 in <i>Proceedings of the ICTL '94 Workshop, MPI-I-94-230<\/i>, edited by H. J. Ohlbach, Max-Planck-Institut f\u00fcr Informatik, Saarbruecken,1994."},{"key":"14","doi-asserted-by":"crossref","unstructured":"Montanari, A., and M. de Rijke, \u201cCompleteness results for two-sorted metric temporal logics,\u201d pp. 385\u2013399 in <i>Proceedings of the AMAST '95<\/i>, LNCS 936, Springer-Verlag, Berlin, 1995.","DOI":"10.1007\/3-540-60043-4_66"},{"key":"15","unstructured":"Montanari, A., and A. Policriti, \u201cA decidable theory of finitely-layered metric temporal structures,\u201d Report ML-96-06, ILLC, University of Amsterdam, July, 1996."},{"key":"16","unstructured":"Montanari, A., A. Peron, and A. Policriti, \u201cDecidabable theories of $\\omega$-layered metric temporal structures,\u201d Report ML-96-07, ILLC, University of Amsterdam, July, 1996."},{"key":"17","doi-asserted-by":"crossref","unstructured":"Rabin, M. O., \u201cDecidable theories,\u201d pp. 595\u2013629 in <i>Handbook of Mathematical Logic<\/i>, edited by J. Barwise, North-Holland, Ansterdam, 1977. Zbl 0443.03001 MR 56:15351","DOI":"10.1016\/S0049-237X(08)71116-9"},{"key":"18","doi-asserted-by":"crossref","unstructured":"Thomas, W., \u201cAutomata on infinite objects,\u201d pp. 131\u2013191 in <i>Handbook of Theoretical Computer Science<\/i>, edited by J. van Leeuwen, Elsevier, Amsterdam, 1990. Zbl 0900.68316 MR 1127189","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"key":"19","doi-asserted-by":"crossref","unstructured":"van Benthem J., \u201cTemporal logic,\u201d pp. 241\u2013350 in <i>Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. 4<\/i>, edited by D. Gabbay, C. Hogger, and J. Robinson, Oxford University Press, Oxford,1995. MR 97a:03023","DOI":"10.1093\/oso\/9780198537915.003.0005"},{"key":"20","unstructured":"Wang, X., C. Bettini, A. Brodsky, and S. Jajodia, \u201cLogical design for temporal databases with multiple granularities,\u201d forthcoming in <i>ACM TODS<\/i>."}],"container-title":["Notre Dame Journal of Formal Logic"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/journalArticle\/Download?urlid=10.1305\/ndjfl\/1040046089","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T22:54:46Z","timestamp":1791932086000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/notre-dame-journal-of-formal-logic\/volume-37\/issue-2\/Decidability-Results-for-Metric-and-Layered-Temporal-Logics\/10.1305\/ndjfl\/1040046089.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,4,1]]},"references-count":20,"journal-issue":{"issue":"2","published-online":{"date-parts":[[1996,4,1]]}},"URL":"https:\/\/doi.org\/10.1305\/ndjfl\/1040046089","relation":{},"ISSN":["0029-4527","1939-0726"],"issn-type":[{"value":"0029-4527","type":"print"},{"value":"1939-0726","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,4,1]]}}}