research-article

Refinement modal logic

Authors:

Laura Bozzelli,

Hans van Ditmarsch,

Sophie PinchinatAuthors Info & Claims

Information and Computation, Volume 239, Issue C

Pages 303 - 339

https://doi.org/10.1016/j.ic.2014.07.013

Published: 01 December 2014 Publication History

Abstract

In this paper we present refinement modal logic. A refinement is like a bisimulation, except that from the three relational requirements only 'atoms' and 'back' need to be satisfied. Our logic contains a new operator in addition to the standard box modalities for each agent. The operator acts as a quantifier over the set of all refinements of a given model. As a variation on a bisimulation quantifier, this refinement operator or refinement quantifier can be seen as quantifying over a variable not occurring in the formula bound by it. The logic combines the simplicity of multi-agent modal logic with some powers of monadic second-order quantification. We present a sound and complete axiomatization of multi-agent refinement modal logic. We also present an extension of the logic to the modal µ-calculus, and an axiomatization for the single-agent version of this logic. Examples and applications are also discussed: to software verification and design (the set of agents can also be seen as a set of actions), and to dynamic epistemic logic. We further give detailed results on the complexity of satisfiability, and on succinctness.

References

[1]

P. Aczel, Non-Well-Founded Sets, CSLI Publications, Stanford, CA, 1988.

[2]

R. Alur, T.A. Henzinger, O. Kupferman, Alternating-Time Temporal Logic, 1998.

[3]

Rajeev Alur, Thomas A. Henzinger, Orna Kupferman, Moshe Y. Vardi, Alternating refinement relations, in: International Conference on Concurrency Theory, 1998, pp. 163-178.

Digital Library

[4]

Adam Antonik, Michael Huth, Kim G. Larsen, Ulrik Nyman, Andrzej Wasowski, 20 years of modal and mixed specifications, Bull. Eur. Assoc. Theor. Comput. Sci., 1 (2008).

[5]

A. Arnold, D. Niwinski, Rudiments of µ-Calculus, North Holland, 2001.

[6]

G. Aucher, Characterizing updates in dynamic epistemic logic, in: Proceedings of Twelfth KR, AAAI Press, 2010.

[7]

G. Aucher, DEL-sequents for regression and epistemic planning, J. Appl. Non-Class. Log., 22 (2012) 337-367.

[8]

P. Balbiani, A. Baltag, H. van Ditmarsch, A. Herzig, T. Hoshi, T. De Lima, 'Knowable' as 'known after an announcement', Rev. Symb. Log., 1 (2008) 305-334.

[9]

A. Baltag, L.S. Moss, S. Solecki, The logic of public announcements, common knowledge, and private suspicions, in: Proc. of 7th TARK, Morgan Kaufmann, 1998, pp. 43-56.

Digital Library

[10]

M. Bilkova, A. Palmigiano, Y. Venema, Proof systems for the coalgebraic cover modality, in: Advances in Modal Logic, College Publications, 2008, pp. 1-21.

[11]

P. Blackburn, M. de Rijke, Y. Venema, Modal Logic, Cambridge University Press, Cambridge, 2001.

Digital Library

[12]

Laura Bozzelli, Hans P. van Ditmarsch, Sophie Pinchinat, The complexity of one-agent refinement modal logic, in: Lecture Notes in Computer Science, vol. 7519, Springer, 2012, pp. 120-133.

Digital Library

[13]

M. Browne, E. Clarke, O. Grümberg, Characterizing Kripke structures in temporal logic, in: LNCS, vol. 249, Springer, 1987, pp. 256-270.

Digital Library

[14]

E.M. Clarke, E.A. Emerson, Design and verification of synchronization skeletons using branching time temporal logic, in: LNCS, vol. 131, Springer-Verlag, 1981, pp. 52-71.

Digital Library

[15]

G. d'Agostino, M. Hollenberg, Logical questions concerning the µ-calculus: interpolation, Lyndon and Los-Tarski, J. Symb. Log., 65 (2000) 310-332.

[16]

