{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T12:07:43Z","timestamp":1775736463082,"version":"3.50.1"},"reference-count":44,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2023,8,24]],"date-time":"2023-08-24T00:00:00Z","timestamp":1692835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,3,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We discuss the notion of bisimulation in various model-changing modal logics and provide an algorithmic study of the same. We provide a general algorithm which gives an overall procedure to check whether two models are bisimilar in all these logics. Through our algorithmic analyses we provide a PSPACE upper bound of the bisimulation\/model comparison problem of all these modal logics. We also provide some insight into the higher complexity of the model comparison problem for these logics compared to that for the basic modal logic.<\/jats:p>","DOI":"10.1093\/logcom\/exad018","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T10:52:42Z","timestamp":1692960762000},"page":"399-427","source":"Crossref","is-referenced-by-count":5,"title":["Bisimulation in model-changing modal logics: An algorithmic study"],"prefix":"10.1093","volume":"34","author":[{"given":"Sujata","family":"Ghosh","sequence":"first","affiliation":[{"name":"Indian Statistical Institute , Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shreyas","family":"Gupta","sequence":"additional","affiliation":[{"name":"Indian Institute of Science , Bangalore, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Li","sequence":"additional","affiliation":[{"name":"Tsinghua University-University of Amsterdam JRC for Logic , Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"key":"2024030222105816400_ref1","first-page":"100","article-title":"The algorithmics of bisimilarity","volume-title":"Advanced Topics in Bisimulation and Coinduction","author":"Aceto","year":"2012"},{"key":"2024030222105816400_ref2","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1007\/978-3-642-32621-9_11","article-title":"Moving arrows and four model checking results","volume-title":"International Workshop on Logic, Language, Information, and Computation","author":"Areces","year":"2012"},{"key":"2024030222105816400_ref3","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1093\/jigpal\/jzt030","article-title":"Swap logic","volume":"22","author":"Areces","year":"2014","journal-title":"Logic Journal of IGPL"},{"key":"2024030222105816400_ref4","first-page":"56","article-title":"Expressive power and decidability for memory logics","volume-title":"Proceedings of the 15th International Workshop on Logic, Language, Information and Computation, WoLLIC 2008","author":"Areces","year":"2008"},{"key":"2024030222105816400_ref5","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1093\/logcom\/exx034","article-title":"Modal logics of sabotage revisited","volume":"28","author":"Aucher","year":"2018","journal-title":"Journal of Logic and Computation"},{"key":"2024030222105816400_ref6","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1007\/BF03180566","article-title":"Deciding bisimilarity is P-complete","volume":"4","author":"Balc\u00e1zar","year":"1992","journal-title":"Formal Aspects Comput."},{"key":"2024030222105816400_ref7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-662-60292-8_1","article-title":"On the right path: A modal logic for supervised learning","volume-title":"Logic, Rationality, and Interaction","author":"Baltag","year":"2019"},{"key":"2024030222105816400_ref8","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1023\/B:SYNT.0000024912.56773.5e","article-title":"Logics for epistemic programs","volume":"139","author":"Baltag","year":"2004","journal-title":"Synthese"},{"key":"2024030222105816400_ref9","article-title":"The Logic of Public Announcements, Common Knowledge, and Private Suspicions. Readings in Formal Epistemology","volume-title":"773\u2011812","author":"Baltag","year":"(2016)"},{"key":"2024030222105816400_ref10","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1145\/151646.151648","article-title":"The concurrency workbench: A semantics-based tool for the verification of concurrent systems","volume":"15","author":"Cleaveland","year":"1993","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"2024030222105816400_ref11","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0012-365X(93)90496-G","article-title":"Kernels in directed graphs: A poison game","volume":"115","author":"Duchet","year":"1993","journal-title":"Discrete Mathematics"},{"key":"2024030222105816400_ref12","volume-title":"Relation-changing modal logics","author":"Fervari","year":"2014"},{"key":"2024030222105816400_ref13","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/s10009-012-0244-z","article-title":"CADP 2011: a toolbox for the construction and analysis of distributed processes","volume":"15","author":"Garavel","year":"2012","journal-title":"International Journal on Software Tools for Technology Transfer"},{"key":"2024030222105816400_ref14","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1023\/A:1008222603071","article-title":"Reasoning about information change","volume":"6","author":"Gerbrandy","year":"1997","journal-title":"Journal of Logic, Language and Information"},{"key":"2024030222105816400_ref15","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1017\/CBO9780511973468.005","article-title":"Back and forth between logic and games","volume-title":"Lectures in Game Theory for Computer Scientists","author":"Gr\u00e4del","year":"2011"},{"key":"2024030222105816400_ref16","first-page":"53","article-title":"The mCRL2 toolset","volume-title":"Proceedings of the International Workshop on Advanced Software Development Tools and Techniques (WASDeTT 2008)","author":"Groote","year":"2008"},{"key":"2024030222105816400_ref17","first-page":"1994","article-title":"Credulous acceptability, poison games and modal logic","volume-title":"Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems","author":"Grossi","year":"2019"},{"key":"2024030222105816400_ref18","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1145\/568438.568455","article-title":"Introduction to automata theory, languages, and computation","volume":"32","author":"Hopcroft","year":"2001","journal-title":"Sigact News"},{"key":"2024030222105816400_ref19","first-page":"228","article-title":"CCS expressions, finite state processes, and three problems of equivalence","volume-title":"Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing","author":"Kanellakis","year":"1983"},{"key":"2024030222105816400_ref20","doi-asserted-by":"crossref","first-page":"231","DOI":"10.3166\/jancl.17.231-253","article-title":"Expressivity and completeness for public update logics via reduction axioms","volume":"17","author":"Kooi","year":"2007","journal-title":"Journal of Applied Non-Classical Logics"},{"key":"2024030222105816400_ref21","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1017\/S1755020311000189","article-title":"Arrow update logic","volume":"4","author":"Kooi","year":"2011","journal-title":"The Review of Symbolic Logic"},{"key":"2024030222105816400_ref22","first-page":"205","article-title":"Generalized arrow update logic","volume-title":"Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, TARK XIII","author":"Kooi","year":"2011"},{"key":"2024030222105816400_ref23","doi-asserted-by":"crossref","first-page":"715","DOI":"10.1093\/logcom\/exz036","article-title":"Losing connection: The modal logic of definable link deletion","volume":"30","author":"Li","year":"2020","journal-title":"Journal of Logic and Computation"},{"key":"2024030222105816400_ref24","first-page":"302","article-title":"Model checking and satisfiability for sabotage modal logic","volume-title":"Foundations of Software Technology and Theoretical Computer Science. FSTTCS 2003, number 2914 in Lecture Notes in Computer Science","author":"L\u00f6ding","year":"2003"},{"key":"2024030222105816400_ref25","first-page":"531","article-title":"Solving the sabotage game is pspace-hard","volume-title":"Mathematical Foundations of Computer Science 2003, number 2914 in Lecture Notes in Computer Science","author":"L\u00f6ding","year":"2003"},{"key":"2024030222105816400_ref26","volume-title":"Modal Memory Logics","author":"Mera","year":"2009"},{"key":"2024030222105816400_ref27","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0012-365X(83)90160-7","article-title":"Vertex-to-vertex pursuit in a graph","volume":"43","author":"Nowakowski","year":"1983","journal-title":"Discrete Mathematics"},{"key":"2024030222105816400_ref28","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1137\/0216062","article-title":"Three partition refinement algorithms","volume":"16","author":"Paige","year":"1987","journal-title":"SIAM Journal on Computing"},{"key":"2024030222105816400_ref29","first-page":"201","article-title":"Logics of public communications","volume-title":"Proceedings of the 4th International Symposium on Methodologies for Intelligent Systems (ISMIS 1989), Poster Session Program","author":"Plaza","year":"1989"},{"key":"2024030222105816400_ref30","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s11229-007-9168-7","article-title":"Logics of public communications","volume":"158","author":"Plaza","year":"2007","journal-title":"Synthese"},{"key":"2024030222105816400_ref31","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1093\/logcom\/14.2.251","article-title":"Changing modalities","volume":"14","author":"Renardel","year":"2004","journal-title":"Journal of Logic and Computation"},{"key":"2024030222105816400_ref32","volume-title":"On games and logics over dynamically changing structures","author":"Rohde","year":"2005"},{"key":"2024030222105816400_ref33","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/978-981-15-2221-5_5","article-title":"Local fact change logic","volume-title":"Knowledge, Proof and Dynamics","author":"Thompson","year":"2020"},{"key":"2024030222105816400_ref34","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1007\/978-3-540-32254-2_16","article-title":"An essay on sabotage and obstruction","volume-title":"Mechanizing Mathematical Reasoning: Essays in Honor of J\u00f6rg H. Siekmann on the Occasion of His 60th Birthday","author":"van Benthem","year":"2005"},{"key":"2024030222105816400_ref35","doi-asserted-by":"crossref","first-page":"129","DOI":"10.3166\/jancl.17.129-155","article-title":"Dynamic logic for belief revision","volume":"17","author":"van Benthem","year":"2007","journal-title":"Journal of Applied Non-Classical Logics"},{"key":"2024030222105816400_ref36","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511974533","volume-title":"Logical Dynamics of Information and Interaction","author":"van Benthem","year":"2011"},{"key":"2024030222105816400_ref37","first-page":"exac006","article-title":"Hybrid sabotage modal logic","volume":"03","author":"van Benthem","year":"2022","journal-title":"Journal of Logic and Computation"},{"key":"2024030222105816400_ref38","doi-asserted-by":"crossref","first-page":"157","DOI":"10.3166\/jancl.17.157-182","article-title":"Dynamic logic of preference upgrade","volume":"17","author":"van Benthem","year":"2007","journal-title":"Journal of Applied Non-Classical Logics"},{"key":"2024030222105816400_ref39","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-981-15-2221-5_7","article-title":"Graph games and logic design","volume-title":"Knowledge, Proof and Dynamics","author":"van Benthem","year":"2020"},{"key":"2024030222105816400_ref40","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1017\/S1755020320000258","article-title":"The modal logic of stepwise removal","volume":"15","author":"van Benthem","year":"2020","journal-title":"The Review of Symbolic Logic"},{"key":"2024030222105816400_ref41","doi-asserted-by":"crossref","first-page":"1620","DOI":"10.1016\/j.ic.2006.04.006","article-title":"Logics of communication and change","volume":"204","author":"van Benthem","year":"2006","journal-title":"Inf. Comput."},{"key":"2024030222105816400_ref42","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1145\/1082473.1082495","article-title":"Dynamic epistemic logic with assignment","author":"van Ditmarsch","year":"2005","journal-title":"Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems"},{"key":"2024030222105816400_ref43","volume-title":"Dynamic epistemic logic, volume 337","author":"Van Ditmarsch","year":"2007"},{"key":"2024030222105816400_ref44","doi-asserted-by":"crossref","DOI":"10.1007\/978-981-15-2221-5_1","article-title":"The modal logics of the poison game","volume-title":"Knowledge, Proofs and Dynamics","author":"Zaffora Blando","year":"2020"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/34\/2\/399\/56818175\/exad018.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/34\/2\/399\/56818175\/exad018.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T22:11:33Z","timestamp":1709417493000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/34\/2\/399\/7244669"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,24]]},"references-count":44,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2023,8,24]]},"published-print":{"date-parts":[[2024,3,3]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exad018","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,3]]},"published":{"date-parts":[[2023,8,24]]}}}