Abstract
We investigate bisimulations for instantial neighbourhood logic and an \(\omega \)-indexed collection of its fragments. For each of these logics we give a Hennessy-Milner theorem and a Van Benthem-style characterisation theorem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abriola, S., M. Descotte, and S. Figueira, Model theory of XPath on data trees. Part II: Binary bisimulation and definability, Information and Computation 255:195–223, 2017.
Aczel, P., Non-well-founded Sets, CSLI Publications, Stanford, 1988.
Badia, G., Bi-simulating in bi-intuitionistic logic, Studia Logica 104:1037–1050, 2016.
Benthem, J. van, Modal Correspondence Theory, Ph.D. thesis, Mathematisch Instituut & Instituut voor Grondslagenonderzoek, University of Amsterdam, 1976.
Benthem, J. van, Correspondence theory, in D. Gabbay, and F. Guenthner, (eds.), Handbook of Philosophical Logic: Volume II: Extensions of Classical Logic, Springer Netherlands, Dordrecht, 1984, pp. 167–247.
Benthem, J. van, N. Bezhanishvili, and S. Enqvist, A new game equivalence, its logic and algebra, Journal of Philosophical Logic 48(4):649–684, 2019.
Benthem, J. van, N. Bezhanishvili, and S. Enqvist, A propositional dynamic logic for instantial neighbourhood semantics, Studia Logica 107(4):719–751, 2019.
Benthem, J. van, N. Bezhanishvili, S. Enqvist, and J. Yu, Instantial neighbourhood logic, Review of Symbolic Logic 10(1):116–144, 2017.
Bezhanishvili, N., S. Enqvist, and J. de Groot, Duality for instantial neighbourhood logic via coalgebra, in D. Petrişan, and J. Rot, (eds.), Proc. CMCS 2020, Springer International Publishing, Cham, 2020, pp. 32–54.
Bezhanishvili, N., J. de Groot, and Y. Venema, Coalgebraic geometric logic, in M. Roggenbach, and A. Sokolova, (eds.), Proc. CALCO 2019, vol. 139 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2019, pp. 7:1–7:18.
Blackburn, P., M. de Rijke, and Y. Venema, Modal Logic, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, Cambridge, 2001.
Carreiro, F., PDL is the bisimulation-invariant fragment of weak chain logic, in Proc. LICS 2015, IEEE Computer Society, USA, 2015, pp. 341–352.
Cate, B. ten, D. Gabelaia, and D. Sustretov, Modal languages for topology: Expressivity and definability, Annals of Pure and Applied Logic 159(1–2):146–170, 2009.
Cate, B. ten, G. Fontaine, and T. Litak, Some modal aspects of XPath, Journal of Applied Non-Classical Logics 20:139–171, 2010.
Celani, S. A., and R. Jansana, A new semantics for positive modal logic, Notre Dame Journal of Formal Logic 38(1):1–19, 1997.
Celani, S. A., and R. Jansana, Priestley duality, a Sahlqvist theorem and a Goldblatt-Thomason theorem for positive modal logic, Logic Journal of the IGPL 7:683–715, 1999.
Chang, C., and H. Keisler, Model Theory, Elsevier, North-Holland, 1973.
Chellas, B. F., Modal Logic: An Introduction, Cambridge University Press, Cambridge, 1980.
Dunn, J. M., Positive modal logic, Studia Logica 55:301–317, 1995.
Enqvist, S., Homomorphisms of coalgebras from predicate liftings, in Proc. CALCO 2013, Springer, 2013, pp. 126–140.
Enqvist, S., F. Seifan, and Y. Venema, Completeness for-\(\mu \)calculi: a coalgebraic approach, Annals of Pure and Applied Logic 170:578–641, 2019.
Figueira, D., S. Figueira, and C. Areces, Model theory of XPath on data trees. Part I: Bisimulation and characterization, Journal of Artificial Intelligence Research 53:271–314, 2015.
Flum, J., and M. Ziegler, Topological Model Theory, vol. 769 of Lecture Notes in Mathematics, Springer Verlag, 1980.
Gorín, D., and L. Schröder, Simulations and bisimulations for coalgebraic modal logics, in R. Heckel, and S. Milius, (eds.), Proc. CALCO 2013, Springer, 2013, pp. 253–266.
Groot, J. de, and D. Pattinson, Hennessy-Milner properties for (modal) bi-intuitionistic logic, in R. Iemhoff, M. Moortgat, and R. de Queiroz, (eds.), Proc. WoLLIC 2019, Springer, Berlin, Heidelberg, 2019, pp. 161–176.
Hansen, H. H., Monotonic modal logics, Masters thesis, Institute for Logic, Language and Computation, University of Amsterdam, 2003.
Hansen, H. H., C. Kupke, and E. Pacuit, Neighbourhood structures: bisimilarity and basic model theory, Logical Methods in Computer Science 5(2):1–38, 2009.
Hennessy, M., and R. Milner, Algebraic laws for nondeterminism and concurrency, Journal of the Association for Computing Machinery 32(1):137–161, 1985.
Janin, D., and I. Walukiewicz, Automata for the modal \(\mu \)-calculus and related results, in J. Wiedermann, and P. Hájek, (eds.), Mathematical Foundations of Computer Science 1995, Springer, Berlin, Heidelberg, 1995, pp. 552–562.
Kupke, C., and D. Pattinson, Coalgebraic semantics of modal logics: An overview, Theoretical Computer Science 412(38):5070–5094, 2011 (CMCS Tenth Anniversary Meeting).
Litak, T., D. Pattinson, K. Sano, and L. Schröder, Coalgebraic predicate logic, in A. Czumaj, K. Mehlhorn, A. Pitts, and R. Wattenhofer, (eds.), Proc. ICALP 2012, Springer, 2012, pp. 299–311.
Milner, R., A Calculus of Communicating Systems, Springer-Verlag, Berlin, Heidelberg, 1980.
Olkhovikov, G. K., Model-theoretic characterization of intuitionistic propositional formulas, The Review of Symbolic Logic 6(2):348–365, 2013.
Park, D., Concurrency and automata on infinite sequences, in P. Deussen, (ed.), Theoretical Computer Science, Springer, Berlin, Heidelberg, 1981, pp. 167–183.
Patterson, A., Bisimulation and propositional intuitionistic logic, in A. Mazurkiewicz, and J. Winkowski, (eds.), CONCUR ’97: Concurrency Theory, Springer Berlin Heidelberg, Berlin, Heidelberg, 1997, pp. 347–360.
Rutten, J.J.M.M., Universal coalgebra: a theory of systems, Theoretical Computer Science 249(1):3–80, 2000.
Schröder, L., Expressivity of coalgebraic modal logic: The limits and beyond, Theoretical Computer Science 390:230–247, 2008.
Schröder, L., D. Pattinson, and T. Litak, A Van Benthem/Rosen theorem for coalgebraic predicate logic, Journal of Logic and Computation 27(3):749–773, 2017.
Tuyt, O., Canonical rules on neighbourhood frames, Masters thesis, ILLC, University of Amsterdam, 2016.
Venema, Y., and J. Vosmaer, Modal logic and the Vietoris functor, in G. Bezhanishvili, (ed.), Leo Esakia on Duality in Modal and Intuitionistic Logics, Springer Netherlands, Dordrecht, 2014, pp. 119–153.
Yu, J., A tableau system for instantial neighborhood logic, in Proc. LFCS 2018, 2018, pp. 337–353.
Yu, J., Lyndon interpolation theorem of instantial neighborhood logic – constructively via a sequent calculus, Annals of Pure and Applied Logic, 171(1):102721, 2020.
Zhao, Z., Sahlqvist correspondence theory for instantial neighbourhood logic, 2020. Available at arXiv:2003.14187
Acknowledgements
I am grateful to Johan van Benthem and Nick Bezhanishvili for their comments on the manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Presented by Heinrich Wansing.
Rights and permissions
About this article
Cite this article
de Groot, J. Hennessy-Milner and Van Benthem for Instantial Neighbourhood Logic. Stud Logica 110, 717–743 (2022). https://doi.org/10.1007/s11225-021-09975-w
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11225-021-09975-w