G. d'Agostino, G. Lenzi, An axiomatization of bisimulation quantifiers via the µ-calculus, Theor. Comput. Sci., 338 (2005) 64-95.

Digital Library

[17]

G. d'Agostino, G. Lenzi, A note on bisimulation quantifiers and fixed points over transitive frames, J. Log. Comput., 18 (2008) 601-614.

Digital Library

[18]

P. Economou, Extensions and applications of dynamic epistemic logic, Oxford University, 2010.

[19]

R. Fagin, J.Y. Halpern, Y. Moses, M.Y. Vardi, Reasoning about Knowledge, MIT Press, Cambridge MA, 1995.

Digital Library

[20]

Guillaume Feuillade, Sophie Pinchinat, Modal specifications for the control theory of discrete-event systems, Discrete Event Dyn. Syst., 17 (2007) 181-205.

Digital Library

[21]

K. Fine, Propositional quantifiers in modal logic, Theoria, 36 (1970) 336-346.

[22]

T. French, Bisimulation quantifiers for modal logic, University of Western Australia, 2006.

[23]

T. French, H. van Ditmarsch, Undecidability for arbitrary public announcement logic, in: Proc. of the Seventh Conference, College Publications, London, 2008, pp. 23-42.

[24]

J.D. Gerbrandy, W. Groeneveld, Reasoning about information change, J. Log. Lang. Inf., 6 (1997) 147-169.

Digital Library

[25]

J. Hales, Refinement quantifiers for logics of belief and knowledge, University of Western Australia, 2011.

[26]

J. Hales, Arbitrary action model logic and action model synthesis, in: Proc. of 28th LICS, IEEE, 2013, pp. 253-262.

Digital Library

[27]

J. Hales, T. French, R. Davies, Refinement quantified logics of knowledge, Electron. Notes Theor. Comput. Sci., 278 (2011) 85-98.

Digital Library

[28]

J. Hales, T. French, R. Davies, Refinement quantified logics of knowledge and belief for multiple agents, in: Advances in Modal Logic 9, College Publications, 2012, pp. 317-338.

[29]

D. Harel, D. Kozen, J. Tiuryn, Dynamic Logic, MIT Press, Cambridge MA, 2000.

Digital Library

[30]

D. Janin, I. Walukiewicz, Automata for the modal mu-calculus and related results, in: LNCS, vol. 969, Springer, 1995, pp. 552-562.

Digital Library

[31]

D. Janin, I. Walukiewicz, On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic, in: LNCS, vol. 1119, Springer, 1996, pp. 263-277.

Digital Library

[32]

B. Kooi, Expressivity and completeness for public update logics via reduction axioms, J. Appl. Non-Class. Log., 17 (2007) 231-254.

[33]

O. Kupferman, M. Vardi, P. Wolper, Module checking, Inf. Comput., 164 (2001) 322-344.

Digital Library

[34]

C. Kupke, A. Kurz, Y. Venema, Completeness of the finitary moss logic, in: Advances in Modal Logic 7, College Publications, 2008, pp. 193-217.

[35]

Ralf Küsters, Memoryless determinacy of parity games, in: Automata Logics, and Infinite Games, Springer, 2002, pp. 95-106.

Digital Library

[36]

Kim G. Larsen, Ulrik Nyman, Andrzej Wasowski, Modal I/O automata for interface and product line theories, in: Lecture Notes in Computer Science, vol. 4421, Springer, 2007, pp. 64-79.

Digital Library

[37]

A.R. Lomuscio, M.D. Ryan, An algorithmic approach to knowledge evolution, Artif. Intell. Eng. Des. Anal. Manuf. (AIEDAM), 13 (1998).

Digital Library

[38]

René Mazala, Infinite games, in: Automata Logics, and Infinite Games, 2002, pp. 197-204.

[39]

J.S. Miller, L.S. Moss, The undecidability of iterated modal relativization, Stud. Log., 79 (2005) 373-407.

[40]

C. Morgan, Programming from Specifications, Prentice Hall International, Hempstead, UK, 1994.

Digital Library

[41]

