{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:40:00Z","timestamp":1753890000337,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2017,7,3]],"date-time":"2017-07-03T00:00:00Z","timestamp":1499040000000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"},{"start":{"date-parts":[[2017,7,3]],"date-time":"2017-07-03T00:00:00Z","timestamp":1499040000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"},{"start":{"date-parts":[[2017,7,3]],"date-time":"2017-07-03T00:00:00Z","timestamp":1499040000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>Generalizing standard monadic second-order logic for Kripke models, we introduce monadic second-order logic interpreted over coalgebras for an arbitrary set functor. We then consider invariance under behavioral equivalence of MSO-formulas. More specifically, we investigate whether the coalgebraic mu-calculus is the bisimulation-invariant fragment of the monadic second-order language for a given functor. Using automatatheoretic techniques and building on recent results by the third author, we show that in order to provide such a characterization result it suffices to find what we call an adequate uniform construction for the coalgebraic type functor. As direct applications of this result we obtain a partly new proof of the Janin-Walukiewicz Theorem for the modal mu-calculus, avoiding the use of syntactic normal forms, and bisimulation invariance results for the bag functor (graded modal logic) and all exponential polynomial functors (including the &amp;quot;game functor&amp;quot;). As a more involved application, involving additional non-trivial ideas, we also derive a characterization theorem for the monotone modal mu-calculus, with respect to a natural monadic second-order language for monotone neighborhood models.<\/jats:p><jats:p>Comment: arXiv admin note: substantial text overlap with arXiv:1501.07215<\/jats:p>","DOI":"10.23638\/lmcs-13(2:14)2017","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T17:32:56Z","timestamp":1743701576000},"source":"Crossref","is-referenced-by-count":0,"title":["An expressive completeness theorem for coalgebraic modal mu-calculi"],"prefix":"10.23638","volume":"Volume 13, Issue 2","author":[{"given":"Sebastian","family":"Enqvist","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2901-5332","authenticated-orcid":false,"given":"Fatemeh","family":"Seifan","sequence":"additional","affiliation":[]},{"given":"Yde","family":"Venema","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2017,7,3]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/1704.08637v2","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/1704.08637v2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T17:32:56Z","timestamp":1743701576000},"score":1,"resource":{"primary":{"URL":"http:\/\/lmcs.episciences.org\/3756"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,3]]},"references-count":0,"URL":"https:\/\/doi.org\/10.23638\/lmcs-13(2:14)2017","relation":{"is-same-as":[{"id-type":"arxiv","id":"1704.08637","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1704.08637","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2017,7,3]]},"article-number":"3756"}}