nach oben

2020 | Buch

Kapitel lesen Erstes Kapitel lesen

Dynamic Logic. New Trends and Applications

Second International Workshop, DaLí 2019, Porto, Portugal, October 7–11, 2019, Proceedings

herausgegeben von: Luís Soares Barbosa, Alexandru Baltag

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the proceedings of the Second International Workshop on Dynamic Logic, DALI 2019, held in Porto, Portugal in October 2019.
The workshop was held in Porto, Portugal, on October 9, 2019, as part of the Formal Methods Week which hosted the 3rd World Congress on Formal Methods. The 12 full papers presented together with 2 short papers were carefully reviewed and selected from 26 submissions. The workshop is based on the project DaLí – Dynamic logics for cyber-physical systems: towards contract based design.

Inhaltsverzeichnis

Frontmatter

Regular Papers

Frontmatter

Mechanizing Bisimulation Theorems for Relation-Changing Logics in Coq

Abstract

Over the last years, the study of logics that can modify a model while evaluating a formula has gained in interest. Motivated by many examples in practice such as hybrid logics, separation logics and dynamic epistemic logics, the ability of updating a model has been investigated from a more general point of view. In this work, we formalize and verify in the proof assistant Coq, the bisimulation theorems for a particular family of dynamic logics that can change the accessibility relation of a model. The benefits of this formalization are twofold. First, our results apply for a wide variety of dynamic logics. Second, we argue that this is the first step towards the development of a modal logic library in Coq, which allows us to mechanize many relevant results in modal logics.

Raul Fervari, Francisco Trucco, Beta Ziliani

Behavioural and Abstractor Specifications for a Dynamic Logic with Binders and Silent Transitions

Abstract

We extend dynamic logic with binders (for state variables) by distinguishing between observable and silent transitions. This differentiation gives rise to two kinds of observational interpretations of the logic: abstractor and behavioural specifications. Abstractor specifications relax the standard model class semantics of a specification by considering its closure under weak bisimulation. Behavioural specifications, however, rely on a behavioural satisfaction relation which relaxes the interpretation of state variables and the satisfaction of modal formulas \(\langle \alpha \rangle \varphi \) and \([\alpha ]\varphi \) by abstracting from silent transitions. A formal relation between abstractor and behavioural specifications is provided which shows that both coincide semantically under mild conditions. For the proof we instantiate the previously introduced concept of a behaviour-abstractor framework to the case of dynamic logic with binders and silent transitions.

Rolf Hennicker, Alexander Knapp, Alexandre Madeira, Felix Mindt

The Logic of AGM Learning from Partial Observations

Abstract

We present a dynamic logic for inductive learning from partial observations by a “rational” learner, that obeys AGM postulates for belief revision. We apply our logic to an example, showing how various concrete properties can be learnt with certainty or inductively by such an AGM learner. We present a sound and complete axiomatization, based on a combination of relational and neighbourhood version of the canonical model method.

Alexandru Baltag, Aybüke Özgün, Ana Lucia Vargas-Sandoval

A Dynamic Epistemic Logic Analysis of the Equality Negation Task

Abstract

In this paper we study the solvability of the equality negation task in a simple wait-free model where processes communicate by reading and writing shared variables or exchanging messages. In this task, two processes start with a private input value in the set \(\left\{ 0,1,2 \right\} \), and after communicating, each one must decide a binary output value, so that the outputs of the processes are the same if and only if the input values of the processes are different. This task is already known to be unsolvable; our goal here is to prove this result using the dynamic epistemic logic (DEL) approach introduced by Goubault, Ledent and Rajsbaum in GandALF 2018. We show that in fact, there is no epistemic logic formula that explains why the task is unsolvable. We fix this issue by extending the language of our DEL framework, which allows us to construct such a formula, and discuss its utility.

Éric Goubault, Marijana Lazić, Jérémy Ledent, Sergio Rajsbaum

A Logical Analysis of the Interplay Between Social Influence and Friendship Selection

Abstract

This paper is part of a series of proposals for using logic to analyse social networks. It studies the intertwining of two forms of information dynamics: social influence, through which an agent’s behaviour, opinions or features are affected by those of her social connections, and friendship selection, through which an agent chooses her social connections based on their common behaviour, opinions or features. The text provides a logical analysis of the two forms of dynamics (the main ingredients in the phenomenon known as homophily) as well as of their interaction, discussing also some of their variations.

Sonja Smets, Fernando R. Velázquez-Quesada

A Four-Valued Hybrid Logic with Non-dual Modal Operators

Abstract

Hybrid logics are an extension of modal logics where it is possible to refer to a specific state, thus allowing the description of what happens at specific states, equalities and transitions between them. This makes hybrid logics very desirable to work with relational structures.

However, as the amount of information grows, it becomes increasingly more common to find inconsistencies. Information collected about a particular hybrid structure is not an exception. Rather than discarding all the data congregated, working with a paraconsistent type of logic allows us to keep it and still make sensible inferences.

In this paper we introduce a four-valued semantics for hybrid logic, where contradictions are allowed both at the level of propositional variables and accessibility relations. A distinguishing feature of this new logic is the fact that the classical equivalence between modal operators will be broken. A sound and complete tableau system is also presented.

Diana Costa, Manuel A. Martins

Persuasive Argumentation and Epistemic Attitudes

Abstract

