SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

LQP: the dynamic logic of quantum information

2006-06-01
Alexandru Baltag , Sonja Smets
The main contribution of this paper is the introduction of a dynamic logic formalism for reasoning about information flow in composite quantum systems. This builds on our previous work on … The main contribution of this paper is the introduction of a dynamic logic formalism for reasoning about information flow in composite quantum systems. This builds on our previous work on a complete quantum dynamic logic for single systems. Here we extend that work to a sound (but not necessarily complete) logic for composite systems, which brings together ideas from the quantum logic tradition with concepts from (dynamic) modal logic and from quantum computation. This Logic of Quantum Programs ( LQP ) is capable of expressing important features of quantum measurements and unitary evolutions of multi-partite states, as well as giving logical characterisations to various forms of entanglement (for example, the Bell states, the GHZ states etc.). We present a finitary syntax, a relational semantics and a sound proof system for this logic. As applications, we use our system to give formal correctness proofs for the Teleportation protocol and for a standard Quantum Secret Sharing protocol; a whole range of other quantum circuits and programs, including other well-known protocols (for example, superdense coding, entanglement swapping, logic-gate teleportation etc.), can be similarly verified using our logic.
View PDF Chat

Epistemic Actions as Resources

2007-03-21
Alexandru Baltag , Bob Coecke , Mehrnoosh Sadrzadeh
We provide an algebraic semantics together with a sound and complete sequent calculus for information update due to epistemic actions. This semantics is flexible enough to accommodate incomplete as well … We provide an algebraic semantics together with a sound and complete sequent calculus for information update due to epistemic actions. This semantics is flexible enough to accommodate incomplete as well as wrong information e.g. due to secrecy and deceit, as well as nested knowledge. We give a purely algebraic treatment of the muddy children puzzle, which moreover extends to situations where the children are allowed to lie and cheat. Epistemic actions, that is, information exchanges between agents A,B,…∈A⁠, are modeled as elements of a quantale. The quantale (Q,⋁,•) acts on an underlying Q-right module(M,⋁) of epistemic propositions and facts. The epistemic content is encoded by appearance maps, one pair fMA:M→M and fQA:Q→Q of (lax) morphisms for each agent A∈A⁠, which preserve the module and quantale structure respectively. By adjunction, they give rise to epistemic modalities, capturing the agents' knowledge on propositions and actions. The module action is epistemic update and gives rise to dynamic modalities—cf. weakest precondition. This model subsumes the crucial fragment of Baltag, Moss and Solecki's dynamic epistemic logic, abstracting it in a constructive fashion while introducing resource-sensitive structure on the epistemic actions.
View PDF Chat

The Logic of Quantum Programs.

2004-06-01
Alexandru Baltag , Sonja Smets
We present a logical calculus for reasoning about information flow in quantum programs. In particular we introduce a dynamic logic that is capable of dealing with quantum measurements, unitary evolutions … We present a logical calculus for reasoning about information flow in quantum programs. In particular we introduce a dynamic logic that is capable of dealing with quantum measurements, unitary evolutions and entanglements in compound quantum systems. We give a syntax and a relational semantics in which we abstract away from phases and probabilities. We present a sound proof system for this logic, and we show how to characterize by logical means various forms of entanglement (e.g. the Bell states) and various linear operators. As an example we sketch an analysis of the teleportation protocol.

A Simple Logic of Functional Dependence

2021-03-24
Alexandru Baltag , Johan van Benthem
Abstract This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within … Abstract This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within the setting of generalized assignment semantics for first order logic. The expressive strength, complete proof calculus and meta-properties of LFD are explored. Various language extensions are presented as well, up to undecidable modal-style logics for independence and dynamic logics of changing dependence models. Finally, more concrete settings for dependence are discussed: continuous dependence in topological models, linear dependence in vector spaces, and temporal dependence in dynamical systems and games.
View PDF Chat

On the Solvability of Inductive Problems: A Study in Epistemic Topology

2016-06-23
Alexandru Baltag , Nina Gierasimczuk , Sonja Smets
We investigate the issues of inductive problem-solving and learning by doxastic agents. We provide topological characterizations of solvability and learnability, and we use them to prove that AGM-style belief revision … We investigate the issues of inductive problem-solving and learning by doxastic agents. We provide topological characterizations of solvability and learnability, and we use them to prove that AGM-style belief revision is "universal", i.e., that every solvable problem is solvable by AGM conditioning.
View PDF Chat

Learning What Others Know

2020-05-27
Alexandru Baltag , Sonja Smets
We propose a number of powerful dynamic-epistemic logics for multi-agent information sharing and acts of publicly or privately accessing other agents’ information databases. The static base of our logics is … We propose a number of powerful dynamic-epistemic logics for multi-agent information sharing and acts of publicly or privately accessing other agents’ information databases. The static base of our logics is obtained by adding to standard epistemic logic comparative epistemic assertions for groups or individuals, as well as a common distributed knowledge operator (that combines features of both common knowledge and distributed knowledge). On the dynamic side, we introduce actions by which epistemic superiority can be acquired: “sharing all one knows” (by e.g. giving access to one’s information database to all or some of the other agents), as well as more complex informational events, such as hacking. We completely axiomatize several such logics and prove their decidability.
View PDF Chat

The Topological Mu-Calculus: completeness and decidability

2021-06-29
Alexandru Baltag , Nick Bezhanishvili , David Fernández‐Duque
We study the topological μ-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability and FMP over general topological spaces, as well as over T0 and TD spaces. … We study the topological μ-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability and FMP over general topological spaces, as well as over T0 and TD spaces. We also investigate relational μ-calculus, providing general completeness results for all natural fragments of μ-calculus over many different classes of relational frames. Unlike most other such proofs for μ-calculus, ours is modeltheoretic, making an innovative use of a known Modal Logic method (-the 'final' submodel of the canonical model), that has the twin advantages of great generality and essential simplicity.
View PDF Chat

On the Right Path: A Modal Logic for Supervised Learning

2019-01-01
Alexandru Baltag , Dazhu Li , Mina Young Pedersen
View PDF Chat

Evidence Logics with Relational Evidence

2017-01-01
Alexandru Baltag , Andrés Occhipinti
View PDF Chat

Epistemic actions as resources

2006-01-01
Alexandru Baltag , Bob Coecke , Mehrnoosh Sadrzadeh
We provide algebraic semantics together with a sound and complete sequent calculus for information update due to epistemic actions. This semantics is flexible enough to accommodate incomplete as well as … We provide algebraic semantics together with a sound and complete sequent calculus for information update due to epistemic actions. This semantics is flexible enough to accommodate incomplete as well as wrong information e.g.due to secrecy and deceit, as well as nested knowledge. We give a purely algebraic treatment of the muddy children puzzle, which moreover extends to situations where the children are allowed to lie and cheat. Epistemic actions, that is, information exchanges between agents, are modeled as elements of a quantale. The quantale acts on an underlying right module of epistemic propositions and facts. The epistemic content is encoded by appearance maps, one pair of (lax) morphisms for each agent, which preserve the module and quantale structure respectively. By adjunction, they give rise to epistemic modalities, capturing the agents' knowledge on propositions and actions. The module action is epistemic update and gives rise to dynamic modalities - cf. weakest precondition. This model subsumes the crucial fragment of Baltag, Moss and Solecki's dynamic epistemic logic, abstracting it in a constructive fashion while introducing resource-sensitive structure on the epistemic actions.

