{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:00:24Z","timestamp":1750309224546,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T00:00:00Z","timestamp":1720396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Siemens AG"},{"name":"Integreat - Norwegian Centre for knowledge-driven machine learning","award":["332645"],"award-info":[{"award-number":["332645"]}]},{"name":"EPSRC ConCur","award":["EP\/V050869\/1"],"award-info":[{"award-number":["EP\/V050869\/1"]}]},{"name":"EPSRC OASIS","award":["EP\/S032347\/1"],"award-info":[{"award-number":["EP\/S032347\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,7,8]]},"DOI":"10.1145\/3661814.3662107","type":"proceedings-article","created":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T12:30:12Z","timestamp":1718973012000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Characterisation Theorem for Two-Way Bisimulation-Invariant Monadic Least Fixpoint Logic Over Finite Structures"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8235-3154","authenticated-orcid":false,"given":"Maximilian","family":"Pflueger","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-3193-0450","authenticated-orcid":false,"given":"Johannes","family":"Marti","sequence":"additional","affiliation":[{"name":"University of Zurich, Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8886-6129","authenticated-orcid":false,"given":"Egor V.","family":"Kostylev","sequence":"additional","affiliation":[{"name":"University of Oslo, Oslo, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Niwi\u0144ski","author":"Arnold Andr\u00e9","year":"2001","unstructured":"Andr\u00e9 Arnold and Damian D. Niwi\u0144ski. 2001. Rudiments of \u03bc-Calculus. Studies in Logic and the Foundations of Mathematics, Vol. 146. Elsevier, Amsterdam."},{"volume-title":"Introduction to Description Logic","author":"Baader Franz","key":"e_1_3_2_1_2_1","unstructured":"Franz Baader, Ian Horrocks, Carsten Lutz, and Uli Sattler. 2017. Introduction to Description Logic. Cambridge University Press."},{"key":"e_1_3_2_1_3_1","volume-title":"The Logical Expressiveness of Graph Neural Networks. In International Conference on Learning Representations, ICLR","author":"Barcel\u00f3 Pablo","year":"2019","unstructured":"Pablo Barcel\u00f3, Egor V. Kostylev, Mikael Monet, Jorge P\u00e9rez, Juan Reutter, and Juan Pablo Silva. 2019. The Logical Expressiveness of Graph Neural Networks. In International Conference on Learning Representations, ICLR 2019."},{"key":"e_1_3_2_1_4_1","volume-title":"On Classical Decidable Logics Extended With Percentage Quantifiers and Arithmetics. In Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS","volume":"213","author":"Bednarczyk Bartosz","year":"2021","unstructured":"Bartosz Bednarczyk, Maja Or\u0142owska, Anna Pacanowska, and Tony Tan. 2021. On Classical Decidable Logics Extended With Percentage Quantifiers and Arithmetics. In Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021, Vol. 213. 36:1--36:15."},{"volume-title":"Modal Logic","author":"Blackburn Patrick","key":"e_1_3_2_1_5_1","unstructured":"Patrick Blackburn, Maarten de Rijke, and Yde Venema. 2002. Modal Logic. Cambridge University Press."},{"volume-title":"Handbook of Modal Logic","author":"Blackburn Patrick","key":"e_1_3_2_1_6_1","unstructured":"Patrick Blackburn, Johan van Benthem, and Frank Wolter. 2006. Handbook of Modal Logic. Elsevier."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.03.001"},{"key":"e_1_3_2_1_8_1","volume-title":"Common Knowledge and Multi-Scale Locality Analysis in Cayley Structures. In ACM\/IEEE Symposium on Logic in Computer Science, LICS","author":"Canavoi Felix","year":"2017","unstructured":"Felix Canavoi and Martin Otto. 2017. Common Knowledge and Multi-Scale Locality Analysis in Cayley Structures. In ACM\/IEEE Symposium on Logic in Computer Science, LICS 2017. 1--12."},{"volume-title":"Fragments of Fixpoint Logics. Ph. D. Dissertation. Ph. D. thesis","author":"Carreiro Facundo","key":"e_1_3_2_1_9_1","unstructured":"Facundo Carreiro. 2015. Fragments of Fixpoint Logics. Ph. D. Dissertation. Ph. D. thesis, University of Amsterdam."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603101"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372392"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2020.77"},{"key":"e_1_3_2_1_13_1","volume-title":"Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS","author":"Dawar Anuj","year":"2004","unstructured":"Anuj Dawar and David Janin. 2004. On the Bisimulation Invariant Fragment of Monadic S1 in the Finite. In Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2004. 224--236."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.27"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2009.04.002"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1005245900406"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793304741"},{"key":"e_1_3_2_1_18_1","volume-title":"An Expressive Completeness Theorem for Coalgebraic Modal mu-Calculi. Logical Methods in Computer Science 13, 2","author":"Enqvist Sebastian","year":"2017","unstructured":"Sebastian Enqvist, Fatemeh Seifan, and Yde Venema. 2017. An Expressive Completeness Theorem for Coalgebraic Modal mu-Calculi. Logical Methods in Computer Science 13, 2 (2017)."},{"volume-title":"Studies in Logic and the Foundations of Mathematics.","author":"Gaifman Haim","key":"e_1_3_2_1_19_1","unstructured":"Haim Gaifman. 1982. On Local and Non-Local Properties. In Studies in Logic and the Foundations of Mathematics. Vol. 107. Elsevier, 105--135."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"V. Goranko and M. Otto. 2006. Handbook of Modal Logic. Elsevier Chapter Model Theory of Modal Logic 255--325.","DOI":"10.1016\/S1570-2464(07)80008-5"},{"volume-title":"Automata, Logic, and Infinite Games","author":"Gr\u00e4del Erich","key":"e_1_3_2_1_21_1","unstructured":"Erich Gr\u00e4del, Wolfgang Thomas, and Thomas Wilke. 2002. Automata, Logic, and Infinite Games. Springer."},{"key":"e_1_3_2_1_22_1","volume-title":"The Descriptive Complexity of Graph Neural Networks. In ACM\/IEEE Symposium on Logic in Computer Science, LICS","author":"Grohe Martin","year":"2023","unstructured":"Martin Grohe. 2023. The Descriptive Complexity of Graph Neural Networks. In ACM\/IEEE Symposium on Logic in Computer Science, LICS 2023. 1--14."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.2460"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61604-7_60"},{"key":"e_1_3_2_1_25_1","first-page":"133","article-title":"Un Theoreme Sur Les Functions d'Ensembles","volume":"6","author":"Knaster Bronis\u0142aw","year":"1928","unstructured":"Bronis\u0142aw Knaster. 1928. Un Theoreme Sur Les Functions d'Ensembles. Annales Soc. Polon. Math. 6 (1928), 133--134.","journal-title":"Annales Soc. Polon. Math."},{"volume-title":"Elements of Finite Model Theory","author":"Libkin Leonid","key":"e_1_3_2_1_26_1","unstructured":"Leonid Libkin. 2004. Elements of Finite Model Theory. Springer."},{"key":"e_1_3_2_1_27_1","volume-title":"On the Expressive Power of CTL. In Symposium on Logic in Computer Science, LICS","author":"Moller Faron","year":"1999","unstructured":"Faron Moller and Alexander Moshe Rabinovich. 1999. On the Expressive Power of CTL. In Symposium on Logic in Computer Science, LICS 1999. 360--368."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00104-4"},{"key":"e_1_3_2_1_29_1","volume-title":"Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. In AAAI Conference on Artificial Intelligence, AAAI","author":"Morris Christopher","year":"2019","unstructured":"Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2019. Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. In AAAI Conference on Artificial Intelligence, AAAI 2019. 4602--4609."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.04.003"},{"key":"e_1_3_2_1_31_1","volume-title":"Graded Modal Logic and Counting Bisimulation. arXiv preprint arXiv:1910.00039","author":"Otto Martin","year":"2019","unstructured":"Martin Otto. 2019. Graded Modal Logic and Counting Bisimulation. arXiv preprint arXiv:1910.00039 (2019)."},{"key":"e_1_3_2_1_32_1","volume-title":"TCS","author":"Park David","year":"1981","unstructured":"David Park. 1981. Concurrency and Automata on Infinite Sequences. In GI-Conference on Theoretical Computer Science, TCS 1981. 167--183."},{"key":"e_1_3_2_1_33_1","volume-title":"AAAI Conference on Artificial Intelligence, AAAI","author":"Pflueger Maximilian","year":"2024","unstructured":"Maximilian Pflueger, David Tena Cucala, and Egor V. Kostylev. 2024. Recurrent Graph Neural Networks and Their Connections to Bisimulation and Logic. In AAAI Conference on Artificial Intelligence, AAAI 2024. 14608--14616."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008275906015"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516507.1516510"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNN.2008.2005605"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.025"},{"key":"e_1_3_2_1_39_1","volume-title":"ICALP","author":"Vardi Moshe Y.","year":"1998","unstructured":"Moshe Y. Vardi. 1998. Reasoning about The Past with Two-Way Automata. In International Colloquium on Automata, Languages, and Programming, ICALP 1998. 628--641."},{"volume-title":"Lectures on the Modal \u03bc-Calculus. (2020). Lecture Notes","author":"Venema Yde","key":"e_1_3_2_1_40_1","unstructured":"Yde Venema. 2020. Lectures on the Modal \u03bc-Calculus. (2020). Lecture Notes, University of Amsterdam."},{"key":"e_1_3_2_1_41_1","first-page":"12","article-title":"A Reduction of a Graph to a Canonical Form and an Algebra Arising During This Reduction","volume":"2","author":"Weisfeiler Boris Yu.","year":"1968","unstructured":"Boris Yu. Weisfeiler and Andrei A. Leman. 1968. A Reduction of a Graph to a Canonical Form and an Algebra Arising During This Reduction. Nauchno-Technicheskaya Informatsia 2, 9 (1968), 12--16.","journal-title":"Nauchno-Technicheskaya Informatsia"},{"key":"e_1_3_2_1_42_1","volume-title":"International Conference on Learning Representations, ICLR","author":"Xu Keyulu","year":"2019","unstructured":"Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In International Conference on Learning Representations, ICLR 2019."}],"event":{"name":"LICS '24: 39th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","IEEE Computer Society","EACSL"],"location":"Tallinn Estonia","acronym":"LICS '24"},"container-title":["Proceedings of the 39th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661814.3662107","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3661814.3662107","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:44:09Z","timestamp":1750290249000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661814.3662107"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,8]]},"references-count":41,"alternative-id":["10.1145\/3661814.3662107","10.1145\/3661814"],"URL":"https:\/\/doi.org\/10.1145\/3661814.3662107","relation":{},"subject":[],"published":{"date-parts":[[2024,7,8]]},"assertion":[{"value":"2024-07-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}