R. Parikh, L.S. Moss, C. Steinsvold, Topology and epistemic logic, in: Handbook of Spatial Logics, Springer Verlag, 2007, pp. 299-341.

[42]

M. Pauly, Logic for social software, University of Amsterdam, 2001.

[43]

J.A. Plaza, Logics of public communications, in: Proc. of the 4th ISMIS, Oak Ridge National Laboratory, 1989, pp. 201-216.

[44]

Jean-Baptiste Raclet, Quotient de spécifications pour la réutilisation de composants, Université de Rennes I, December 2007.

[45]

Jean-Baptiste Raclet, Residual for component specifications, in: Electr. Notes Theor. Comput. Sci., vol. 215, 2008, pp. 93-110.

Digital Library

[46]

Jean-Baptiste Raclet, Eric Badouel, Albert Benveniste, Benoit Caillaud, Roberto Passerone, Why are modalities good for interface theories?, in: Proceedings of the 9th International Conference on Application of Concurrency to System Design, IEEE Computer Society Press, 2009, pp. 119-127.

Digital Library

[47]

P. Ramadge, W. Wonham, On the supervisory control of discrete event systems, in: Proc. of the IEEE, 1989, pp. 81-98.

[48]

Stéphane Riedweg, Sophie Pinchinat, Quantified mu-calculus for control synthesis, in: Lecture Notes in Computer Science, vol. 2747, Springer, 2003, pp. 642-651.

[49]

M. Ryan, P.-Y. Schobbens, Agents and roles: refinement in alternating-time temporal logic, in: Revised Papers from the 8th International Workshop on Intelligent Agents VIII, Springer, 2002, pp. 100-114.

Digital Library

[50]

A.P. Sistla, M.Y. Vardi, P. Wolper, The complementation problem for Buchi automata with applications to temporal logic, Theor. Comput. Sci., 49 (1987) 217-237.

Digital Library

[51]

J. Tsitsoklis, On the control of discrete event dynamical systems, Math. Control Signals Syst., 2 (1989) 95-107.

[52]

J. van Benthem, An essay on sabotage and obstruction, in: LNCS, vol. 2605, Springer, 2005, pp. 268-276.

[53]

J. van Benthem, One is a lonely number: on the logic of communication, in: Lecture Notes in Logic, vol. 27, A.K. Peters, 2006, pp. 96-129.

[54]

H. van Ditmarsch, Quantifying notes, in: LNCS, vol. 7456, Springer, 2012, pp. 89-109.

[55]

H. van Ditmarsch, T. French, Simulation and information, in: LNAI, vol. 5605, Springer, 2009, pp. 51-65.

Digital Library

[56]

H. van Ditmarsch, T. French, S. Pinchinat, Future event logic - axioms and complexity, in: Advances in Modal Logic, vol. 8, College Publications, 2010, pp. 77-99.

[57]

H. van Ditmarsch, W. van der Hoek, B. Kooi, Dynamic epistemic logic, in: Synthese Library, vol. 337, Springer, 2007.

Digital Library

[58]

Y. Venema, Lecture notes on the modal µ-calculus, Draft, 2012.

[59]

I. Walukiewicz, Completeness of Kozen's axiomatisation of the propositional mu-calculus, in: INFCTRL: Information and Computation (Formerly Information and Control), vol. 157, 2000.

Digital Library

[60]

X. Wen, H. Liu, F. Huang, An alternative logic for knowability, in: LNCS, vol. 6953, Springer, 2011, pp. 342-355.

Digital Library

[61]

T. Wilke, CTL + is exponentially more succinct than CTL, in: LNCS, vol. 1738, Springer, 1999, pp. 110-121.

Digital Library

[62]

J. Woodcock, J. Davies, Using Z - Specification, Refinement and Proof, Prentice Hall, 1996.

Digital Library

Cited By