Learning Probabilities: Towards a Logic of Statistical Learning

2019-07-19
Alexandru Baltag , Soroush Rafiee Rad , Sonja Smets
We propose a new model for forming beliefs and learning about unknown probabilities (such as the probability of picking a red marble from a bag with an unknown distribution of … We propose a new model for forming beliefs and learning about unknown probabilities (such as the probability of picking a red marble from a bag with an unknown distribution of coloured marbles). The most widespread model for such situations of 'radical uncertainty' is in terms of imprecise probabilities, i.e. representing the agent's knowledge as a set of probability measures. We add to this model a plausibility map, associating to each measure a plausibility number, as a way to go beyond what is known with certainty and represent the agent's beliefs about probability. There are a number of standard examples: Shannon Entropy, Centre of Mass etc. We then consider learning of two types of information: (1) learning by repeated sampling from the unknown distribution (e.g. picking marbles from the bag); and (2) learning higher-order information about the distribution (in the shape of linear inequalities, e.g. we are told there are more red marbles than green marbles). The first changes only the plausibility map (via a 'plausibilistic' version of Bayes' Rule), but leaves the given set of measures unchanged; the second shrinks the set of measures, without changing their plausibility. Beliefs are defined as in Belief Revision Theory, in terms of truth in the most plausible worlds. But our belief change does not comply with standard AGM axioms, since the revision induced by (1) is of a non-AGM type. This is essential, as it allows our agents to learn the true probability: we prove that the beliefs obtained by repeated sampling converge almost surely to the correct belief (in the true probability). We end by sketching the contours of a dynamic doxastic logic for statistical learning.
View PDF Chat

The Topological Mu-Calculus: Completeness and Decidability

2023-09-07
Alexandru Baltag , Nick Bezhanishvili , David Fernández‐Duque
We study the topological μ-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability, and finite model property over general topological spaces, as well as over T 0 … We study the topological μ-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability, and finite model property over general topological spaces, as well as over T 0 and T D spaces. We also investigate the relational μ-calculus, providing general completeness results for all natural fragments of the μ-calculus over many different classes of relational frames. Unlike most other such proofs for μ-calculi, ours is model theoretic, making an innovative use of a known method from modal logic (the ‘final’ submodel of the canonical model), which has the twin advantages of great generality and essential simplicity.
View PDF Chat

The Logic of Quantum Programs

2021-01-01
Alexandru Baltag , Sonja Smets
We present a logical calculus for reasoning about information flow in quantum programs. In particular we introduce a dynamic logic that is capable of dealing with quantum measurements, unitary evolutions … We present a logical calculus for reasoning about information flow in quantum programs. In particular we introduce a dynamic logic that is capable of dealing with quantum measurements, unitary evolutions and entanglements in compound quantum systems. We give a syntax and a relational semantics in which we abstract away from phases and probabilities. We present a sound proof system for this logic, and we show how to characterize by logical means various forms of entanglement (e.g. the Bell states) and various linear operators. As an example we sketch an analysis of the teleportation protocol.

LQP: The Dynamic Logic of Quantum Information.

2021-10-04
Alexandru Baltag , Sonja Smets
The main contribution of this paper is the introduction of a dynamic logic formalism for reasoning about information flow in composite quantum systems. This builds on our previous work on … The main contribution of this paper is the introduction of a dynamic logic formalism for reasoning about information flow in composite quantum systems. This builds on our previous work on a complete quantum dynamic logic for single systems. Here we extend that work to a sound (but not necessarily complete) logic for composite systems, which brings together ideas from the quantum logic tradition with concepts from (dynamic) modal logic and from quantum computation. This Logic of Quantum Programs (LQP) is capable of expressing important features of quantum measurements and unitary evolutions of multi-partite states, as well as giving logical characterisations to various forms of entanglement (for example, the Bell states, the GHZ states etc.). We present a finitary syntax, a relational semantics and a sound proof system for this logic. As applications, we use our system to give formal correctness proofs for the Teleportation protocol and for a standard Quantum Secret Sharing protocol; a whole range of other quantum circuits and programs, including other well-known protocols (for example, superdense coding, entanglement swapping, logic-gate teleportation etc.), can be similarly verified using our logic.

Logics for Epistemic Actions: Completeness, Decidability, Expressivity

2023-06-12
Alexandru Baltag , Lawrence S. Moss , Sławomir Solecki
We build and study dynamic versions of epistemic logic. We study languages parameterized by an action signature that allows one to express epistemic actions such as (truthful) public announcements, completely … We build and study dynamic versions of epistemic logic. We study languages parameterized by an action signature that allows one to express epistemic actions such as (truthful) public announcements, completely private announcements to groups of agents, and more. The language L(Σ) is modeled on dynamic logic. Its sentence-building operations include modalities for the execution of programs, and for knowledge and common knowledge. Its program-building operations include action execution, composition, repetition, and choice. We consider two fragments of L(Σ). In L1(Σ), we drop action repetition; in L0(Σ), we also drop common knowledge. We present the syntax and semantics of these languages and sound proof systems for the validities in them. We prove the strong completeness of a logical system for L0(Σ) and the weak completeness of one for L1(Σ). We show the finite model property and, hence, decidability of L1(Σ). We translate L1(Σ) into PDL, obtaining a second proof of decidability. We prove results on expressive power, comparing L1(Σ) with modal logic together with transitive closure operators. We prove that a logical language with operators for private announcements is more expressive than one for public announcements.
View PDF Chat

Revisable Justified Belief: Preliminary Report.

2015-03-27
Alexandru Baltag , Bryan Renne , Sonja Smets
The theory $\mathsf{CDL}$ of Conditional Doxastic Logic is the single-agent version of Board's multi-agent theory $\mathsf{BRSIC}$ of conditional belief. $\mathsf{CDL}$ may be viewed as a version of AGM belief revision … The theory $\mathsf{CDL}$ of Conditional Doxastic Logic is the single-agent version of Board's multi-agent theory $\mathsf{BRSIC}$ of conditional belief. $\mathsf{CDL}$ may be viewed as a version of AGM belief revision theory in which Boolean combinations of revisions are expressible in the language. We introduce a theory $\mathsf{JCDL}$ of Justified Conditional Doxastic Logic that replaces conditional belief formulas $B^\psi\varphi$ by expressions $t{\,:^{\psi}}\varphi$ made up of a term $t$ whose syntactic structure suggests a derivation of the belief $\varphi$ after revision by $\psi$. This allows us to think of terms $t$ as reasons justifying a belief in various formulas after a revision takes place. We show that $\mathsf{JCDL}$-theorems are the exact analogs of $\mathsf{CDL}$-theorems, and that this result holds the other way around as well. This allows us to think of $\mathsf{JCDL}$ as a theory of revisable justified belief.

Evidence Logics with Relational Evidence

2017-06-19
Alexandru Baltag , Andrés Occhipinti Liberman
Dynamic evidence logics are logics for reasoning about the evidence and evidence-based beliefs of agents in a dynamic environment. In this paper, we introduce a family of logics for reasoning … Dynamic evidence logics are logics for reasoning about the evidence and evidence-based beliefs of agents in a dynamic environment. In this paper, we introduce a family of logics for reasoning about relational evidence: evidence that involves an orderings of states in terms of their relative plausibility. We provide sound and complete axiomatizations for the logics. We also present several evidential actions and prove soundness and completeness for the associated dynamic logics.

On the Right Path: A Modal Logic for Supervised Learning

2019-09-18
Alexandru Baltag , Dazhu Li , Mina Young Pedersen
Formal learning theory formalizes the process of inferring a general result from examples, as in the case of inferring grammars from sentences when learning a language. Although empirical evidence suggests … Formal learning theory formalizes the process of inferring a general result from examples, as in the case of inferring grammars from sentences when learning a language. Although empirical evidence suggests that children can learn a language without responding to the correction of linguistic mistakes, the importance of Teacher in many other paradigms is significant. Instead of focusing only on learner(s), this work develops a general framework---the supervised learning game (SLG)---to investigate the interaction between Teacher and Learner. In particular, our proposal highlights several interesting features of the agents: on the one hand,Learner may make mistakes in the learning process, and she may also ignore the potential relation between different hypotheses; on the other hand, Teacher is able to correct Learner's mistakes, eliminate potential mistakes and point out the facts ignored by Learner. To reason about strategies in this game, we develop a modal logic of supervised learning (SLL). Broadly, this work takes a small step towards studying the interaction between graph games, logics and formal learning theory.

Learning Probabilities: Towards a Logic of Statistical Learning.

2019-01-01
Alexandru Baltag , Soroush Rafiee Rad , Sonja Smets
We propose a new model for forming beliefs and learning about unknown probabilities (such as the probability of picking a red marble from a bag with an unknown distribution of … We propose a new model for forming beliefs and learning about unknown probabilities (such as the probability of picking a red marble from a bag with an unknown distribution of coloured marbles). The most widespread model for such situations of 'radical uncertainty' is in terms of imprecise probabilities, i.e. representing the agent's knowledge as a set of probability measures. We add to this model a plausibility map, associating to each measure a plausibility number, as a way to go beyond what is known with certainty and represent the agent's beliefs about probability. There are a number of standard examples: Shannon Entropy, Centre of Mass etc. We then consider learning of two types of information: (1) learning by repeated sampling from the unknown distribution (e.g. picking marbles from the bag); and (2) learning higher-order information about the distribution (in the shape of linear inequalities, e.g. we are told there are more red marbles than green marbles). The first changes only the plausibility map (via a 'plausibilistic' version of Bayes' Rule), but leaves the given set of measures unchanged; the second shrinks the set of measures, without changing their plausibility. Beliefs are defined as in Belief Revision Theory, in terms of truth in the most plausible worlds. But our belief change does not comply with standard AGM axioms, since the revision induced by (1) is of a non-AGM type. This is essential, as it allows our agents to learn the true probability: we prove that the beliefs obtained by repeated sampling converge almost surely to the correct belief (in the true probability). We end by sketching the contours of a dynamic doxastic logic for statistical learning.

Logics for Epistemic Actions: Completeness, Decidability, Expressivity

2022-01-01
Alexandru Baltag , Lawrence S. Moss , Sławomir Solecki
We consider dynamic versions of epistemic logic as formulated in Baltag and Moss "Logics for epistemic programs" (2004). That paper proposed a logical language (actually families of languages parameterized by … We consider dynamic versions of epistemic logic as formulated in Baltag and Moss "Logics for epistemic programs" (2004). That paper proposed a logical language (actually families of languages parameterized by action signatures) for dynamic epistemic logic. It had been shown that validity in the language is Pi-1-1-complete, so there are no recursively axiomatized complete logical systems for it. In contrast, this paper proves a weak completeness result for the fragment without action iteration, and a strong completeness result for the fragment without action iteration and common knowledge. Our work involves a detour into term rewriting theory. The argument uses modal filtration, and thus we obtain the finite model property and hence decidability. We also give a translation of our largest language into PDL, thereby obtaining a second proof of decidability. The paper closes with some results on expressive power. These are mostly concerned with comparing the action-iteration-free language with modal logic augmented by transitive closure operators. We answer a natural question about the languages we obtain by varying the action signature: we prove that a logical language with operators for private announcements is more expressive than one for public announcements.

A Logical Analysis of Dynamic Dependence

2022-01-01
Alexandru Baltag , Johan van Benthem , Dazhu Li
Many forms of dependence manifest themselves over time, with behavior of variables in dynamical systems as a paradigmatic example. This paper studies temporal dependence in dynamical systems from a logical … Many forms of dependence manifest themselves over time, with behavior of variables in dynamical systems as a paradigmatic example. This paper studies temporal dependence in dynamical systems from a logical perspective, by enriching a minimal modal base logic of static functional dependencies. We first introduce a logic for dynamical systems featuring temporalized variables, provide a complete axiomatic proof calculus, and show that its satisfiability problem is decidable. Then, to capture explicit reasoning about dynamic transition functions, we enhance the framework with function symbols and term identity. Next we combine temporalized variables with a modality for next-time truth from standard temporal logic, where modal correspondence analysis reveals the principles needed for a complete and decidable logic of timed dynamical systems supporting reductions between the two ways of referring to time. Our final result is an axiomatization of a general decidable logic of dependencies in arbitrary dynamical systems. We conclude with a brief outlook on how the systems introduced here mesh with richer temporal logics of system behavior, and with dynamic topological logic.
View PDF Chat

LQP: The Dynamic Logic of Quantum Information

2021-01-01
Alexandru Baltag , Sonja Smets
The main contribution of this paper is the introduction of a dynamic logic formalism for reasoning about information flow in composite quantum systems. This builds on our previous work on … The main contribution of this paper is the introduction of a dynamic logic formalism for reasoning about information flow in composite quantum systems. This builds on our previous work on a complete quantum dynamic logic for single systems. Here we extend that work to a sound (but not necessarily complete) logic for composite systems, which brings together ideas from the quantum logic tradition with concepts from (dynamic) modal logic and from quantum computation. This Logic of Quantum Programs (LQP) is capable of expressing important features of quantum measurements and unitary evolutions of multi-partite states, as well as giving logical characterisations to various forms of entanglement (for example, the Bell states, the GHZ states etc.). We present a finitary syntax, a relational semantics and a sound proof system for this logic. As applications, we use our system to give formal correctness proofs for the Teleportation protocol and for a standard Quantum Secret Sharing protocol; a whole range of other quantum circuits and programs, including other well-known protocols (for example, superdense coding, entanglement swapping, logic-gate teleportation etc.), can be similarly verified using our logic.
View PDF Chat

Learning What Others Know

2021-01-01
Alexandru Baltag , Sonja Smets
We propose a number of powerful dynamic-epistemic logics for multi-agent information sharing and acts of publicly or privately accessing other agents' information databases. The static base of our logics is … We propose a number of powerful dynamic-epistemic logics for multi-agent information sharing and acts of publicly or privately accessing other agents' information databases. The static base of our logics is obtained by adding to standard epistemic logic comparative epistemic assertions, that can express epistemic superiority between groups or individuals, as well as a common distributed knowledge operator (that combines features of both common knowledge and distributed knowledge). On the dynamic side, we introduce actions by which epistemic superiority can be acquired: "sharing all one knows" (by e.g. giving access to one's information database to all or some of the other agents), as well as more complex informational events, such as hacking. We completely axiomatize several such logics and prove their decidability.
View PDF Chat

The Topological Mu-Calculus: completeness and decidability

2021-01-01
Alexandru Baltag , Nick Bezhanishvili , David Fernández‐Duque
We study the topological $\mu$-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability and FMP over general topological spaces, as well as over $T_0$ and $T_D$ spaces. … We study the topological $\mu$-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability and FMP over general topological spaces, as well as over $T_0$ and $T_D$ spaces. We also investigate relational $\mu$-calculus, providing general completeness results for all natural fragments of $\mu$-calculus over many different classes of relational frames. Unlike most other such proofs for $\mu$-calculus, ours is model-theoretic, making an innovative use of a known Modal Logic method (--the 'final' submodel of the canonical model), that has the twin advantages of great generality and essential simplicity.
View PDF Chat

On the Right Path: A Modal Logic for Supervised Learning

2019-01-01
Alexandru Baltag , Dazhu Li , Mina Young Pedersen
Formal learning theory formalizes the process of inferring a general result from examples, as in the case of inferring grammars from sentences when learning a language. Although empirical evidence suggests … Formal learning theory formalizes the process of inferring a general result from examples, as in the case of inferring grammars from sentences when learning a language. Although empirical evidence suggests that children can learn a language without responding to the correction of linguistic mistakes, the importance of Teacher in many other paradigms is significant. Instead of focusing only on learner(s), this work develops a general framework---the supervised learning game (SLG)---to investigate the interaction between Teacher and Learner. In particular, our proposal highlights several interesting features of the agents: on the one hand,Learner may make mistakes in the learning process, and she may also ignore the potential relation between different hypotheses; on the other hand, Teacher is able to correct Learner's mistakes, eliminate potential mistakes and point out the facts ignored by Learner. To reason about strategies in this game, we develop a modal logic of supervised learning (SLL). Broadly, this work takes a small step towards studying the interaction between graph games, logics and formal learning theory.
View PDF Chat

Evidence Logics with Relational Evidence

2017-01-01
Alexandru Baltag , Andrés Occhipinti Liberman
Dynamic evidence logics are logics for reasoning about the evidence and evidence-based beliefs of agents in a dynamic environment. In this paper, we introduce a family of logics for reasoning … Dynamic evidence logics are logics for reasoning about the evidence and evidence-based beliefs of agents in a dynamic environment. In this paper, we introduce a family of logics for reasoning about relational evidence: evidence that involves an orderings of states in terms of their relative plausibility. We provide sound and complete axiomatizations for the logics. We also present several evidential actions and prove soundness and completeness for the associated dynamic logics.
View PDF Chat

Revisable Justified Belief: Preliminary Report

2015-01-01
Alexandru Baltag , Bryan Renne , Sonja Smets
The theory $\mathsf{CDL}$ of Conditional Doxastic Logic is the single-agent version of Board's multi-agent theory $\mathsf{BRSIC}$ of conditional belief. $\mathsf{CDL}$ may be viewed as a version of AGM belief revision … The theory $\mathsf{CDL}$ of Conditional Doxastic Logic is the single-agent version of Board's multi-agent theory $\mathsf{BRSIC}$ of conditional belief. $\mathsf{CDL}$ may be viewed as a version of AGM belief revision theory in which Boolean combinations of revisions are expressible in the language. We introduce a theory $\mathsf{JCDL}$ of Justified Conditional Doxastic Logic that replaces conditional belief formulas $B^\psi\varphi$ by expressions $t{\,:^{\psi}}\varphi$ made up of a term $t$ whose syntactic structure suggests a derivation of the belief $\varphi$ after revision by $\psi$. This allows us to think of terms $t$ as reasons justifying a belief in various formulas after a revision takes place. We show that $\mathsf{JCDL}$-theorems are the exact analogs of $\mathsf{CDL}$-theorems, and that this result holds the other way around as well. This allows us to think of $\mathsf{JCDL}$ as a theory of revisable justified belief.

A Dynamic-Epistemic Logic for Mobile Structured Agents

2012-01-01
Anya Yermakova , Alexandru Baltag
Multi-agent systems have been studied in various contexts of both application and theory. We take Dynamic Epistemic Logic (DEL), one of the formalisms designed to reason about such systems, as … Multi-agent systems have been studied in various contexts of both application and theory. We take Dynamic Epistemic Logic (DEL), one of the formalisms designed to reason about such systems, as the foundation of the language we will build. BioAmbient calculus is an extension of \pi-calculus, developed largely for applications to biomolecular systems. It deals with ambients and their ability to communicate and to execute concurrent processes while moving. In this paper we combine the formalism of Dynamic Epistemic Logic together with the formalism of BioAmbient Calculus in order to reason about knowledge maintained and gained upon process transitions. The motivation lies in developing a language that captures locally available information through assignment of knowledge, with potential application to biological systems as well as social, virtual, and others. We replace the ambients of BioAmbient Calculus with agents, to which we attribute knowledge, and explore the parallels of this treatment. The resulting logic describes the information flow governing mobile structured agents, organized hierarchically, whose architecture (and local information) may change due to actions such as communication, merging (of two agents), entering (of an agent into the inner structure of another agent) and exiting (of an agent from the structure of another). We show how the main axioms of DEL must be altered to accommodate the informational effects of the agents' dynamic architecture.
View PDF Chat

Logic meets Wigner's Friend (and their Friends)

2023-01-01
Alexandru Baltag , Sonja Smets
We take a fresh look at Wigner's Friend thought-experiment and some of its more recent variants and extensions, such as the Frauchiger-Renner (FR) Paradox. We discuss various solutions proposed in … We take a fresh look at Wigner's Friend thought-experiment and some of its more recent variants and extensions, such as the Frauchiger-Renner (FR) Paradox. We discuss various solutions proposed in the literature, focusing on a few questions: What is the correct epistemic interpretation of the multiplicity of state assignments in these scenarios? Under which conditions can one include classical observers into the quantum state descriptions, in a way that is still compatible with traditional Quantum Mechanics? Under which conditions can one system be admitted as an additional 'observer' from the perspective of another background observer? When can the standard axioms of multi-agent Epistemic Logic (that allow "knowledge transfer" between agents) be applied to quantum-physical observers? In the last part of the paper, we propose a new answer to these questions, sketch a particular formal implementation of this answer, and apply it to obtain a principled solution to Wigner Friend-type paradoxes.
View PDF Chat

Knowability as continuity: a topological account of informational dependence

2024-01-01
Alexandru Baltag , Johan van Benthem
We study knowable informational dependence between empirical questions, modeled as continuous functional dependence between variables in a topological setting. We also investigate epistemic independence in topological terms and show that … We study knowable informational dependence between empirical questions, modeled as continuous functional dependence between variables in a topological setting. We also investigate epistemic independence in topological terms and show that it is compatible with functional (but non-continuous) dependence. We then proceed to study a stronger notion of knowability based on uniformly continuous dependence. On the technical logical side, we determine the complete logics of languages that combine general functional dependence, continuous dependence, and uniformly continuous dependence.

Knowability as continuity: a topological account of informational dependence

2024-01-01
Alexandru Baltag , Johan van Benthem
We study knowable informational dependence between empirical questions, modeled as continuous functional dependence between variables in a topological setting. We also investigate epistemic independence in topological terms and show that … We study knowable informational dependence between empirical questions, modeled as continuous functional dependence between variables in a topological setting. We also investigate epistemic independence in topological terms and show that it is compatible with functional (but non-continuous) dependence. We then proceed to study a stronger notion of knowability based on uniformly continuous dependence. On the technical logical side, we determine the complete logics of languages that combine general functional dependence, continuous dependence, and uniformly continuous dependence.

The Topological Mu-Calculus: Completeness and Decidability

2023-09-07
Alexandru Baltag , Nick Bezhanishvili , David Fernández‐Duque
We study the topological μ-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability, and finite model property over general topological spaces, as well as over T 0 … We study the topological μ-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability, and finite model property over general topological spaces, as well as over T 0 and T D spaces. We also investigate the relational μ-calculus, providing general completeness results for all natural fragments of the μ-calculus over many different classes of relational frames. Unlike most other such proofs for μ-calculi, ours is model theoretic, making an innovative use of a known method from modal logic (the ‘final’ submodel of the canonical model), which has the twin advantages of great generality and essential simplicity.
View PDF Chat

Logics for Epistemic Actions: Completeness, Decidability, Expressivity

2023-06-12
Alexandru Baltag , Lawrence S. Moss , Sławomir Solecki
We build and study dynamic versions of epistemic logic. We study languages parameterized by an action signature that allows one to express epistemic actions such as (truthful) public announcements, completely … We build and study dynamic versions of epistemic logic. We study languages parameterized by an action signature that allows one to express epistemic actions such as (truthful) public announcements, completely private announcements to groups of agents, and more. The language L(Σ) is modeled on dynamic logic. Its sentence-building operations include modalities for the execution of programs, and for knowledge and common knowledge. Its program-building operations include action execution, composition, repetition, and choice. We consider two fragments of L(Σ). In L1(Σ), we drop action repetition; in L0(Σ), we also drop common knowledge. We present the syntax and semantics of these languages and sound proof systems for the validities in them. We prove the strong completeness of a logical system for L0(Σ) and the weak completeness of one for L1(Σ). We show the finite model property and, hence, decidability of L1(Σ). We translate L1(Σ) into PDL, obtaining a second proof of decidability. We prove results on expressive power, comparing L1(Σ) with modal logic together with transitive closure operators. We prove that a logical language with operators for private announcements is more expressive than one for public announcements.
View PDF Chat

Logic meets Wigner's Friend (and their Friends)

2023-01-01
Alexandru Baltag , Sonja Smets
We take a fresh look at Wigner's Friend thought-experiment and some of its more recent variants and extensions, such as the Frauchiger-Renner (FR) Paradox. We discuss various solutions proposed in … We take a fresh look at Wigner's Friend thought-experiment and some of its more recent variants and extensions, such as the Frauchiger-Renner (FR) Paradox. We discuss various solutions proposed in the literature, focusing on a few questions: What is the correct epistemic interpretation of the multiplicity of state assignments in these scenarios? Under which conditions can one include classical observers into the quantum state descriptions, in a way that is still compatible with traditional Quantum Mechanics? Under which conditions can one system be admitted as an additional 'observer' from the perspective of another background observer? When can the standard axioms of multi-agent Epistemic Logic (that allow "knowledge transfer" between agents) be applied to quantum-physical observers? In the last part of the paper, we propose a new answer to these questions, sketch a particular formal implementation of this answer, and apply it to obtain a principled solution to Wigner Friend-type paradoxes.
View PDF Chat

Logics for Epistemic Actions: Completeness, Decidability, Expressivity

2022-01-01
Alexandru Baltag , Lawrence S. Moss , Sławomir Solecki
We consider dynamic versions of epistemic logic as formulated in Baltag and Moss "Logics for epistemic programs" (2004). That paper proposed a logical language (actually families of languages parameterized by … We consider dynamic versions of epistemic logic as formulated in Baltag and Moss "Logics for epistemic programs" (2004). That paper proposed a logical language (actually families of languages parameterized by action signatures) for dynamic epistemic logic. It had been shown that validity in the language is Pi-1-1-complete, so there are no recursively axiomatized complete logical systems for it. In contrast, this paper proves a weak completeness result for the fragment without action iteration, and a strong completeness result for the fragment without action iteration and common knowledge. Our work involves a detour into term rewriting theory. The argument uses modal filtration, and thus we obtain the finite model property and hence decidability. We also give a translation of our largest language into PDL, thereby obtaining a second proof of decidability. The paper closes with some results on expressive power. These are mostly concerned with comparing the action-iteration-free language with modal logic augmented by transitive closure operators. We answer a natural question about the languages we obtain by varying the action signature: we prove that a logical language with operators for private announcements is more expressive than one for public announcements.

A Logical Analysis of Dynamic Dependence

2022-01-01
Alexandru Baltag , Johan van Benthem , Dazhu Li
Many forms of dependence manifest themselves over time, with behavior of variables in dynamical systems as a paradigmatic example. This paper studies temporal dependence in dynamical systems from a logical … Many forms of dependence manifest themselves over time, with behavior of variables in dynamical systems as a paradigmatic example. This paper studies temporal dependence in dynamical systems from a logical perspective, by enriching a minimal modal base logic of static functional dependencies. We first introduce a logic for dynamical systems featuring temporalized variables, provide a complete axiomatic proof calculus, and show that its satisfiability problem is decidable. Then, to capture explicit reasoning about dynamic transition functions, we enhance the framework with function symbols and term identity. Next we combine temporalized variables with a modality for next-time truth from standard temporal logic, where modal correspondence analysis reveals the principles needed for a complete and decidable logic of timed dynamical systems supporting reductions between the two ways of referring to time. Our final result is an axiomatization of a general decidable logic of dependencies in arbitrary dynamical systems. We conclude with a brief outlook on how the systems introduced here mesh with richer temporal logics of system behavior, and with dynamic topological logic.
View PDF Chat

LQP: The Dynamic Logic of Quantum Information.

2021-10-04
Alexandru Baltag , Sonja Smets
The main contribution of this paper is the introduction of a dynamic logic formalism for reasoning about information flow in composite quantum systems. This builds on our previous work on … The main contribution of this paper is the introduction of a dynamic logic formalism for reasoning about information flow in composite quantum systems. This builds on our previous work on a complete quantum dynamic logic for single systems. Here we extend that work to a sound (but not necessarily complete) logic for composite systems, which brings together ideas from the quantum logic tradition with concepts from (dynamic) modal logic and from quantum computation. This Logic of Quantum Programs (LQP) is capable of expressing important features of quantum measurements and unitary evolutions of multi-partite states, as well as giving logical characterisations to various forms of entanglement (for example, the Bell states, the GHZ states etc.). We present a finitary syntax, a relational semantics and a sound proof system for this logic. As applications, we use our system to give formal correctness proofs for the Teleportation protocol and for a standard Quantum Secret Sharing protocol; a whole range of other quantum circuits and programs, including other well-known protocols (for example, superdense coding, entanglement swapping, logic-gate teleportation etc.), can be similarly verified using our logic.

The Topological Mu-Calculus: completeness and decidability

2021-06-29
Alexandru Baltag , Nick Bezhanishvili , David Fernández‐Duque
We study the topological μ-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability and FMP over general topological spaces, as well as over T0 and TD spaces. … We study the topological μ-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability and FMP over general topological spaces, as well as over T0 and TD spaces. We also investigate relational μ-calculus, providing general completeness results for all natural fragments of μ-calculus over many different classes of relational frames. Unlike most other such proofs for μ-calculus, ours is modeltheoretic, making an innovative use of a known Modal Logic method (-the 'final' submodel of the canonical model), that has the twin advantages of great generality and essential simplicity.
View PDF Chat

A Simple Logic of Functional Dependence

2021-03-24
Alexandru Baltag , Johan van Benthem
Abstract This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within … Abstract This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within the setting of generalized assignment semantics for first order logic. The expressive strength, complete proof calculus and meta-properties of LFD are explored. Various language extensions are presented as well, up to undecidable modal-style logics for independence and dynamic logics of changing dependence models. Finally, more concrete settings for dependence are discussed: continuous dependence in topological models, linear dependence in vector spaces, and temporal dependence in dynamical systems and games.
View PDF Chat

The Logic of Quantum Programs

2021-01-01
Alexandru Baltag , Sonja Smets
We present a logical calculus for reasoning about information flow in quantum programs. In particular we introduce a dynamic logic that is capable of dealing with quantum measurements, unitary evolutions … We present a logical calculus for reasoning about information flow in quantum programs. In particular we introduce a dynamic logic that is capable of dealing with quantum measurements, unitary evolutions and entanglements in compound quantum systems. We give a syntax and a relational semantics in which we abstract away from phases and probabilities. We present a sound proof system for this logic, and we show how to characterize by logical means various forms of entanglement (e.g. the Bell states) and various linear operators. As an example we sketch an analysis of the teleportation protocol.

LQP: The Dynamic Logic of Quantum Information

2021-01-01
Alexandru Baltag , Sonja Smets
The main contribution of this paper is the introduction of a dynamic logic formalism for reasoning about information flow in composite quantum systems. This builds on our previous work on … The main contribution of this paper is the introduction of a dynamic logic formalism for reasoning about information flow in composite quantum systems. This builds on our previous work on a complete quantum dynamic logic for single systems. Here we extend that work to a sound (but not necessarily complete) logic for composite systems, which brings together ideas from the quantum logic tradition with concepts from (dynamic) modal logic and from quantum computation. This Logic of Quantum Programs (LQP) is capable of expressing important features of quantum measurements and unitary evolutions of multi-partite states, as well as giving logical characterisations to various forms of entanglement (for example, the Bell states, the GHZ states etc.). We present a finitary syntax, a relational semantics and a sound proof system for this logic. As applications, we use our system to give formal correctness proofs for the Teleportation protocol and for a standard Quantum Secret Sharing protocol; a whole range of other quantum circuits and programs, including other well-known protocols (for example, superdense coding, entanglement swapping, logic-gate teleportation etc.), can be similarly verified using our logic.
View PDF Chat

Learning What Others Know

2021-01-01
Alexandru Baltag , Sonja Smets
We propose a number of powerful dynamic-epistemic logics for multi-agent information sharing and acts of publicly or privately accessing other agents' information databases. The static base of our logics is … We propose a number of powerful dynamic-epistemic logics for multi-agent information sharing and acts of publicly or privately accessing other agents' information databases. The static base of our logics is obtained by adding to standard epistemic logic comparative epistemic assertions, that can express epistemic superiority between groups or individuals, as well as a common distributed knowledge operator (that combines features of both common knowledge and distributed knowledge). On the dynamic side, we introduce actions by which epistemic superiority can be acquired: "sharing all one knows" (by e.g. giving access to one's information database to all or some of the other agents), as well as more complex informational events, such as hacking. We completely axiomatize several such logics and prove their decidability.
View PDF Chat

The Topological Mu-Calculus: completeness and decidability

2021-01-01
Alexandru Baltag , Nick Bezhanishvili , David Fernández‐Duque
We study the topological $\mu$-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability and FMP over general topological spaces, as well as over $T_0$ and $T_D$ spaces. … We study the topological $\mu$-calculus, based on both Cantor derivative and closure modalities, proving completeness, decidability and FMP over general topological spaces, as well as over $T_0$ and $T_D$ spaces. We also investigate relational $\mu$-calculus, providing general completeness results for all natural fragments of $\mu$-calculus over many different classes of relational frames. Unlike most other such proofs for $\mu$-calculus, ours is model-theoretic, making an innovative use of a known Modal Logic method (--the 'final' submodel of the canonical model), that has the twin advantages of great generality and essential simplicity.
View PDF Chat

Learning What Others Know

2020-05-27
Alexandru Baltag , Sonja Smets
We propose a number of powerful dynamic-epistemic logics for multi-agent information sharing and acts of publicly or privately accessing other agents’ information databases. The static base of our logics is … We propose a number of powerful dynamic-epistemic logics for multi-agent information sharing and acts of publicly or privately accessing other agents’ information databases. The static base of our logics is obtained by adding to standard epistemic logic comparative epistemic assertions for groups or individuals, as well as a common distributed knowledge operator (that combines features of both common knowledge and distributed knowledge). On the dynamic side, we introduce actions by which epistemic superiority can be acquired: “sharing all one knows” (by e.g. giving access to one’s information database to all or some of the other agents), as well as more complex informational events, such as hacking. We completely axiomatize several such logics and prove their decidability.
View PDF Chat

On the Right Path: A Modal Logic for Supervised Learning

2019-09-18
Alexandru Baltag , Dazhu Li , Mina Young Pedersen
Formal learning theory formalizes the process of inferring a general result from examples, as in the case of inferring grammars from sentences when learning a language. Although empirical evidence suggests … Formal learning theory formalizes the process of inferring a general result from examples, as in the case of inferring grammars from sentences when learning a language. Although empirical evidence suggests that children can learn a language without responding to the correction of linguistic mistakes, the importance of Teacher in many other paradigms is significant. Instead of focusing only on learner(s), this work develops a general framework---the supervised learning game (SLG)---to investigate the interaction between Teacher and Learner. In particular, our proposal highlights several interesting features of the agents: on the one hand,Learner may make mistakes in the learning process, and she may also ignore the potential relation between different hypotheses; on the other hand, Teacher is able to correct Learner's mistakes, eliminate potential mistakes and point out the facts ignored by Learner. To reason about strategies in this game, we develop a modal logic of supervised learning (SLL). Broadly, this work takes a small step towards studying the interaction between graph games, logics and formal learning theory.

Learning Probabilities: Towards a Logic of Statistical Learning

2019-07-19
Alexandru Baltag , Soroush Rafiee Rad , Sonja Smets
We propose a new model for forming beliefs and learning about unknown probabilities (such as the probability of picking a red marble from a bag with an unknown distribution of … We propose a new model for forming beliefs and learning about unknown probabilities (such as the probability of picking a red marble from a bag with an unknown distribution of coloured marbles). The most widespread model for such situations of 'radical uncertainty' is in terms of imprecise probabilities, i.e. representing the agent's knowledge as a set of probability measures. We add to this model a plausibility map, associating to each measure a plausibility number, as a way to go beyond what is known with certainty and represent the agent's beliefs about probability. There are a number of standard examples: Shannon Entropy, Centre of Mass etc. We then consider learning of two types of information: (1) learning by repeated sampling from the unknown distribution (e.g. picking marbles from the bag); and (2) learning higher-order information about the distribution (in the shape of linear inequalities, e.g. we are told there are more red marbles than green marbles). The first changes only the plausibility map (via a 'plausibilistic' version of Bayes' Rule), but leaves the given set of measures unchanged; the second shrinks the set of measures, without changing their plausibility. Beliefs are defined as in Belief Revision Theory, in terms of truth in the most plausible worlds. But our belief change does not comply with standard AGM axioms, since the revision induced by (1) is of a non-AGM type. This is essential, as it allows our agents to learn the true probability: we prove that the beliefs obtained by repeated sampling converge almost surely to the correct belief (in the true probability). We end by sketching the contours of a dynamic doxastic logic for statistical learning.
View PDF Chat

Learning Probabilities: Towards a Logic of Statistical Learning.

2019-01-01
Alexandru Baltag , Soroush Rafiee Rad , Sonja Smets
We propose a new model for forming beliefs and learning about unknown probabilities (such as the probability of picking a red marble from a bag with an unknown distribution of … We propose a new model for forming beliefs and learning about unknown probabilities (such as the probability of picking a red marble from a bag with an unknown distribution of coloured marbles). The most widespread model for such situations of 'radical uncertainty' is in terms of imprecise probabilities, i.e. representing the agent's knowledge as a set of probability measures. We add to this model a plausibility map, associating to each measure a plausibility number, as a way to go beyond what is known with certainty and represent the agent's beliefs about probability. There are a number of standard examples: Shannon Entropy, Centre of Mass etc. We then consider learning of two types of information: (1) learning by repeated sampling from the unknown distribution (e.g. picking marbles from the bag); and (2) learning higher-order information about the distribution (in the shape of linear inequalities, e.g. we are told there are more red marbles than green marbles). The first changes only the plausibility map (via a 'plausibilistic' version of Bayes' Rule), but leaves the given set of measures unchanged; the second shrinks the set of measures, without changing their plausibility. Beliefs are defined as in Belief Revision Theory, in terms of truth in the most plausible worlds. But our belief change does not comply with standard AGM axioms, since the revision induced by (1) is of a non-AGM type. This is essential, as it allows our agents to learn the true probability: we prove that the beliefs obtained by repeated sampling converge almost surely to the correct belief (in the true probability). We end by sketching the contours of a dynamic doxastic logic for statistical learning.

On the Right Path: A Modal Logic for Supervised Learning

2019-01-01
Alexandru Baltag , Dazhu Li , Mina Young Pedersen
View PDF Chat

On the Right Path: A Modal Logic for Supervised Learning

2019-01-01
Alexandru Baltag , Dazhu Li , Mina Young Pedersen
Formal learning theory formalizes the process of inferring a general result from examples, as in the case of inferring grammars from sentences when learning a language. Although empirical evidence suggests … Formal learning theory formalizes the process of inferring a general result from examples, as in the case of inferring grammars from sentences when learning a language. Although empirical evidence suggests that children can learn a language without responding to the correction of linguistic mistakes, the importance of Teacher in many other paradigms is significant. Instead of focusing only on learner(s), this work develops a general framework---the supervised learning game (SLG)---to investigate the interaction between Teacher and Learner. In particular, our proposal highlights several interesting features of the agents: on the one hand,Learner may make mistakes in the learning process, and she may also ignore the potential relation between different hypotheses; on the other hand, Teacher is able to correct Learner's mistakes, eliminate potential mistakes and point out the facts ignored by Learner. To reason about strategies in this game, we develop a modal logic of supervised learning (SLL). Broadly, this work takes a small step towards studying the interaction between graph games, logics and formal learning theory.
View PDF Chat

Evidence Logics with Relational Evidence

2017-06-19
Alexandru Baltag , Andrés Occhipinti Liberman
Dynamic evidence logics are logics for reasoning about the evidence and evidence-based beliefs of agents in a dynamic environment. In this paper, we introduce a family of logics for reasoning … Dynamic evidence logics are logics for reasoning about the evidence and evidence-based beliefs of agents in a dynamic environment. In this paper, we introduce a family of logics for reasoning about relational evidence: evidence that involves an orderings of states in terms of their relative plausibility. We provide sound and complete axiomatizations for the logics. We also present several evidential actions and prove soundness and completeness for the associated dynamic logics.

Evidence Logics with Relational Evidence

2017-01-01
Alexandru Baltag , Andrés Occhipinti
View PDF Chat

Evidence Logics with Relational Evidence

2017-01-01
Alexandru Baltag , Andrés Occhipinti Liberman
Dynamic evidence logics are logics for reasoning about the evidence and evidence-based beliefs of agents in a dynamic environment. In this paper, we introduce a family of logics for reasoning … Dynamic evidence logics are logics for reasoning about the evidence and evidence-based beliefs of agents in a dynamic environment. In this paper, we introduce a family of logics for reasoning about relational evidence: evidence that involves an orderings of states in terms of their relative plausibility. We provide sound and complete axiomatizations for the logics. We also present several evidential actions and prove soundness and completeness for the associated dynamic logics.
View PDF Chat

On the Solvability of Inductive Problems: A Study in Epistemic Topology

2016-06-23
Alexandru Baltag , Nina Gierasimczuk , Sonja Smets
We investigate the issues of inductive problem-solving and learning by doxastic agents. We provide topological characterizations of solvability and learnability, and we use them to prove that AGM-style belief revision … We investigate the issues of inductive problem-solving and learning by doxastic agents. We provide topological characterizations of solvability and learnability, and we use them to prove that AGM-style belief revision is "universal", i.e., that every solvable problem is solvable by AGM conditioning.
View PDF Chat

Revisable Justified Belief: Preliminary Report.

2015-03-27
Alexandru Baltag , Bryan Renne , Sonja Smets
The theory $\mathsf{CDL}$ of Conditional Doxastic Logic is the single-agent version of Board's multi-agent theory $\mathsf{BRSIC}$ of conditional belief. $\mathsf{CDL}$ may be viewed as a version of AGM belief revision … The theory $\mathsf{CDL}$ of Conditional Doxastic Logic is the single-agent version of Board's multi-agent theory $\mathsf{BRSIC}$ of conditional belief. $\mathsf{CDL}$ may be viewed as a version of AGM belief revision theory in which Boolean combinations of revisions are expressible in the language. We introduce a theory $\mathsf{JCDL}$ of Justified Conditional Doxastic Logic that replaces conditional belief formulas $B^\psi\varphi$ by expressions $t{\,:^{\psi}}\varphi$ made up of a term $t$ whose syntactic structure suggests a derivation of the belief $\varphi$ after revision by $\psi$. This allows us to think of terms $t$ as reasons justifying a belief in various formulas after a revision takes place. We show that $\mathsf{JCDL}$-theorems are the exact analogs of $\mathsf{CDL}$-theorems, and that this result holds the other way around as well. This allows us to think of $\mathsf{JCDL}$ as a theory of revisable justified belief.

Revisable Justified Belief: Preliminary Report

2015-01-01
Alexandru Baltag , Bryan Renne , Sonja Smets
The theory $\mathsf{CDL}$ of Conditional Doxastic Logic is the single-agent version of Board's multi-agent theory $\mathsf{BRSIC}$ of conditional belief. $\mathsf{CDL}$ may be viewed as a version of AGM belief revision … The theory $\mathsf{CDL}$ of Conditional Doxastic Logic is the single-agent version of Board's multi-agent theory $\mathsf{BRSIC}$ of conditional belief. $\mathsf{CDL}$ may be viewed as a version of AGM belief revision theory in which Boolean combinations of revisions are expressible in the language. We introduce a theory $\mathsf{JCDL}$ of Justified Conditional Doxastic Logic that replaces conditional belief formulas $B^\psi\varphi$ by expressions $t{\,:^{\psi}}\varphi$ made up of a term $t$ whose syntactic structure suggests a derivation of the belief $\varphi$ after revision by $\psi$. This allows us to think of terms $t$ as reasons justifying a belief in various formulas after a revision takes place. We show that $\mathsf{JCDL}$-theorems are the exact analogs of $\mathsf{CDL}$-theorems, and that this result holds the other way around as well. This allows us to think of $\mathsf{JCDL}$ as a theory of revisable justified belief.

A Dynamic-Epistemic Logic for Mobile Structured Agents

2012-01-01
Anya Yermakova , Alexandru Baltag
Multi-agent systems have been studied in various contexts of both application and theory. We take Dynamic Epistemic Logic (DEL), one of the formalisms designed to reason about such systems, as … Multi-agent systems have been studied in various contexts of both application and theory. We take Dynamic Epistemic Logic (DEL), one of the formalisms designed to reason about such systems, as the foundation of the language we will build. BioAmbient calculus is an extension of \pi-calculus, developed largely for applications to biomolecular systems. It deals with ambients and their ability to communicate and to execute concurrent processes while moving. In this paper we combine the formalism of Dynamic Epistemic Logic together with the formalism of BioAmbient Calculus in order to reason about knowledge maintained and gained upon process transitions. The motivation lies in developing a language that captures locally available information through assignment of knowledge, with potential application to biological systems as well as social, virtual, and others. We replace the ambients of BioAmbient Calculus with agents, to which we attribute knowledge, and explore the parallels of this treatment. The resulting logic describes the information flow governing mobile structured agents, organized hierarchically, whose architecture (and local information) may change due to actions such as communication, merging (of two agents), entering (of an agent into the inner structure of another agent) and exiting (of an agent from the structure of another). We show how the main axioms of DEL must be altered to accommodate the informational effects of the agents' dynamic architecture.
View PDF Chat

Epistemic Actions as Resources

2007-03-21
Alexandru Baltag , Bob Coecke , Mehrnoosh Sadrzadeh
We provide an algebraic semantics together with a sound and complete sequent calculus for information update due to epistemic actions. This semantics is flexible enough to accommodate incomplete as well … We provide an algebraic semantics together with a sound and complete sequent calculus for information update due to epistemic actions. This semantics is flexible enough to accommodate incomplete as well as wrong information e.g. due to secrecy and deceit, as well as nested knowledge. We give a purely algebraic treatment of the muddy children puzzle, which moreover extends to situations where the children are allowed to lie and cheat. Epistemic actions, that is, information exchanges between agents A,B,…∈A⁠, are modeled as elements of a quantale. The quantale (Q,⋁,•) acts on an underlying Q-right module(M,⋁) of epistemic propositions and facts. The epistemic content is encoded by appearance maps, one pair fMA:M→M and fQA:Q→Q of (lax) morphisms for each agent A∈A⁠, which preserve the module and quantale structure respectively. By adjunction, they give rise to epistemic modalities, capturing the agents' knowledge on propositions and actions. The module action is epistemic update and gives rise to dynamic modalities—cf. weakest precondition. This model subsumes the crucial fragment of Baltag, Moss and Solecki's dynamic epistemic logic, abstracting it in a constructive fashion while introducing resource-sensitive structure on the epistemic actions.
View PDF Chat

LQP: the dynamic logic of quantum information

2006-06-01
Alexandru Baltag , Sonja Smets
The main contribution of this paper is the introduction of a dynamic logic formalism for reasoning about information flow in composite quantum systems. This builds on our previous work on … The main contribution of this paper is the introduction of a dynamic logic formalism for reasoning about information flow in composite quantum systems. This builds on our previous work on a complete quantum dynamic logic for single systems. Here we extend that work to a sound (but not necessarily complete) logic for composite systems, which brings together ideas from the quantum logic tradition with concepts from (dynamic) modal logic and from quantum computation. This Logic of Quantum Programs ( LQP ) is capable of expressing important features of quantum measurements and unitary evolutions of multi-partite states, as well as giving logical characterisations to various forms of entanglement (for example, the Bell states, the GHZ states etc.). We present a finitary syntax, a relational semantics and a sound proof system for this logic. As applications, we use our system to give formal correctness proofs for the Teleportation protocol and for a standard Quantum Secret Sharing protocol; a whole range of other quantum circuits and programs, including other well-known protocols (for example, superdense coding, entanglement swapping, logic-gate teleportation etc.), can be similarly verified using our logic.
View PDF Chat

Epistemic actions as resources

2006-01-01
Alexandru Baltag , Bob Coecke , Mehrnoosh Sadrzadeh
We provide algebraic semantics together with a sound and complete sequent calculus for information update due to epistemic actions. This semantics is flexible enough to accommodate incomplete as well as … We provide algebraic semantics together with a sound and complete sequent calculus for information update due to epistemic actions. This semantics is flexible enough to accommodate incomplete as well as wrong information e.g.due to secrecy and deceit, as well as nested knowledge. We give a purely algebraic treatment of the muddy children puzzle, which moreover extends to situations where the children are allowed to lie and cheat. Epistemic actions, that is, information exchanges between agents, are modeled as elements of a quantale. The quantale acts on an underlying right module of epistemic propositions and facts. The epistemic content is encoded by appearance maps, one pair of (lax) morphisms for each agent, which preserve the module and quantale structure respectively. By adjunction, they give rise to epistemic modalities, capturing the agents' knowledge on propositions and actions. The module action is epistemic update and gives rise to dynamic modalities - cf. weakest precondition. This model subsumes the crucial fragment of Baltag, Moss and Solecki's dynamic epistemic logic, abstracting it in a constructive fashion while introducing resource-sensitive structure on the epistemic actions.

The Logic of Quantum Programs.

2004-06-01
Alexandru Baltag , Sonja Smets
We present a logical calculus for reasoning about information flow in quantum programs. In particular we introduce a dynamic logic that is capable of dealing with quantum measurements, unitary evolutions … We present a logical calculus for reasoning about information flow in quantum programs. In particular we introduce a dynamic logic that is capable of dealing with quantum measurements, unitary evolutions and entanglements in compound quantum systems. We give a syntax and a relational semantics in which we abstract away from phases and probabilities. We present a sound proof system for this logic, and we show how to characterize by logical means various forms of entanglement (e.g. the Bell states) and various linear operators. As an example we sketch an analysis of the teleportation protocol.
Coauthor Papers Together
Sonja Smets 13
Dazhu Li 4
David Fernández‐Duque 3
Mina Young Pedersen 3
Johan van Benthem 3
Nick Bezhanishvili 3
Andrés Occhipinti Liberman 2
Bryan Renne 2
Soroush Rafiee Rad 2
Sławomir Solecki 2
Bob Coecke 2
Lawrence S. Moss 2
Mehrnoosh Sadrzadeh 2
Anya Yermakova 1
Andrés Occhipinti 1
Nina Gierasimczuk 1