This paper studies the relation between persuasive argumentation and the speaker’s epistemic attitude. Dung-style abstract argumentation and dynamic epistemic logic provide the necessary tools to characterize the notion of persuasion. Within abstract argumentation, persuasive argumentation has been previously studied from a game-theoretic perspective. These approaches are blind to the fact that, in real-life situations, the epistemic attitude of the speaker determines which set of arguments will be disclosed by her in the context of a persuasive dialogue. This work is a first step to fill this gap. For this purpose we extend one of the logics of Schwarzentruber et al. with dynamic operators, designed to capture communicative phenomena. A complete axiomatization for the new logic via reduction axioms is provided. Within the new framework, a distinction between actual persuasion and persuasion from the speaker’s perspective is made. Finally, we explore the relationship between the two notions.

Carlo Proietti, Antonio Yuste-Ginel

The Trace Modality

Abstract

We propose the trace modality, a concept to uniformly express a wide range of program verification problems. To demonstrate its usefulness, we formalize several program verification problems in it: Functional Verification, Information Flow Analysis, Temporal Model Checking, Program Synthesis, Correct Compilation, and Program Evolution. To reason about the trace modality, we translate programs and specifications to regular symbolic traces and construct simulation relations on first-order symbolic automata. The idea with this uniform representation is that it helps to identify synergy potential—theoretically and practically—between so far separate verification approaches.

Dominic Steinhöfel, Reiner Hähnle

Iterative Division in the Distributive Full Non-associative Lambek Calculus

Abstract

We study an extension of the Distributive Full Non-associative Lambek Calculus with iterative division operators. The iterative operators can be seen as representing iterative composition of linguistic resources or of actions. A complete axiomatization of the logic is provided and decidability is established via a proof of the finite model property.

Igor Sedlár

Resource Separation in Dynamic Logic of Propositional Assignments

Abstract

We extend dynamic logic of propositional assignments by adding an operator of parallel composition that is inspired by separation logics. We provide an axiomatisation via reduction axioms, thereby establishing decidability. We also prove that the complexity of both the model checking and the satisfiability problem stay in PSPACE.

Joseph Boudou, Andreas Herzig, Nicolas Troquard

Stit Semantics for Epistemic Notions Based on Information Disclosure in Interactive Settings

Abstract

We characterize four types of agentive knowledge using a stit semantics over branching discrete-time structures. These are ex ante knowledge, ex interim knowledge, ex post knowledge, and know-how. The first three are notions that arose from game-theoretical analyses on the stages of information disclosure across the decision making process, and the fourth has gained prominence both in logics of action and in deontic logic as a means to formalize ability. In recent years, logicians in AI have argued that any comprehensive study of responsibility attribution and blameworthiness should include proper treatment of these kinds of knowledge. This paper intends to clarify previous attempts to formalize them in stit logic and to propose alternative interpretations that in our opinion are more akin to the study of responsibility in the stit tradition. The logic we present uses an extension with knowledge operators of the Xstit language, and formulas are evaluated with respect to branching discrete-time models. We also present an axiomatic system for this logic, and address its soundness and completeness.

Aldo Iván Ramírez Abarca, Jan Broersen

Bringing Belief Base Change into Dynamic Epistemic Logic

Abstract

AGM’s belief revision is one of the main paradigms in the study of belief change operations. In this context, belief bases (prioritised bases) have been primarily used to specify the agent’s belief state. While the connection of iterated AGM-like operations and their encoding in dynamic epistemic logics have been studied before, few works considered how well-known postulates from iterated belief revision theory can be characterised by means of belief bases and their counterpart in dynamic epistemic logic. Particularly, it has been shown that some postulates can be characterised through transformations in priority graphs, while others may not be represented that way. This work investigates changes in the semantics of Dynamic Preference Logic that give rise to an appropriate syntactic representation for its models that allow us to represent and reason about iterated belief base change in this logic.

Marlo Souza, Álvaro Moreira

Short Papers

Frontmatter

A Dynamic Logic for QASM Programs

Abstract

We define a dynamic logic for QASM (Quantum Assembly) programming language, a language that requires the handling of quantum and probabilistic information. We provide a syntax and a model to this logic, providing a probabilistic semantics to the classical part. We exercise it with the quantum coin toss program.

Carlos Tavares

On the Construction of Multi-valued Concurrent Dynamic Logics

Abstract

Dynamic logic is a powerful framework for reasoning about imperative programs. An extension with a concurrent operator, called concurrent propositional dynamic logic (CPDL) [20], was introduced to formalise programs running in parallel. In a different direction, other authors proposed a systematic method for generating multi-valued propositional dynamic logics to reason about weighted programs [15]. This paper presents the first step of combining these two frameworks to introduce uncertainty in concurrent computations. In the proposed framework, a weight is assigned to each branch of the parallel execution, resulting in a (possible) asymmetric parallelism, inherent to the fuzzy programming paradigm [2, 23]. By adopting such an approach, a family of logics is obtained, called multi-valued concurrent propositional dynamic logics (\(\mathcal {GCDL}(\mathbf {A})\)), parametric on an action lattice \(\mathbf {A}\) specifying a notion of “weight” assigned to program execution. Additionally, the validity of some axioms of CPDL is discussed in the new family of generated logics.

Leandro Gomes

Backmatter

Titel: Dynamic Logic. New Trends and Applications
herausgegeben von: Luís Soares Barbosa
Alexandru Baltag
Verlag: Springer International Publishing
Electronic ISBN: 978-3-030-38808-9
Print ISBN: 978-3-030-38807-2
DOI: https://doi.org/10.1007/978-3-030-38808-9