{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T04:03:44Z","timestamp":1748837024450,"version":"3.41.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"6-8","license":[{"start":{"date-parts":[[2016,1,22]],"date-time":"2016-01-22T00:00:00Z","timestamp":1453420800000},"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,10]]},"DOI":"10.1007\/s00236-016-0256-3","type":"journal-article","created":{"date-parts":[[2016,1,22]],"date-time":"2016-01-22T10:17:38Z","timestamp":1453457858000},"page":"621-648","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Metric propositional neighborhood logic with an equivalence relation"],"prefix":"10.1007","volume":"53","author":[{"given":"Angelo","family":"Montanari","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Pazzaglia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pietro","family":"Sala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,22]]},"reference":[{"issue":"3","key":"256_CR1","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1007\/s00224-010-9279-2","volume":"48","author":"M Boja\u0144czyk","year":"2011","unstructured":"Boja\u0144czyk, M.: Weak MSO with the unbounding quantifier. Theory Comput. Syst. 48(3), 554\u2013576 (2011)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"256_CR2","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/1970398.1970403","volume":"12","author":"M Boja\u0144czyk","year":"2011","unstructured":"Boja\u0144czyk, M., David, C., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data words. ACM Trans. Comput. Log. 12(4), 27 (2011)","journal-title":"ACM Trans. Comput. Log."},{"issue":"2","key":"256_CR3","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10270-011-0195-y","volume":"12","author":"D Bresolin","year":"2013","unstructured":"Bresolin, D., Monica, D.Della, Goranko, V., Montanari, A., Sciavicco, G.: Metric propositional neighborhood logics on natural numbers. Softw. Syst. Model. 12(2), 245\u2013264 (2013)","journal-title":"Softw. Syst. Model."},{"issue":"3","key":"256_CR4","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":"256_CR5","doi-asserted-by":"crossref","unstructured":"Bresolin, D., Montanari, A., Sala, P.: An optimal tableau-based decision algorithm for propositional neighborhood logic. In: Proceedings of the 24th STACS, vol. 4393 of LNCS, pp. 549\u2013560. Springer, (2007)","DOI":"10.1007\/978-3-540-70918-3_47"},{"issue":"1\u20133","key":"256_CR6","doi-asserted-by":"crossref","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. J. Autom. Reason. 38(1\u20133), 173\u2013199 (2007)","journal-title":"J. Autom. Reason."},{"key":"256_CR7","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.tcs.2012.10.043","volume":"493","author":"Davide Bresolin","year":"2013","unstructured":"Bresolin, Davide, Montanari, Angelo, Sala, Pietro, Sciavicco, Guido: Optimal decision procedures for MPNL over finite structures, the natural numbers, and the integers. Theor. Comput. Sci. 493, 98\u2013115 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"256_CR8","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/1507244.1507246","volume":"10","author":"S Demri","year":"2009","unstructured":"Demri, S., Lazic, R.: LTL with the freeze quantifier and register automata. ACM Trans. Comput. Log. 10(3), 16 (2009)","journal-title":"ACM Trans. Comput. Log."},{"issue":"9","key":"256_CR9","first-page":"1137","volume":"9","author":"V Goranko","year":"2003","unstructured":"Goranko, V., Montanari, A., Sciavicco, G.: Propositional interval neighborhood temporal logics. J. Univers. Comput. Sci. 9(9), 1137\u20131167 (2003)","journal-title":"J. Univers. Comput. Sci."},{"issue":"1","key":"256_CR10","doi-asserted-by":"crossref","first-page":"53","DOI":"10.2307\/421196","volume":"3","author":"E Gr\u00e4del","year":"1997","unstructured":"Gr\u00e4del, E., Kolaitis, P.G., Vardi, M.Y.: On the decision problem for two-variable first-order logic. Bull. Symb. Log. 3(1), 53\u201369 (1997)","journal-title":"Bull. Symb. Log."},{"issue":"2","key":"256_CR11","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0304-3975(79)90041-0","volume":"8","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Pansiot, J.-J.: On the reachability problem for 5-dimensional vector addition systems. Theor. Comput. Sci. 8(2), 135\u2013159 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"256_CR12","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0022-0000(69)80011-5","volume":"3","author":"RM Karp","year":"1969","unstructured":"Karp, R.M., Miller, R.E.: Parallel program schemata. J. Comput. Syst. Sci. 3(2), 147\u2013195 (1969)","journal-title":"J. Comput. Syst. Sci."},{"key":"256_CR13","doi-asserted-by":"crossref","unstructured":"Kieronski, E., Michaliszyn, J., Pratt-Hartmann, I., Tendera, L.: Two-variable first-order logic with equivalence closure. In: Proceedings of the 27th LICS, pp. 431\u2013440. IEEE, (2012)","DOI":"10.1109\/LICS.2012.53"},{"key":"256_CR14","doi-asserted-by":"crossref","unstructured":"Kieronski, E., Otto, M.: Small substructures and decidability issues for first-order logic with two variables. In: Proceedings of the 20th LICS, pp. 448\u2013457. IEEE, (2005)","DOI":"10.1109\/LICS.2005.49"},{"key":"256_CR15","doi-asserted-by":"crossref","unstructured":"Kieronski, E., Tendera, L.: On finite satisfiability of two-variable first-order logic with equivalence relations. In: Proceedings of the 24th LICS, pp. 123\u2013132. IEEE, (2009)","DOI":"10.1109\/LICS.2009.39"},{"key":"256_CR16","doi-asserted-by":"crossref","unstructured":"Kosaraju, S.R.: Decidability of reachability in vector addition systems (preliminary version). In: Proceedings of the 14th STOC, pp. 267\u2013281. ACM, (1982)","DOI":"10.1145\/800070.802201"},{"key":"256_CR17","unstructured":"Lipton, R.J.: The reachability problem requires exponential space. Technical Report\u00a062, Department of Computer Science, Yale University, (1976)"},{"key":"256_CR18","unstructured":"Montanari, A., Puppis, G., Sala, P., Sciavicco, G.: Decidability of the interval temporal logic $$AB\\bar{B}$$ A B B \u00af on natural numbers. In: Proceedings of the 27th STACS, pp. 597\u2013608, (2010)"},{"key":"256_CR19","doi-asserted-by":"crossref","unstructured":"Montanari, A., Sala, P.: Adding an equivalence relation to the interval logic $${AB\\overline{B}}$$ A B B \u00af : complexity and expressiveness. In: Proceedings of the 28th LICS, pp. 193\u2013202. IEEE, (2013)","DOI":"10.1109\/LICS.2013.25"},{"key":"256_CR20","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/malq.19750210118","volume":"21","author":"M Mortimer","year":"1975","unstructured":"Mortimer, M.: On languages with two variables. Z. Math. Log. Grundlagen Math. 21, 135\u2013140 (1975)","journal-title":"Z. Math. Log. Grundlagen Math."},{"issue":"2","key":"256_CR21","doi-asserted-by":"crossref","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. J. Symb. Log. 66(2), 685\u2013702 (2001)","journal-title":"J. Symb. Log."},{"key":"256_CR22","doi-asserted-by":"crossref","unstructured":"Ouaknine, J., Worrell, J.: On the decidability and complexity of metric temporal logic over finite words. Log. Methods Comput. Sci. 3(1), 1\u201327 (2007)","DOI":"10.2168\/LMCS-3(1:8)2007"},{"issue":"4","key":"256_CR23","first-page":"377","volume":"27","author":"D Scott","year":"1962","unstructured":"Scott, D.: A decision method for validity of sentences in two variables. J. Symb. Log. 27(4), 377 (1962)","journal-title":"J. Symb. Log."},{"issue":"4","key":"256_CR24","doi-asserted-by":"crossref","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. J. Log. Comput. 1(4), 453\u2013476 (1991)","journal-title":"J. Log. Comput."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0256-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-016-0256-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0256-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-016-0256-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T06:17:31Z","timestamp":1748758651000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-016-0256-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,22]]},"references-count":24,"journal-issue":{"issue":"6-8","published-print":{"date-parts":[[2016,10]]}},"alternative-id":["256"],"URL":"https:\/\/doi.org\/10.1007\/s00236-016-0256-3","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2016,1,22]]}}}