The modal logic of copy and remove

被引:5
作者
Areces, Carlos [1 ,2 ]
van Ditmarsch, Hans [3 ,4 ]
Fervari, Raul [1 ,2 ]
Schwarzentruber, Francois [5 ]
机构
[1] Univ Nacl Cordoba, FaMAF, Cordoba, Argentina
[2] Consejo Nacl Invest Cient & Tecn, Cordoba, Argentina
[3] Univ Lorraine, CNRS, LORIA, Nancy, France
[4] IMSc, Madras, Tamil Nadu, India
[5] ENS Rennes, Rennes, France
基金
欧盟第七框架计划;
关键词
Modal logic; Dynamic epistemic logic; Complexity; Expressivity;
D O I
10.1016/j.ic.2017.01.004
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We propose a logic with the dynamic modal operators copy and remove. The copy operator replicates a given model, and the remove operator removes paths in a given model. We show that the product update by an action model in dynamic epistemic logic decomposes in copy and remove operations, when we consider action models with Boolean preconditions and no post-condition. We also show that copy and remove operators with paths of length 1 can be expressed by action models with post-conditions. We investigate the expressive power of the logic with copy and remove operations, together with the complexity of the satisfiability problem of some of its syntactic fragments. (C) 2017 Elsevier Inc. All rights reserved.
引用
收藏
页码:243 / 261
页数:19
相关论文
共 20 条
[1]  
[Anonymous], LOGIC PUBLIC ANNOUNC
[2]  
[Anonymous], 1999, Handbook of Tableau Methods
[3]  
[Anonymous], 2001, CAMBRIDGE TRACTS THE
[4]  
Areces Carlos, 2014, Logic, Language, Information, and Computation. 21st International Workshop, WoLLIC 2014. Proceedings: LNCS 8652, P51, DOI 10.1007/978-3-662-44145-9_4
[5]  
Areces Carlos, 2012, Logic, Language, Information and Computation. Proceedings of the 19th International Workshop, WoLLIC 2012, P142, DOI 10.1007/978-3-642-32621-9_11
[6]  
Areces C., 2015, LOG J IGPL
[7]   Swap logic [J].
Areces, Carlos ;
Fervari, Raul ;
Hoffmann, Guillaume .
LOGIC JOURNAL OF THE IGPL, 2014, 22 (02) :309-332
[8]  
Aucher G., 2013, COMPLEXITY DYNAMIC E, P19
[9]   Global and Local Graph Modifiers [J].
Aucher, Guillaume ;
Balbiani, Philippe ;
del Cerro, Luis Farinas ;
Herzig, Andreas .
ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2009, 231 :293-307
[10]  
Fervari R., 2014, THESIS