Ågotnes TGalimullin R(2023)Quantifying over information change with common knowledgeAutonomous Agents and Multi-Agent Systems10.1007/s10458-023-09601-037:1Online publication date: 8-Mar-2023
https://dl.acm.org/doi/10.1007/s10458-023-09601-0
Ågotnes TAlechina NGalimullin R(2022)Logics with Group Announcements and Distributed Knowledge: Completeness and Expressive PowerJournal of Logic, Language and Information10.1007/s10849-022-09355-031:2(141-166)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10849-022-09355-0
Galimullin RÅgotnes T(2022)Action Models for Coalition LogicDynamic Logic. New Trends and Applications10.1007/978-3-031-26622-5_5(73-89)Online publication date: 31-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-26622-5_5
Show More Cited By

Refinement modal logic
1. Theory of computation
  1. Logic
  2. Models of computation

Recommendations

On Modal Grzegorczyk Logic
Topics in Logic, Philosophy and Foundations of Mathematics and Computer Science. In Recognition of Professor Andrzej Grzegorczyk

In 1964-68 Andrzej Grzegorczyk investigated relational and topological semantics for the intuitionistic logic [15]-[18] . In this connection, following to McKinsey and Tarski, he also considered a semantics for modal logics. It is well known that there ...
On Modal Grzegorczyk Logic
Topics in Logic, Philosophy and Foundations of Mathematics and Computer Science. In Recognition of Professor Andrzej Grzegorczyk

In 1964-68 Andrzej Grzegorczyk investigated relational and topological semantics for the intuitionistic logic [15]-[18] . In this connection, following to McKinsey and Tarski, he also considered a semantics for modal logics. It is well known that there ...
Ground Nonmonotonic Modal Logic S5: New Results

We study logic programs under Gelfond's translation in the context of modal logic S5. We show that for arbitrary logic programs (propositional theories where logic negation is associated with default negation) ground nonmonotonic modal logics between T ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 239, Issue C

December 2014

376 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 December 2014

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ågotnes TGalimullin R(2023)Quantifying over information change with common knowledgeAutonomous Agents and Multi-Agent Systems10.1007/s10458-023-09601-037:1Online publication date: 8-Mar-2023
https://dl.acm.org/doi/10.1007/s10458-023-09601-0
Ågotnes TAlechina NGalimullin R(2022)Logics with Group Announcements and Distributed Knowledge: Completeness and Expressive PowerJournal of Logic, Language and Information10.1007/s10849-022-09355-031:2(141-166)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10849-022-09355-0
Galimullin RÅgotnes T(2022)Action Models for Coalition LogicDynamic Logic. New Trends and Applications10.1007/978-3-031-26622-5_5(73-89)Online publication date: 31-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-26622-5_5
van Ditmarsch HFrench THales J(2021)Positive AnnouncementsStudia Logica10.1007/s11225-020-09922-1109:3(639-681)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s11225-020-09922-1
Hatano RSano K(2021)Recapturing Dynamic Logic of Relation Changers via Bounded MorphismsStudia Logica10.1007/s11225-020-09902-5109:1(95-124)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s11225-020-09902-5
Galimullin R(2021)Coalition and Relativised Group Announcement LogicJournal of Logic, Language and Information10.1007/s10849-020-09327-230:3(451-489)Online publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1007/s10849-020-09327-2
Xiong ZÅgotnes T(2020)Arbitrary Propositional Network Announcement LogicDynamic Logic. New Trends and Applications10.1007/978-3-030-65840-3_17(277-293)Online publication date: 9-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-65840-3_17
Galimullin RÅgotnes TAlechina N(2019)Group Announcement Logic with Distributed KnowledgeLogic, Rationality, and Interaction10.1007/978-3-662-60292-8_8(98-111)Online publication date: 18-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-662-60292-8_8
(2017)The undecidability of arbitrary arrow update logicTheoretical Computer Science10.1016/j.tcs.2017.07.018693:C(1-12)Online publication date: 12-Sep-2017
https://dl.acm.org/doi/10.1016/j.tcs.2017.07.018
Guelev D(2017)Refining strategic ability in alternating-time temporal logicInformation and Computation10.1016/j.ic.2016.10.013254:P2(316-328)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.ic.2016.10.013
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents