# Comparing the Update Expressivity of Communication Patterns and Action
Models

Armando Castañeda Instituto de Matemáticas
Universidad Nacional Autónoma de México<EMAIL_ADDRESS>University of Toulouse, CNRS, IRITInstituto de Inv. en Matemáticas Aplicadas y
en Sistemas
Universidad Nacional Autónoma de MéxicoPosgr. en Ciencia e Ingeniería de la
Computación
Universidad Nacional Autónoma de México Hans van Ditmarsch University of
Toulouse, CNRS, IRIT<EMAIL_ADDRESS>Instituto de Inv. en
Matemáticas Aplicadas y en Sistemas
Universidad Nacional Autónoma de MéxicoPosgr. en Ciencia e Ingeniería de la
Computación
Universidad Nacional Autónoma de México David A. Rosenblueth Instituto de Inv.
en Matemáticas Aplicadas y en Sistemas
Universidad Nacional Autónoma de México<EMAIL_ADDRESS>Posgr. en Ciencia e
Ingeniería de la Computación
Universidad Nacional Autónoma de México Diego A. Velázquez Posgr. en Ciencia e
Ingeniería de la Computación
Universidad Nacional Autónoma de México<EMAIL_ADDRESS>
###### Abstract

Any kind of dynamics in dynamic epistemic logic can be represented as an
action model. Right? Wrong! In this contribution we prove that the update
expressivity of communication patterns is incomparable to that of action
models. Action models, as update mechanisms, were proposed by Baltag, Moss,
and Solecki in 1998 and have remained the nearly universally accepted update
mechanism in dynamic epistemic logics since then. Alternatives, such as arrow
updates that were proposed by Kooi and Renne in 2011, have update equivalent
action models. More recently, the picture is shifting. Communication patterns
are update mechanisms originally proposed in some form or other by Ågotnes and
Wang in 2017 (as resolving distributed knowledge), by Baltag and Smets in 2020
(as reading events), and by Velázquez, Castañeda, and Rosenblueth in 2021 (as
communication patterns). All these logics have the same expressivity as the
base logic of distributed knowledge. However, their update expressivity, the
relation between pointed epistemic models induced by such an update, was
conjectured to be different from that of action model logic. Indeed, we show
that action model logic and communication pattern logic are incomparable in
update expressivity. We also show that, given a history-based semantics and
when restricted to (static) interpreted systems, action model logic is
(strictly) more update expressive than communication pattern logic. Our
results are relevant for distributed computing wherein oblivious models
involve arbitrary iteration of communication patterns.

##  1 Introduction

It is well known that the expressivity of public announcement logic is the
same as that of epistemic logic [16]. This is proved by way of a reduction
system showing that every public announcement formula is equivalent to one
without public announcement modalities. Similarly, the expressivity of the
logic of distributed knowledge with public announcements is the same as that
of the logic of distributed knowledge [2]. Again, this is shown by a
reduction. A reduction also exists for the logic of distributed knowledge with
action models [3]; see [19, Fig. 5 and Th. 15] and the reduction axiom called
AD in [19, Fig. 9].

Distributed knowledge can also be extended with dynamic modalities for
communication patterns, an update mechanism proposed in [18]. The resulting
communication pattern logic is as expressive as the logic of distributed
knowledge: we can reduce formulas with dynamic modalities to formulas without
[7]. This logic is a slight generalization of logics with similar modalities
also showing this by reduction [2, 4]. A detailed comparison to these other
proposals is found in [7].

We conclude that the logic of communication patterns and distributed knowledge
has the same expressivity as the logic of action models and distributed
knowledge, because they both reduce to the logic of distributed knowledge. A
different matter, however, is so-called _update expressivity_ [11, 13, 8].

We will compare the update expressivity of communication pattern logic and
action model logic. Communication patterns, like action models, are (induce)
updates transforming pointed epistemic models into other pointed epistemic
models. Is there for each communication pattern an action model defining the
same update, and vice versa? Communication patterns can always be executed,
but action models cannot always be executed, for example a truthful public
announcement of $p$ requires $p$ to be true in some world. We can therefore
expect a trivial difference in update expressivity. It becomes non-trivial if
we also consider union of relations, such as non-deterministic choice between
the announcement of $p$ and the announcement of $\neg p$.

This is an overview of the structure of our contribution. Sect. 2 recalls
communication pattern logic, action model logic, and update expressivity. In
Sect. 3 we show that for each communication pattern there is an update
equivalent action model when executed on epistemic models that are interpreted
systems. However, the resulting model may not be an interpreted system. In
Sect. 4 we then show that communication pattern logic and action model logic
are indeed incomparable in update expressivity on the class of epistemic
models. Finally, in Sect. 5 we propose a history-based semantics for
communication pattern logic for which the class of interpreted systems is,
after all, closed under updates, and we show that for each iterated
communication pattern there is then an update equivalent action model.

##  2 Communication pattern logic and action model logic

###  2.1 Language

Given are a finite set of _agents_ $A$ and a set of _propositional variables_
$P\subseteq P^{\prime}\times A$, where $P^{\prime}$ is a countable set. For
$B\subseteq A$ and $Q\subseteq P$, $Q\cap(P^{\prime}\times B)$ is denoted
$Q_{B}$ (where $Q_{a}$ is $Q_{\\{a\\}}$), and $(p,a)\in P$ is denoted $p_{a}$.
The set $P_{a}$ consists of the _local variables_ of agent $a$. In this work
we consider the following languages.

######  Definition 1 (Language)

Given $A$ and $P$, the language $\mathcal{L}^{\times\circ}$ is defined by BNF
(where $p_{a}\in P$, $B\subseteq A$):

$\begin{array}[]{ll}\varphi:=p_{a}\mid\neg\varphi\mid\varphi\wedge\varphi\mid
D_{B}\varphi\mid[\boldsymbol{R},R]\varphi\mid[\boldsymbol{U},e]\varphi\end{array}$

where $(\boldsymbol{R},R)$ and $(\boldsymbol{U},e)$ are structures defined
below, with $R\in\boldsymbol{R}$ and $e$ in the domain of $\boldsymbol{U}$.
Furthermore, $\mathcal{L}^{\circ}$ is the language without
$[\boldsymbol{U},e]\varphi$, $\mathcal{L}^{\times}$ without
$[\boldsymbol{R},R]\varphi$, and $\mathcal{L}^{-}$ without either.

_Epistemic_ formula $D_{B}\varphi$ is read as ‘the agents in $B$ have
distributed knowledge of $\varphi$’. We write $K_{a}\varphi$ for
$D_{\\{a\\}}\varphi$, for ‘agent $a$ knows $\varphi$’. _Dynamic_ formula
$[\boldsymbol{R},R]\varphi$ means ‘after execution of communication graph $R$
from communication pattern $\boldsymbol{R}$, $\varphi$ is true’, and
$[\boldsymbol{U},e]\varphi$ means ‘after execution of action $e$ from action
model $\boldsymbol{U}$, $\varphi$ is true’. Dynamic modalities will be
interpreted as updates of epistemic models.

By notational abbreviation we define $[\boldsymbol{U}]\varphi:=\bigwedge_{e\in
E}[\boldsymbol{U},e]\varphi$ and
$[\boldsymbol{R}]\varphi:=\bigwedge_{R\in\boldsymbol{R}}[\boldsymbol{R},R]\varphi$.
The _modal depth_ of a formula $\varphi\in\mathcal{L}^{\circ\times}$ is
inductively defined as: $md(p_{a})=0$, $md(\neg\varphi)=md(\varphi)$,
$md(\varphi\wedge\psi)=\max\\{md(\varphi),md(\psi)\\}$,
$md(D_{B}\varphi):=md(\varphi)+1$,
$md([\boldsymbol{R},R]\varphi):=md(\varphi)$,
$md([\boldsymbol{U},e]\varphi)=md(\boldsymbol{U})+md(\varphi)$, where
$md(\boldsymbol{U})=\max\\{md({\rm Phys.~{}Rev.~{}E}(f))\mid f\in E\\}$. In
$md(\boldsymbol{U})$, the formulas ${\rm Phys.~{}Rev.~{}E}(f)$ are defined
below.

If $P$ is finite and $Q\subseteq P$, _description_ $\delta_{Q}$ (of valuation
$Q$) is defined as $\bigwedge_{p_{a}\in Q}p_{a}\wedge\bigwedge_{p_{a}\in
P{\setminus}Q}\neg p_{a}$. If $P$ is infinite and $Q\subseteq
Q^{\prime}\subset P$ are finite subsets of $P$, description
$\delta_{Q,Q^{\prime}}$ is defined as $\bigwedge_{p_{a}\in
Q}p_{a}\wedge\bigwedge_{p_{a}\in Q^{\prime}{\setminus}Q}\neg p_{a}$.

###  2.2 Structures

######  Definition 2 (Epistemic model)

An epistemic model $M$ is a triple $(W,\sim,L)$, where for all $a\in A$,
$\sim_{a}$ is an equivalence relation on the _domain_ $W$ (also denoted
$\mathcal{D}(M)$) consisting of _states_ (or _worlds_), and where
$L:W\rightarrow\mathcal{P}(P)$ is the _valuation_ (function). For
$\bigcap_{a\in B}\sim_{a}$ we write $\sim_{B}$, and for $\\{w^{\prime}\in
W\mid w^{\prime}\sim_{a}w\\}$ we write $[w]_{a}$. We further require epistemic
models to be _local_ : for all $a\in A$ and $v,w\in W$, $v\sim_{a}w$ implies
$L(v)_{a}=L(w)_{a}$; if for all $a,v,w$ also $L(v)_{a}=L(w)_{a}$ implies
$v\sim_{a}w$, it is a _(static) interpreted system_.

An epistemic model encodes uncertainty among the agents about the value of
other agents’ local variables and about the knowledge of other agents.

######  Definition 3 (Communication pattern)

A communication graph $R$ is a reflexive binary relation on the set of agents
$A$, that is, $R\in\mathcal{P}(A\times A)$ and such that for all $a\in A$,
$(a,a)\in R$. A communication pattern $\boldsymbol{R}$ is a set of
communication graphs, that is, $\boldsymbol{R}\subseteq\mathcal{P}(A\times
A)$.

Expression $(a,b)\in R$ means that the message sent by $a$ is received by $b$.
For $(a,b)\in R$ we write $aRb$. We let $Rb:=\\{a\in A\mid aRb\\}$,
$RB:=\bigcup_{b\in B}Rb$, and $R^{\prime}B\equiv RB$ if $R^{\prime}a=Ra$ for
all $a\in B$. The _identity relation_ $I$ is $\\{(a,a)\mid a\in A\\}$. The
_universal relation_ $U$ is $A\times A$. A communication graph is a reflexive
relation, because we assume that an agent always receives her own message. But
not every other agent may receive the message. We could alternatively have
defined a communication pattern as a structure with equivalence relations
$\sim_{a}$ for each agent, namely by defining that $R\sim_{a}R^{\prime}$ iff
$Ra=R^{\prime}a$, as in [18].

######  Definition 4 (Action model)

An action model $\boldsymbol{U}=(E,\sim,{\rm Phys.~{}Rev.~{}E})$ consists of a
domain $E$ of actions, an accessibility function $\sim\
:A\rightarrow{\mathcal{P}}(E\times E)$, where each $\sim_{a}$ is an
equivalence relation, and a precondition function ${\rm
Phys.~{}Rev.~{}E}:E\rightarrow\mathcal{L}^{-}$.

An action model [3] is a structure like an epistemic model but with a
precondition function, associating a formula with each state. The restriction
to language $\mathcal{L}^{-}$ for preconditions excuses us from explanations
involving mutual recursion.

For all the above structures $X$ we also consider _pointed_ and _multi-
pointed_ versions that are pairs $(X,x)$ with $x\in X$ (or
$x\in\mathcal{D}(X)$) resp. $(X,Y)$ with $Y\subseteq X$
($Y\subseteq\mathcal{D}(X)$), so we have pointed epistemic models $(M,w)$,
multi-pointed action models $(\boldsymbol{U},T)$, etcetera.

Communication patterns are fairly novel in dynamic epistemic logic. We note
that similar structures or modalities were proposed in [2] (resolving
distributed knowledge), in [4] (reading events), and in [18] (communication
patterns). The communication patterns in [18] have preconditions, just as
action models. The reading events in [4] and resolution in [2] are
communication patterns without uncertainty over the reception of messages.
Then again, communication patterns permit less uncertainty than the arbitrary
reading events in [4]. These differences are discussed in [7]. Examples are
given in Sect. 3.

One can update an epistemic model with a communication pattern and one can
also update an epistemic model with an action model. The updated epistemic
model encodes how the knowledge has changed after agents have informed each
other according to the update.

Given an epistemic model $M=(W,\sim,L)$ and a communication pattern
$\boldsymbol{R}$, the _updated_ epistemic model
$M\odot\boldsymbol{R}=(\dot{W},\dot{\sim},\dot{L})$ (the _update_ of $M$ with
$\boldsymbol{R}$) is defined as:

$\begin{array}[]{lcl}\dot{W}&=&W\times\boldsymbol{R}\\\
(w,R)\dot{\sim}_{a}(w^{\prime},R^{\prime})&\text{iff}&w\sim_{Ra}w^{\prime}\text{
and }Ra=R^{\prime}a\\\ \dot{L}(w,R)&=&L(w)\end{array}$

The relation $\dot{\sim}_{a}$ is the intersection $\sim_{Ra}$ of the relations
of all agents from which $a$ received messages.

Given an epistemic model $M=(W,\sim,L)$ and an action model
$\boldsymbol{U}=(E,\sim,{\rm Phys.~{}Rev.~{}E})$, the updated epistemic model
$M\otimes\boldsymbol{U}=(W^{\times},\sim^{\times},L^{\times})$ is defined as:

$\begin{array}[]{lcl}W^{\times}&\ \ =&\\{(v,f)\mid v\in W,f\in E,\text{ and
}M,v\models{\rm Phys.~{}Rev.~{}E}(f)\\}\\\
(v,f)\sim^{\times}_{a}(v^{\prime},f^{\prime})&\text{iff}&v\sim_{a}v^{\prime}\text{
and }f\sim_{a}f^{\prime}\\\ L^{\times}(v,f)&=&L(v)\end{array}$

The satisfaction relation $\models$ to determine $M,v\models{\rm
Phys.~{}Rev.~{}E}(f)$ is defined below, by mutual recursion.

In order to compare the information content of epistemic models we need the
notions of _(collective) bisimulation_ and _bounded (collective) bisimulation_
(_$n$ -bisimulation_) [6, 17].

######  Definition 5 (Collective bisimulation)

A relation $Z$ between the domains of epistemic models $M=(W,\sim,L)$ and
$M^{\prime}=(W^{\prime},\sim^{\prime},L^{\prime})$ is a (collective)
bisimulation, notation
$Z:M{\raisebox{1.29167pt}[0.0pt][0.0pt]{$\medspace\underline{\\!\leftrightarrow\\!}\medspace$}}M^{\prime}$,
if for all $(w,w^{\prime})\in Z$:

  * •

atoms: for all $p_{a}\in P$, $p_{a}\in L(w)$ iff $p_{a}\in
L^{\prime}(w^{\prime})$;

  * •

forth: for all nonempty $B\subseteq A$ and for all $v\in W$, if $w\sim_{B}v$
then there is $v^{\prime}\in W^{\prime}$ such that $(v,v^{\prime})\in Z$ and
$w^{\prime}\sim_{B}v^{\prime}$;

  * •

back: for all nonempty $B\subseteq A$ and for all $v^{\prime}\in W^{\prime}$,
if $w^{\prime}\sim_{B}v^{\prime}$ then there is $v\in W$ such that
$(v,v^{\prime})\in Z$ and $w\sim_{B}v$.

We additionally define a _collective bisimulation bounded by $n$_, as a set of
relations $Z^{0}\supseteq Z^{1}\dots\supseteq Z^{n}$ of $i$-bisimulations for
$0\leq i\leq n$. Relation $Z^{0}$ merely satisfies atoms, and for all
$(w,w^{\prime})\in Z^{n+1}$:

  * •

atoms: for all $p_{a}\in P$, $p_{a}\in L(w)$ iff $p_{a}\in
L^{\prime}(w^{\prime})$;

  * •

forth-$(n+1)$: for all nonempty $B\subseteq A$ and for all $v\in W$, if
$w\sim_{B}v$ then there is $v^{\prime}\in W^{\prime}$ such that
$(v,v^{\prime})\in Z^{n}$ and $w^{\prime}\sim_{B}v^{\prime}$.

  * •

back-$(n+1)$: for all nonempty $B\subseteq A$ and for all $v^{\prime}\in
W^{\prime}$, if $w^{\prime}\sim_{B}v^{\prime}$ then there is $v\in W$ such
that $(v,v^{\prime})\in Z^{n}$ and $w\sim_{B}v$.

If there is a bisimulation $Z$ between $M$ and $M^{\prime}$ we write
$M{\raisebox{1.29167pt}[0.0pt][0.0pt]{$\medspace\underline{\\!\leftrightarrow\\!}\medspace$}}M^{\prime}$,
and if there is one containing $(w,w^{\prime})$ we write
$(M,w){\raisebox{1.29167pt}[0.0pt][0.0pt]{$\medspace\underline{\\!\leftrightarrow\\!}\medspace$}}(M^{\prime},w^{\prime})$.
We then say that $M$ and $M^{\prime}$, respectively $(M,w)$ and
$(M^{\prime},w^{\prime})$, are _bisimilar_. If $Z$ is bounded by $n$ we write
$(M,w){\raisebox{1.29167pt}[0.0pt][0.0pt]{$\medspace\underline{\\!\leftrightarrow\\!}\medspace$}}^{n}(M^{\prime},w^{\prime})$
and we say that $(M,w)$ and $(M^{\prime},w^{\prime})$ are _$n$ -bisimilar_.

Bounded bisimulations are used to compare models $(M,w)$ and
$(M^{\prime},w^{\prime})$ up to a depth $n$ from the respective points $w$ and
$w^{\prime}$. Collective $n$-bisimilarity implies that both models satisfy the
same $\mathcal{L}^{-}$ formulas of modal depth at most $n$, as a minor
variation of the standard result in [6].

To compare dynamic modalities we define _updates_ and update expressivity.

######  Definition 6 (Update, update expressivity)

An _update_ (or _update relation_) is a binary relation $X$ on a class of
pointed epistemic models. Given updates $X$ and $Y$, $X$ is update equivalent
to $Y$, if for all pointed epistemic models $(M,w)$ the update of $(M,w)$ with
$X$ is collectively bisimilar to the update of $(M,w)$ with $Y$. Update
modalities $[X]$ and $[Y]$ are update equivalent, if $X$ and $Y$ are update
equivalent. (For more refined notions see [8].)

A language $\mathcal{L}$ is at least as update expressive as
$\mathcal{L}^{\prime}$ if for every update modality $[X]$ of
$\mathcal{L}^{\prime}$ there is an update modality $[Y]$ of $\mathcal{L}$ such
that $X$ is update equivalent to $Y$. Language $\mathcal{L}$ is equally update
expressive as $\mathcal{L}^{\prime}$ (or ‘as update expressive as’), if
$\mathcal{L}$ is at least as update expressive as $\mathcal{L}^{\prime}$ and
$\mathcal{L}^{\prime}$ is at least as update expressive as $\mathcal{L}$.
Language $\mathcal{L}$ is (strictly) more update expressive than
$\mathcal{L}^{\prime}$, if $\mathcal{L}$ is at least as update expressive as
$\mathcal{L}^{\prime}$ and $\mathcal{L}^{\prime}$ is not at least as update
expressive as $\mathcal{L}$. Languages $\mathcal{L}$ and
$\mathcal{L}^{\prime}$ are incomparable in update expressivity if if
$\mathcal{L}$ is not at least as update expressive as $\mathcal{L}^{\prime}$
and $\mathcal{L}^{\prime}$ is not at least as update expressive as
$\mathcal{L}$.

###  2.3 Semantics

######  Definition 7 (Semantics on epistemic models)

Given $M=(W,\sim,L)$ and $w\in W$, the _satisfaction relation_ $\models$ is
defined by induction on $\varphi\in\mathcal{L}^{\times\circ}$ (where $p\in P$,
$a\in A$, $B\subseteq A$, $(\boldsymbol{R},R)$ a pointed communication pattern
and $(\boldsymbol{U},e)$ a pointed action model).

$\begin{array}[]{lcl}M,w\models p_{a}&\text{iff}&p_{a}\in L(w)\\\
M,w\models\neg\varphi&\text{iff}&M,w\not\models\varphi\\\
M,w\models\varphi\wedge\psi&\text{iff}&M,w\models\varphi\text{ and
}M,w\models\psi\\\ M,w\models D_{B}\varphi&\text{iff}&M,v\models\varphi\text{
for all }v\sim_{B}w\\\
M,w\models[\boldsymbol{R},R]\varphi&\text{iff}&M\odot\boldsymbol{R},(w,R)\models\varphi\\\
M,w\models[\boldsymbol{U},e]\varphi&\text{iff}&M,w\models{\rm
Phys.~{}Rev.~{}E}(e)\text{ implies
}M\otimes\boldsymbol{U},(w,e)\models\varphi\end{array}$

Formula $\varphi$ is valid on $M$ iff for all $w\in W$, $M,w\models\varphi$;
formula $\varphi$ is valid iff for all $(M,w)$, $M,w\models\varphi$.

The (required) locality of epistemic models causes distributed knowledge to
have slightly different properties in our semantics. In the standard semantics
of distributed knowledge $D_{B}\varphi\leftrightarrow\varphi$ is invalid for
any $B\subseteq A$. Whereas in our semantics
$D_{A}\varphi\leftrightarrow\varphi$ is valid although
$D_{B}\varphi\leftrightarrow\varphi$ for $B\subset A$ remains invalid.

A complete axiomatization of the validities of $\mathcal{L}^{\circ}$
(communication pattern logic), reducing the dynamics, is given in [7] (similar
to [2, 4]). A complete axiomatization of the validities of
$\mathcal{L}^{\times}$ (action model logic), reducing the dynamics, is given
in [3]. The language $\mathcal{L}^{\times\circ}$ is not of independent
interest.

##  3 Induced action models for interpreted systems

In this section, let $P$ be finite. From each communication pattern we will
construct an _induced action model_. We will show that communication patterns
are update equivalent to induced action models when executed in an interpreted
system. However, the update of an interpreted system with a communication
pattern may not be an interpreted system, and the update of an epistemic model
that is not an interpreted system with a communication pattern may not have
the same update effect as its induced action model, of which we will give an
example.

######  Definition 8 (Action model induced by a communication pattern)

Given a communication pattern $\boldsymbol{R}$, define _induced action model_
$\boldsymbol{U}(\boldsymbol{R})=(E,\sim,{\rm Phys.~{}Rev.~{}E})$ as follows
(where $R,R^{\prime}\in\boldsymbol{R}$, $Q,Q^{\prime}\subseteq P$, $a\in A$).

$\begin{array}[]{lcl}E&=&\boldsymbol{R}\times\mathcal{P}(P)\\\
(R,Q)\sim_{a}(R^{\prime},Q^{\prime})&\text{iff}&Ra=R^{\prime}a\text{ and
}Q_{Ra}=Q^{\prime}_{R^{\prime}a}\\\ {\rm
Phys.~{}Rev.~{}E}(R,Q)&=&\delta_{Q}\end{array}$

Informally, this says that two actions are indistinguishable for an agent if
the agent receives messages from the same agents ($Ra=R^{\prime}a$) and if the
messages it receives from those agents are the same
($Q_{Ra}=Q^{\prime}_{R^{\prime}a}$). As $\boldsymbol{R}$ and $P$ are finite,
$\boldsymbol{U}(\boldsymbol{R})$ has a finite domain, so that modality
$[\boldsymbol{U}(\boldsymbol{R})]$ is in $\mathcal{L}^{\times}$. The size of
the action model $\boldsymbol{U}(\boldsymbol{R})$ is
$|\boldsymbol{R}\times\mathcal{P}(P)|=|\boldsymbol{R}|\cdot 2^{|P|}$.
Therefore, $\boldsymbol{U}(\boldsymbol{R})$ is exponentially larger than
$\boldsymbol{R}$.

###### Proposition 9

Let an interpreted system $M$ and $\boldsymbol{R}$ be given. Then
$M\odot\boldsymbol{R}$ is bisimilar to
$M\otimes\boldsymbol{U}(\boldsymbol{R})$.

######  Proof 3.10.

Let $M=(W,\sim,L)$. Define the following relation $Z$ between (the domains of)
$M\odot\boldsymbol{R}$ and $M\otimes\boldsymbol{U}(\boldsymbol{R})$:
$Z:(w,R)\mapsto(w,(R,L(w)))$. We show that $Z$ defines a bisimulation.

Let $((w,R),(w,R,L(w))\in Z$.

atoms: Straightforwardly, $\dot{L}(w,R)=L(w)=L^{\times}(w,(R,L(w)))$.

forth: Assume $(w,R)\dot{\sim}_{B}(v,S)$. We claim that $(v,(S,L(v)))$ is the
required witness to show forth. Obviously $((v,S),(v,(S,L(v)))\in Z$. We also
have:

$(w,R)\dot{\sim}_{B}(v,S)$ $\Leftrightarrow$
for all $a\in B$, $(w,R)\dot{\sim}_{a}(v,S)$ $\Leftrightarrow$ by definition
of $\dot{\sim}_{a}$
for all $a\in B$, $w\sim_{Ra}v$ and $Ra=Sa$ $\Leftrightarrow$ (*)
for all $a\in B$, $w\sim_{a}v$, $Ra=Sa$, and $L(w)_{Ra}=L(v)_{Sa}$
$\Leftrightarrow$
for all $a\in B$, $w\sim_{a}v$ and $(R,L(w))\sim_{a}(S,L(v))$
$\Leftrightarrow$
for all $a\in B$, $(w,(R,L(w)))\sim^{\times}_{a}(v,(S,L(v)))$
$\Leftrightarrow$
$(w,(R,L(w)))\sim^{\times}_{B}(v,(S,L(v)))$.

(*): As $M$ is an interpreted system, for all agents $b\in Ra$, $w\sim_{b}v$
iff $L(w)_{b}=L(v)_{b}$, in other words: $w\sim_{Ra}v$ iff
$L(w)_{Ra}=L(v)_{Sa}$. As in particular $a\in Ra$, $w\sim_{a}v$ on the right-
hand side of the equation also follows from $L(w)_{Ra}=L(v)_{Sa}$.

back: Similar to forth.

$M:$$w_{1}$$w_{2}$$p_{a}$$\overline{p}_{a}$$b$$M\odot\boldsymbol{\textit{Byz}}:$$(w_{1},I)$$(w_{1},R^{ab})$$(w_{2},I)$$(w_{2},R^{ab})$$p_{a}$$p_{a}$$\overline{p}_{a}$$\overline{p}_{a}$$a$$b$$a$

$\boldsymbol{U}(\boldsymbol{\textit{Byz}}):$$(I,p_{a})$$(R^{ab},p_{a})$$(I,\overline{p}_{a})$$(R^{ab},\overline{p}_{a})$$a$$b$$a$$M\otimes\boldsymbol{U}(\boldsymbol{\textit{Byz}}):$$(w_{1},(I,p_{a}))$$(w_{1},(R^{ab},p_{a}))$$(w_{2},(I,\overline{p}_{a}))$$(w_{2},(R^{ab},\overline{p}_{a}))$$p_{a}$$p_{a}$$\overline{p}_{a}$$\overline{p}_{a}$$a$$b$$a$

Figure 1: Communication pattern and action model for Byzantine Generals

######  Example 3.11 (Byzantine generals).

Byzantine attack [14, 10] is a communication pattern given in [18]. Let
$A=\\{a,b\\}$ and $P=\\{p_{a}\\}$. Generals $a$ and $b$ wish to schedule an
attack, where $b$ desires to learn whether $a$ wants to ‘attack at dawn’
($p_{a}$) or ‘attack at noon’ ($\neg p_{a}$). General $a$ now sends her
decision to general $b$ in a message that may fail to arrive. This fits the
communication pattern $\boldsymbol{R}=\\{I,R^{ab}\\}$ where
$R^{ab}=I\cup\\{(a,b)\\}$, which models that $a$ is uncertain whether her
message has been received by $b$. In this instantiation of Byzantine generals,
general $b$ has no local variable.

The communication pattern $\boldsymbol{\textit{Byz}}=\\{I,R^{ab}\\}$ where
$R^{ab}=I\cup\\{(a,b)\\}$. We have that $Ia=R^{ab}a=\\{a\\}$ whereas
$Ib=\\{b\\}$ and $R^{ab}b=\\{a,b\\}$ (see also [18, Figure 1] and [7, Example
7]).

Fig. 1 depicts the initial epistemic model $M$ wherein agent $b$ is uncertain
about the value of a variable $p_{a}$ of agent $a$, the updated model
$M\odot\boldsymbol{\textit{Byz}}$, the action model
$\boldsymbol{U}(\boldsymbol{\textit{Byz}})$, and updated model
$M\otimes\boldsymbol{U}(\boldsymbol{\textit{Byz}})$. The states in epistemic
models are also labelled with valuations, where $p_{a}$ stands for
$\\{p_{a}\\}$ and $\overline{p}_{a}$ stands for $\emptyset$. Model $M$ is an
interpreted system in the vacuous sense that if agent $b$ were to have local
variables we could assume their value to be the same in both states. In
$\boldsymbol{U}(\boldsymbol{\textit{Byz}})$, the precondition of actions
$(I,\\{p_{a}\\})$ and $(R^{ab},\\{p_{a}\\})$ is $p_{a}$, and that of actions
$(I,\emptyset)$ and $(R^{ab},\emptyset)$ is $\neg p_{a}$. (In the figure, for
visual consistency, these actions are written as $(I,p_{a})$,
$(R^{ab},p_{a})$, $(I,\overline{p}_{a})$, and $(R^{ab},\overline{p}_{a})$.)
Model $M\otimes\boldsymbol{U}(\boldsymbol{\textit{Byz}})$ is bisimilar, as
required, to $M\odot\boldsymbol{\textit{Byz}}$ and even isomorphic.

When model $M$ is an interpreted system, $M\odot\boldsymbol{R}$ may not be an
interpreted system, as, in a way, $M\odot\boldsymbol{\textit{Byz}}$ in Example
3.11. If agent $b$ were to have local variables, their value would be the same
in $w_{1}$ and in $w_{2}$ and thus also in the four worlds of the updated
model. But now agent $b$ has three equivalence classes. It is therefore no
longer an interpreted system.

$\boldsymbol{\textit{Sq}}:$$00$$01$$10$$11$$a$$a$$b$$b$

$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}:$$00$$00$$00$$01$$01$$01$$10$$10$$10$$11$$11$$11$$a$$b$$a$$a$$b$$a$$b$$b$$a$$b$$a$$b$

$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}:$$00$$11$$01$$10$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$a$$a$$b$$b$

Figure 2: Iterated immediate snapshot for two agents $a,b$. In world 10 local
variable $p_{a}$ is true and $p_{b}$ is false (a slightly simpler depiction
than $p_{a}\overline{p}_{b}$), etcetera. In
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}$ and
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$
it is implicit which communication graph is executed, and in
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$
valuations are only indicated schematically.

######  Example 3.12 (Iterated Immediate Snapshot).

Consider the model Sq where $a$ knows the truth about $p_{a}$ and $b$ knows
the truth about $p_{b}$. This is the interpreted system for two agents each
having a single variable. We recall the immediate snapshot (IS) [12] for two
agents $\\{a,b\\}$, defined as $\\{R^{ab},R^{ba},U\\}$, where
$R^{ab}=I\cup\\{(a,b)\\}$ and $R^{ba}=I\cup\\{(b,a)\\}$. These three
communication graphs, as points of IS, are commonly denoted as _schedules_
consisting of _concurrency classes_ $a.b$, $b.a$, and $ab$, respectively. Fig.
2 shows the models Sq,
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}$, and
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$.
Lemma 3.13 below shows that iteration of IS preserves circularity, as in the
figure.

It follows from Prop. 9 that
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}$ is bisimilar to
$\boldsymbol{\textit{Sq}}\otimes\boldsymbol{U}(\boldsymbol{\textit{IS}})$.
However,
$(\boldsymbol{\textit{Sq}}\otimes\boldsymbol{U}(\boldsymbol{\textit{IS}}))\otimes\boldsymbol{U}(\boldsymbol{\textit{IS}})$
is not bisimilar to
$(\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}})\odot\boldsymbol{\textit{IS}}$
and these models therefore satisfy different formulas in comparable worlds. In
view of Prop. 9 it is sufficient to show that
$(\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}})\otimes\boldsymbol{U}(\boldsymbol{\textit{IS}})$
is not bisimilar to
$(\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}})\odot\boldsymbol{\textit{IS}}$.

Consider the fragment

$(11,R^{ba})$$(11,U)$$(11,R^{ab})$$a$$b$

of model $\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}$. This is the
top row in Fig. 2. In the model
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$
this becomes

$(11,R^{ba},R^{ba})$$(11,R^{ba},U)$$(11,R^{ba},R^{ab})$$(11,U,R^{ab})$$(11,U,U)$$(11,U,R^{ba})$$(11,R^{ab},R^{ba})$$(11,R^{ab},U)$$(11,R^{ab},R^{ab})$$a$$b$$a$$b$$a$$b$$a$$b$

Let us now, instead, calculate
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\otimes\boldsymbol{U}(\boldsymbol{\textit{IS}})$.
Instead of $(11,R^{ba},R^{ba})\text{---}a\text{---}(11,R^{ba},U)$, we obtain
$(11,R^{ba},(R^{ba},11))\text{---}a\text{---}(11,R^{ba},(U,11))$. Apart from
this edge and other expected edges as above, we now obtain additional edges as
below (where we also assume transitivity).

$(11,R^{ba},R^{ba})$$(11,R^{ba},U)$$(11,R^{ba},R^{ab})$$(11,U,R^{ab})$$(11,U,U)$$(11,U,R^{ba})$$(11,R^{ab},R^{ba})$$(11,R^{ab},U)$$(11,R^{ab},R^{ab})$$a$$b$$a$$b$$a$$b$$a$$b$$a$$a$$b$$b$

For example, $(11,R^{ba},(U,11))\sim_{a}(11,U,(U,11))$, because by the
semantics of action model execution, $(11,R^{ba})\sim_{a}(11,U)$ in
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}$ and
$(U,11)\sim_{a}(U,11)$ in $\boldsymbol{U}(\boldsymbol{\textit{IS}})$.
Similarly, $(11,R^{ba},(R^{ba},11))\sim_{a}(11,U,(U,11))$, because
$(11,R^{ba})\sim_{a}(11,U)$ in
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}$ and
$(R^{ba},11)\sim_{a}(U,11)$ in $\boldsymbol{U}(\boldsymbol{\textit{IS}})$,
where the latter holds because $R^{ba}a=Ua$ (namely $\\{a,b\\}$) and
$11_{R^{ba}a}=11_{Ua}$ (namely $11_{\\{ab\\}}$, which is $11$).

Intuitively, in
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$
the agents learn in the second round whether the communication succeeded in
the previous, first, round. But in
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\otimes\boldsymbol{U}(\boldsymbol{\textit{IS}})$
they do not learn this in the second round.

It is easy to see that
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$
is not bisimilar to
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\otimes\boldsymbol{U}(\boldsymbol{\textit{IS}})$
wherein we can reach states in the model with a different valuation in fewer
steps. There are then distinguishing formulas, e.g.,
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}},(11,U,R^{ba})\not\models\widehat{K}_{a}\widehat{K}_{b}\neg
p_{a}$, whereas
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\otimes\boldsymbol{U}(\boldsymbol{\textit{IS}}),(11,U,(R^{ba},11))\models\widehat{K}_{a}\widehat{K}_{b}\neg
p_{a}$.

#### On squares and circles

A _circular $ab$-chain_ is an epistemic model consisting of an even number of
worlds $0,\dots,2n-1$, where $n\in\mathbb{N}$ with $n\geq 2$, and such that
for all $i\leq n$, $2i\sim_{a}2i+1$ and $2i\sim_{b}2i-1$ (modulo $2n$).

######  Lemma 3.13.

Define
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{0}:=\boldsymbol{\textit{Sq}}$
and
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n+1}:=(\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n})\odot\boldsymbol{\textit{IS}}$.
For all $n\in\mathbb{N}$,
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}$ is a circular
$ab$-chain.

######  Proof 3.14.

We prove this by induction.

Model Sq is a (minimal) circular $ab$-chain.

Assuming that $\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}$ is a
circular $ab$-chain, take any world $w$ in that chain and let neighbouring
worlds $w^{\prime},w^{\prime\prime}$ be such that $w^{\prime}\sim_{a}w$ and
$w\sim_{b}w^{\prime\prime}$ (where $w,w^{\prime},w^{\prime\prime}$ have
arbitrary valuation). We now execute IS once more. Consider the new worlds
$(w,R^{ab}),(w,U),(w,R^{ba})$. Then:

  * •

$(w^{\prime},R^{ab})\sim_{a}(w,R^{ab})$ because $R^{ab}a=R^{ab}a\ (=\\{a\\})$
and $w^{\prime}\sim_{a}w$. No other world than $(w^{\prime},R^{ab})$ is
indistinguishable for $a$ from $(w,R^{ab})$. If $R\neq R^{ab}$ then $Ra\neq
R^{ab}a$ so $(w^{\prime},R)\not\sim_{a}(w,R^{ab})$. If $v\neq w,w^{\prime}$
then $v\not\sim_{a}w$ so $(v,R^{ab})\not\sim_{a}(w,R^{ab})$.

  * •

$(w,R^{ba})\sim_{b}(w^{\prime\prime},R^{ba})$ because $R^{ba}b=R^{ba}b\
(=\\{b\\})$ and $w\sim_{b}w^{\prime\prime}$. Similarly to the previous case
this is the unique indistinguishable other world in the updated model.

  * •

$(w,R^{ab})\sim_{b}(w,U)$ because $R^{ab}b=Ub\ (=\\{a,b\\})$ and
$w\sim_{ab}w$. No other world than $(w,U)$ is indistinguishable for $b$ from
$(w,R^{ab})$. We note that $R^{ba}b\neq R^{ab}b$ and $R^{ba}b\neq Ub$, so
$(w,R^{ab})\not\sim_{b}(w,R^{ba})$ and $(w,U)\not\sim_{b}(w,R^{ba})$. If
$v\neq w$ then $v\not\sim_{ab}w$ so $(w,R^{ab})\not\sim_{b}(v,R^{ab})$ and
$(w,U)\not\sim_{b}(v,U)$.

  * •

$(w,R^{ba})\sim_{a}(w,U)$ because $R^{ba}a=Ua\ (=\\{a,b\\})$ and
$w\sim_{ab}w$. Similarly to the previous case this is the unique
indistinguishable other world in the updated model.

This result is not surprising. In the corresponding representation as
simplicial complexes, an application of IS is a so-called _subdivision_ [12].
A circular $ab$-chain corresponds to a circular graph (1-dimensional complex)
with alternating $a$ and $b$ nodes, such that each edge $a\text{---}b$ gets
replaced by three edges $a\text{---}b\text{---}a\text{---}b$ at each iteration
of IS (and duplicated nodes keeps their old labels).

##  4 Communication patterns and action models are incomparable

######  Proposition 4.15.

Communication pattern logic is not at least as update expressive as action
model logic.

######  Proof 4.16.

We can prove this in different ways, which seems instructive.

First, in a public announcement, the environment may reveal something that
cannot be revealed by the agents individually or jointly, such as the
announcement whether $p_{a}\vee p_{b}$ in a model where $a$ knows whether
$p_{a}$ and $b$ knows whether $p_{b}$.

$\overline{p}_{a}\overline{p_{b}}$$p_{a}\overline{p_{b}}$$\overline{p}_{a}p_{b}$$p_{a}p_{b}$$a$$a$$b$$b$$\stackrel{{\scriptstyle
p_{a}\vee
p_{b}?}}{{\Rightarrow}}$$\overline{p}_{a}\overline{p_{b}}$$p_{a}\overline{p_{b}}$$\overline{p}_{a}p_{b}$$p_{a}p_{b}$$a$$b$

Second, agents may choose to reveal some but not all of their local variables,
such as, if $a$ knows whether $p_{a}$ and whether $q_{a}$, $a$ informing $b$
of the truth about $p_{a}$ but not about $q_{a}$.

$\overline{p}_{a}\overline{q_{a}}$$p_{a}\overline{q_{a}}$$\overline{p}_{a}q_{a}$$p_{a}q_{a}$$b$$b$$b$$b$$\stackrel{{\scriptstyle
p_{a}?}}{{\Rightarrow}}$$\overline{p}_{a}\overline{q_{a}}$$p_{a}\overline{q_{a}}$$\overline{p}_{a}q_{a}$$p_{a}q_{a}$$b$$b$

Third, there are action models that produce more uncertainty than any
communication pattern. Here we should note that although the composition of
two action models is again an action model (therefore, for all
$\boldsymbol{U},\boldsymbol{U}^{\prime}$ there is a
$\boldsymbol{U}^{\prime\prime}$, namely the composition of $\boldsymbol{U}$
and $\boldsymbol{U}^{\prime}$, such that
$[\boldsymbol{U}][\boldsymbol{U}^{\prime}]\varphi\leftrightarrow[\boldsymbol{U}^{\prime\prime}]\varphi$),
sequentially executing two communication patterns is typically not the same as
executing a single communication pattern (it is not the case that for all
$\boldsymbol{R},\boldsymbol{R}^{\prime}$ there is a
$\boldsymbol{R}^{\prime\prime}$ such that
$[\boldsymbol{R}][\boldsymbol{R}^{\prime}]\varphi\leftrightarrow[\boldsymbol{R}^{\prime\prime}]\varphi$).
For example, consider the models Sq and
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$
(Example 3.12). The domain of model Sq consists of four worlds and that of
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$
consists of $36$ worlds; it is nine times larger (and it is bisimulation
minimal). Now there are only four different communication patterns for two
agents (namely $I$, $R^{ba}$, $R^{ab}$, and $U$). So the maximum size of a
model resulting from updating Sq with a communication pattern is $16$.
Therefore there is no such communication pattern. In other words, there is no
$\boldsymbol{R}$ such that
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$
is bisimilar to $\boldsymbol{\textit{Sq}}\odot\boldsymbol{R}$ which implies
that there is no $\boldsymbol{R}$ that has the same update effect as updating
twice with IS.

However, there is an action model $\boldsymbol{U}$ such that
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$
is bisimilar to $\boldsymbol{\textit{Sq}}\otimes\boldsymbol{U}$: its domain is
the domain of
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$;
its relations for $a$ and $b$ are the relations for $a$ and $b$ on the model
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$,
and its preconditions are such that the precondition of a world
$(ij,R,R^{\prime})$ in the domain of
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$
is the description $\delta_{ij}$ of the valuation $ij$. It is straightforward
to see that
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}\odot\boldsymbol{\textit{IS}}$
is even isomorphic to $\boldsymbol{\textit{Sq}}\otimes\boldsymbol{U}$.

We conclude that there is no communication pattern that is update equivalent
to this action model $\boldsymbol{U}$. Therefore, communication pattern logic
is not at least as update expressive as action model logic.

We continue by showing that action model logic is not at least as update
expressive as communication pattern logic. If multi-pointed action models had
not been allowed, a trivial way to show that, would have been to observe that
single-pointed action models unlike communication patterns may not always be
executable. Although true, that is not of interest. We prove this in a more
meaningful way in the following Prop. 4.17. Its proof assumes towards a
contradiction that an action model $\boldsymbol{U}$ exists that is update
equivalent to the communication pattern IS, where we identify $\boldsymbol{U}$
with the multi-pointed action model
$(\boldsymbol{U},\mathcal{D}(\boldsymbol{U}))$. We then compare the updates IS
and $\boldsymbol{U}$ in epistemic model
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}$ for $n$ exceeding
a function of the modal depth of any precondition of $\boldsymbol{U}$, and
derive a contradiction. It may assist the reader to know that Ex. 3.12 above
replays this proof for
$\boldsymbol{U}=\boldsymbol{U}(\boldsymbol{\textit{IS}})$ of which the action
preconditions are booleans, such that $md(\boldsymbol{U})=0$ and we can choose
$n=1$.

######  Proposition 4.17.

Action model logic is not at least as update expressive as communication
pattern logic.

######  Proof 4.18.

Suppose towards a contradiction that communication pattern IS is update
equivalent to an action model $\boldsymbol{U}=(E,\sim,{\rm
Phys.~{}Rev.~{}E})$.

What do we know about $\boldsymbol{U}$? As IS is always executable, we may
assume that the disjunction $\psi$ of all preconditions of actions $e$ in the
domain $E$ of $\boldsymbol{U}$ is the triviality. Otherwise, given some model
with $M,w\models\neg\psi$, we could update with IS but not with
$\boldsymbol{U}$. Similarly, for any action $e$ in the domain $E$ of
$\boldsymbol{U}$, there must be $f\in E$ such that $e\sim_{a}f$ and ${\rm
Phys.~{}Rev.~{}E}(e)={\rm Phys.~{}Rev.~{}E}(f)$ (and for agent $b$ there must
be a $g\in E$ such that $g\sim_{b}f$ and ${\rm Phys.~{}Rev.~{}E}(g)={\rm
Phys.~{}Rev.~{}E}(f)$). Otherwise, consider a model $(M,w)$ that can only be
updated with $(\boldsymbol{U},e)$ (for which $M,w\models{\rm
Phys.~{}Rev.~{}E}(e)$). It can be updated with $(\boldsymbol{\textit{IS}},U)$
and also with $(\boldsymbol{\textit{IS}},R^{ba})$ resulting in states $(w,U)$
and $(w,R^{ba})$ satisfying different properties, as $(w,U)\sim_{a}(w,R^{ba})$
(because $Ua=R^{ba}=\\{a,b\\}$), so that one or the other but not both can be
bisimilar to $(w,e)$. Therefore, $\boldsymbol{U}$ must be a refinement of IS
seen as a structure $R^{ab}\text{---}b\text{---}U\text{---}a\text{---}R^{ba}$.
Its actions can therefore be assumed to have shape $(R,\varphi)$ where $R$ is
one of $R^{ab},U,R^{ba}$ and where $\varphi\in\mathcal{L}^{\times}$ is the
precondition of that action, that is, ${\rm
Phys.~{}Rev.~{}E}(R,\varphi)=\varphi$.111By _refinement_ we mean that $R^{ab}$
can be seen as an equivalence class
$\\{(R^{ab},\varphi)\mid(R^{ab},\varphi)\in\mathcal{D}(\boldsymbol{U})\\}$,
and similarly for $U$ and $R^{ba}$, where two such equivalence classes are
indistinguishable for $a$ if there are
$(R,\varphi),(R^{\prime},\varphi^{\prime})$ such that
$(R,\varphi)\sim_{a}(R^{\prime},\varphi^{\prime})$, and similarly for $b$.

The modality $[\boldsymbol{U}]$ is an operator in the language
$\mathcal{L}^{\times}$ and $|E|$ is finite, so that
$md(\boldsymbol{U})=\max\\{md({\rm Phys.~{}Rev.~{}E}(e))\mid e\in E\\}$ is
defined. Choose $n\in\mathbb{N}$ with $n>\log_{3}2(md(\boldsymbol{U})+1)$ and
consider $\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}$,
schematically depicted as:

$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}$:$00$$00$$01$$01$$10$$10$$11$$11$$\bullet$$(11,U^{n})$$a$$a$$b$$b$

and concretely its three-action fragment:

$(*):$$(11,U^{n-1}R^{ba})$$(11,U^{n})$$(11,U^{n-1}R^{ab})$$a$$b$

where world $(11,U^{n})$ of $(*)$ is the same as the depicted world
$(11,U^{n})$ of $\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}$.

We can now justify the bound $n>\log_{3}2(md(\boldsymbol{U})+1)$. We need in
the proof that the three worlds of $(*)$ satisfy the same actions of
$\boldsymbol{U}$, and we guarantee that because they are bounded collectively
bisimilar for an appropriate bound. Given $(11,U^{n})$, the bound should
exceed the modal depth of any possible precondition of any action in
$\boldsymbol{U}$. That explains $md(\boldsymbol{U})$. Plus one, as we need
this to hold for the surrounding worlds too. That explains
$md(\boldsymbol{U})+1$. Twice that, $2\cdot(md(\boldsymbol{U})+1)$, is the
required length of one side of the squarish model
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}$ with therefore
$8\cdot(md(\boldsymbol{U})+1)$ worlds. Starting with four worlds, every
iteration of IS multiplies the number of worlds by $3$. So we therefore want
to iterate IS by some $n$ such that $4\cdot
3^{n}>8\cdot(md(\boldsymbol{U})+1)$, that is,
$n>\log_{3}2(md(\boldsymbol{U})+1)$.

Consider
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}\otimes\boldsymbol{U}$.
Recalling what is known about $\boldsymbol{U}$, there must be an $e\in E$ such
that
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n},(11,U^{n})\models{\rm
Phys.~{}Rev.~{}E}(e)$. Also, there must be $f,g\in E$ with $e\sim_{a}f$ and
$f\sim_{b}g$ and ${\rm Phys.~{}Rev.~{}E}(e)={\rm Phys.~{}Rev.~{}E}(f)={\rm
Phys.~{}Rev.~{}E}(e)$. Let ${\rm Phys.~{}Rev.~{}E}(e)$ be $\theta$. These
actions $e,f,g$ therefore have shape $(R^{ab},\theta)$, $(U,\theta)$,
$(R^{ba},\theta)$ respectively.

As $n>\log_{3}2(md(\boldsymbol{U})+1)$, the three worlds in $(*)$ are bounded
collectively bisimilar:

$(\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n},(11,U^{n-1},R^{ba})){\raisebox{1.29167pt}[0.0pt][0.0pt]{$\medspace\underline{\\!\leftrightarrow\\!}\medspace$}}^{md(\boldsymbol{U})+1}(\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n},(11,U^{n})){\raisebox{1.29167pt}[0.0pt][0.0pt]{$\medspace\underline{\\!\leftrightarrow\\!}\medspace$}}^{md(\boldsymbol{U})+1}(\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n},(11,U^{n-1},R^{ab}))$

As $md(\theta)\leq md(\boldsymbol{U})$, all three worlds in $(*)$ satisfy
$\theta$, so actions $e,f,g$ can be executed in all these worlds.

The model
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}\otimes\boldsymbol{U}$
therefore contains the submodel

$(\cdot,(R^{ba},\theta))$$(\cdot,(U,\theta))$$(\cdot,(R^{ab},\theta))$$(\cdot,(R^{ab},\theta))$$(\cdot,(U,\theta))$$(\cdot,(R^{ba},\theta))$$(\cdot,(R^{ba},\theta))$$(\cdot,(U,\theta))$$(\cdot,(R^{ab},\theta))$$a$$b$$a$$b$$a$$b$$a$$b$$a$$a$$b$$b$

wherein only some additional pairs for $\sim_{a}$ and $\sim_{b}$ are shown,
and where from those shown we merely justify one as an example: for the
leftmost and the middle worlds, we have that
$(11,U^{n-1},R^{ba},(R^{ba},\theta))\sim_{a}(11,U^{n},(U,\theta))$, because by
the semantics of action model execution,
$(11,U^{n-1},R^{ba})\sim_{a}(11,U^{n})$ in
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}$ and
$(R^{ba},\theta)\sim_{a}(U,\theta)$ in
$\boldsymbol{U}(\boldsymbol{\textit{IS}})$. Furthermore (unlike in Example
3.12), worlds $(\dots,(R,\theta))$ shown, may be indistinguishable for $a$ or
$b$ from worlds $(\dots,(R,\xi))$ not shown, for actions $(R,\xi)$ with $\xi$
non-equivalent to $\theta$.

Consequently,
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}\otimes\boldsymbol{U}$
is not a circular $ab$-chain like
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n+1}$ that locally
looks like:

$(\cdot,R^{ba})$$(\cdot,U)$$(\cdot,R^{ab})$$(\cdot,R^{ab})$$(\cdot,U)$$(\cdot,R^{ba})$$(\cdot,R^{ba})$$(\cdot,U)$$(\cdot,R^{ab})$$a$$b$$a$$b$$a$$b$$a$$b$

Now the assumption of update equivalence implies that
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n+1}$ is collectively
bisimilar to
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}\otimes\boldsymbol{U}$.
The supposed bisimulation relation $Z$ linking
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n+1}$ and
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n}\otimes\boldsymbol{U}$
should therefore such that $Z:(w,\sigma,R)\mapsto(w,\sigma,(R,{\rm
Phys.~{}Rev.~{}E}(e))$ for all $w\in W$,
$\sigma\in\boldsymbol{\textit{IS}}^{n}$, and $e\in E$ with
$\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}}^{n},(w,\sigma)\models{\rm
Phys.~{}Rev.~{}E}(e)$, in particular the three worlds in $(*)$ and the $e,f,g$
above with preconditions $\theta$. On the other hand, clearly, a pair of
worlds in this relation cannot be bisimilar, as the additional $a$-links and
$b$-links allow shorter paths to a $01$-world. Differently said, as bounded
bisimilarity implies the same truth value for formulas of at most that modal
depth, the worlds in such a pair satisfy different formulas. (See Ex. 3.12 for
$n=1$.)

This contradicts our assumption that $\boldsymbol{U}$ is update equivalent to
IS and thus concludes the proof.

Prop. 4.17 holds for any countable set of local variables $P$. In the proof of
Prop. 4.17 we only need two: $P=\\{p_{a},p_{b}\\}$. When $P$ is countably
infinite there is a shorter proof of Prop. 4.17, given below.

######  Proof 4.19.

Let $P$ be countably infinite. Suppose towards a contradiction that there is
an action model $\boldsymbol{U}$ with $[\boldsymbol{U}]$ (or
$[\boldsymbol{U},e]$) in the logical language (so that the domain of
$\boldsymbol{U}$ is necessarily finite) that is update equivalent to Byz. As
$\boldsymbol{U}$ is finite and $P$ is countably infinite, there exists a
$q_{a}\in P$ not occurring in any of the preconditions of the actions in the
domain of $\boldsymbol{U}$. Now consider epistemic model $M^{\prime\prime}$ as
in Example 3.11 but with $q_{a}$ true in $w_{1}$ and false in $w_{2}$ and with
$p_{a}$ true in both worlds. When executing $\boldsymbol{U}$ in
$M^{\prime\prime}$, the update $M^{\prime\prime}\otimes\boldsymbol{U}$ will
never get the required asymmetry of
$M^{\prime\prime}\odot\boldsymbol{\textit{Byz}}$, because any action (point)
$e$ that is executable in $w_{1}$ is also executable in $w_{2}$, as for any
$p\in P\setminus\\{q_{a}\\}$, $p\in L(w_{1})$ iff $p\in L(w_{2})$. In
particular we therefore will have that
$(w_{1},I,\dots)\sim_{b}(w_{2},I,\dots)$ iff
$(w_{1},R^{ab},\dots)\sim_{b}(w_{2},R^{ab},\dots)$. (An argument involving
$\sim_{a}$ and $\sim_{b}$ similar to the one in the proof of Prop. 4.17 is
omitted for brevity.)

More simply said, if we were to execute
$\boldsymbol{U}(\boldsymbol{\textit{Byz}})$ of Example 3.11 in that model
$M^{\prime\prime}$, the following model would result (as $p_{a}$ is true in
$w_{1}$ and $w_{2}$, the alternatives with precondition $\neg p_{a}$ never
execute):

$M^{\prime\prime}:$$(w_{1})$$(w_{2})$$p_{a}q_{a}$$p_{a}\overline{q_{a}}$$b$$M^{\prime\prime}\odot\boldsymbol{U}(\boldsymbol{\textit{Byz}}):$$(w_{1},(I,p_{a}))$$(w_{1},(R^{ab},p_{a}))$$(w_{2},(I,p_{a}))$$(w_{2},(R^{ab},p_{a}))$$p_{a}q_{a}$$p_{a}q_{a}$$p_{a}\overline{q_{a}}$$p_{a}\overline{q_{a}}$$a$$b$$a$$b$

######  Corollary 4.20.

Communication pattern logic and action model logic are incomparable in update
expressivity.

##  5 Communication patterns for history-based structures

Example 3.12 demonstrated that interpreted systems are not closed under update
with communication patterns. We therefore could not obtain a result for update
expressivity for the class of interpreted systems. In this section we show
that this is after all possible if we adjust the structures in which we
execute updates and simultaneously adjust the definition of the update. In
order to store the sequence of past events we generalize our epistemic models
to history-based epistemic models [5, 9]. Simultaneously, we change the
semantics of the update with a communication pattern namely by having this
depend on the number of previous updates that already took place, what is
known as the number of previous _rounds_ in an oblivious protocol arbitrarily
often executing that communication pattern. The change consists in recording
the information of previous rounds in designated history variables, that store
the _view_ for each agent on all previous rounds. These variables are also
local.

######  Example 5.21.

When updating epistemic model $(\boldsymbol{\textit{Sq}},11)$ with
communication pattern $(\boldsymbol{\textit{IS}},R^{ab})$, we record that
$R^{ab}a=\\{a\\}$ and $R^{ab}b=\\{a,b\\}$ in the resulting world $(11,R^{ab})$
by indexing these sets with the names of the agents, so as $\\{a\\}_{a}$ and
$\\{a,b\\}_{b}$, that we write as $a_{a}$ and $ab_{b}$. These are local
variables. Then, when updating
$(\boldsymbol{\textit{Sq}}\odot\boldsymbol{\textit{IS}},(11,R^{ab}))$ with
$(\boldsymbol{\textit{IS}},R^{ba})$, we record the entire history so far for
$a$ and $b$, where $a$ but not $b$ also receives $b$’s history of the previous
round, as $((a,ab).ab)_{a}$ for agent $a$ and $(ab.b)_{b}$ for agent $b$.

We explain the first. As $a$ receives information from $b$, and by default
from itself, $R^{ba}a=\\{a,b\\}$, written as $ab$, is preceded by the list
$(\\{a\\},\\{a,b\\})$ containing $R^{ab}a=\\{a\\}$ and $R^{ab}b=\\{a,b\\}$ of
the previous round, which is written as $(a,ab)$. The expression $(a,ab).ab$
is the _view_ of agent $a$ on the history, which is a tree. This view is
indexed with the name $a$ of the agent, such that $((a,ab).ab)_{a}$ is a local
variable for agent $a$, wherein the views of $a$ and of $b$ in the previous
round are lexicographically ordered.

And so on for every next round. Such history variables are designated local
variables, initially false.

We adapt the semantics of update $\odot$ by making history variables for a
given round of communication true after the update representing that round. We
name this semantics $\dot{\odot}$.

  * •

in $(\boldsymbol{\textit{Sq}},11)$, variables $p_{a}$ and $p_{b}$ are true and
all others false;

  * •

in
$(\boldsymbol{\textit{Sq}}\dot{\odot}\boldsymbol{\textit{IS}},(11,R^{ab}))$,
variables $p_{a},p_{b},a_{a},ab_{b}$ are true and all others false;

  * •

in
$(\boldsymbol{\textit{Sq}}\dot{\odot}\boldsymbol{\textit{IS}}\dot{\odot}\boldsymbol{\textit{IS}},(11,R^{ab},R^{ba}))$,
variables $p_{a},p_{b},a_{a},ab_{b},((a,ab).ab)_{a},(ab.b)_{b}$ are true and …

The $\dot{\odot}$ semantics is then closed for the class of interpreted
systems. We proceed with formalities.

######  Definition 5.22 (View, history variable).

Let a communication pattern $\boldsymbol{R}$ be given. A _history_ is a member
$\sigma\in\boldsymbol{R}^{*}$ (a finite sequence of communication graphs in
$\boldsymbol{R}$). The _view_ of $a\in A$ on history $\sigma$ is defined as:

$\begin{array}[]{llllll}\mathsf{view}_{a}(\epsilon)&:=&\emptyset&\mathsf{view}_{a}(\sigma.R)&:=&\mathsf{view}_{Ra}(\sigma).Ra\end{array}$

where $\mathsf{view}_{Ra}(\sigma)$ is the ordered list of views
$\mathsf{view}_{b}(\sigma)$ for $b\in Ra$. The set of _history variables_ is
$\boldsymbol{\Sigma}:=$ $\\{(\mathsf{view}_{a}(\sigma))_{a}\mid\sigma\text{ a
history},a\in A\\}$. Also,
$\Sigma^{n}:=\\{(\mathsf{view}_{a}(\sigma))_{a}\in\boldsymbol{\Sigma}\mid|\sigma|=n,a\in
A\\}$, and $\Sigma^{<{n}}=\bigcup_{m<n}\Sigma^{m}$.

The view of agent $a$ on history $\sigma$ defines a tree with root $Ra$ where
$R$ is the last element of $\sigma$. A history variable for $a$ is nothing but
the view of $a$ of a history $\sigma$, subscripted with $a$, denoting a local
variable. The set of views is known as the _full-information protocol_ [15].
We now model the arbitrary iteration of a communication pattern in an
epistemic model, while keeping track of the previous rounds by way of history
variables. The definition is for agents $A$ and variables
$P\cup\boldsymbol{\Sigma}$ (and not, as before, for $A$ and $P$).

######  Definition 5.23 (History epistemic model).

Given an epistemic model $M=(W,\sim,L)$, a communication pattern
$\boldsymbol{R}$, and $n\in\mathbb{N}$, a history epistemic model
$M\dot{\odot}\boldsymbol{R}^{n}$ is defined as follows. For $n=0$,
$M\dot{\odot}\boldsymbol{R}^{0}=M$. For $n\geq 0$, given
$M\dot{\odot}\boldsymbol{R}^{n}=(W\times\boldsymbol{R}^{n},\sim,L)$, we define
$M\dot{\odot}\boldsymbol{R}^{n+1}:=(W\times\boldsymbol{R}^{n+1},\sim^{\prime},L^{\prime})$222Allowing
slight abuse of the notation $\boldsymbol{R}^{n}$. such that:

  * •

$(w,\sigma.R)\sim^{\prime}_{a}(w^{\prime},\sigma^{\prime}.R^{\prime})$ iff
$(w,\sigma)\sim_{Ra}(w^{\prime},\sigma^{\prime})$ and $Ra=R^{\prime}a$;

  * •

$L^{\prime}(w,\sigma.R):=L(w,\sigma)\cup\\{(\mathsf{view}_{b}(\sigma.R))_{b}\mid
b\in A\\}$.

The domain of $M\dot{\odot}\boldsymbol{R}^{n}$ is $W\times\boldsymbol{R}^{n}$,
so that domain elements have shape $(w,\sigma)$. As
$M\dot{\odot}\boldsymbol{R}^{0}=M$, all history variables in
$M\dot{\odot}\boldsymbol{R}^{0}$ are false. This means that no round of
communication has taken place.

The difference between the $\dot{\odot}$ update and the $\odot$ update is
therefore _only_ in the labeling of local variables: we now require a
countably infinite set of local history variables such that in each round for
each agent the entire history is again recorded by making such a variable
true. We will see that this guarantees that interpreted systems are closed
under update.

Given the $\dot{\odot}$ update, the history-based semantics is now as
expected, and unlike the previous semantics it has the property that the
update of an interpreted system remains an interpreted system.

######  Definition 5.24 (History-based semantics).

Given $M\dot{\odot}\boldsymbol{R}^{n}=(W\times\boldsymbol{R}^{n},\sim,L)$ and
$(w,\sigma)\in W$, define _satisfaction relation_ $\models$ by induction on
$\varphi\in\mathcal{L}$ (where $p\in P$, $a\in A$, $B\subseteq A$,
$\boldsymbol{R}$ a communication pattern, $R\in\boldsymbol{R}$,
$\sigma\in\boldsymbol{R}^{n}$, and $\tau\in\boldsymbol{R}^{*}$ — that is,
$\tau$ is an arbitrary history).

$\begin{array}[]{lcl}M\dot{\odot}\boldsymbol{R}^{n},(w,\sigma)\models
p_{a}&\text{iff}&p_{a}\in L(w)\\\
M\dot{\odot}\boldsymbol{R}^{n},(w,\sigma)\models(\mathsf{view}_{a}(\tau))_{a}&\text{iff}&(\mathsf{view}_{a}(\tau))_{a}\in
L(w,\sigma)\\\
M\dot{\odot}\boldsymbol{R}^{n},(w,\sigma)\models\neg\varphi&\text{iff}&M\dot{\odot}\boldsymbol{R}^{n},(w,\sigma)\not\models\varphi\\\
M\dot{\odot}\boldsymbol{R}^{n},(w,\sigma)\models\varphi\wedge\psi&\text{iff}&M\dot{\odot}\boldsymbol{R}^{n},(w,\sigma)\models\varphi\text{
and }M\dot{\odot}\boldsymbol{R}^{n},(w,\sigma)\models\psi\\\
M\dot{\odot}\boldsymbol{R}^{n},(w,\sigma)\models
D_{B}\varphi&\text{iff}&M\dot{\odot}\boldsymbol{R}^{n},(v,\tau)\models\varphi\text{
for all }(v,\tau)\sim_{B}(w,\sigma)\\\
M\dot{\odot}\boldsymbol{R}^{n},(w,\sigma)\models[\boldsymbol{R},R]\varphi&\text{iff}&M\dot{\odot}\boldsymbol{R}^{n+1},(w,\sigma.R)\models\varphi\end{array}$

######  Proposition 5.25.

Let interpreted system $M$ and $\boldsymbol{R}$ be given. Then
$M\dot{\odot}\boldsymbol{R}^{n}$ is an interpreted system.

######  Proof 5.26.

Let $M\dot{\odot}\boldsymbol{R}^{n}=(W\times\boldsymbol{R}^{n},\sim,L)$. We
are required to show that $(w,\sigma)\sim_{a}(w^{\prime},\sigma^{\prime})$ iff
$L(w,\sigma)_{a}=L(w^{\prime},\sigma^{\prime})_{a}$.

For $n=0$ this is because $M$ is an interpreted system.

Let us now assume $M\dot{\odot}\boldsymbol{R}^{n}$ is an interpreted system
and consider $M\dot{\odot}\boldsymbol{R}^{n+1}$, and
$R,R^{\prime}\in\boldsymbol{R}$. We then have that (where
$|\sigma|=|\sigma^{\prime}|=n$):

$(w,\sigma.R)\sim_{a}(w^{\prime},\sigma^{\prime}.R^{\prime})\\\
\Leftrightarrow\hfill\text{by definition of }\sim_{a}\\\ Ra=R^{\prime}a\text{
and }(w,\sigma)\sim_{Ra}(w^{\prime},\sigma^{\prime})\\\ \Leftrightarrow\\\
Ra=R^{\prime}a,\text{ and for all }b\in
Ra:(w,\sigma)\sim_{b}(w^{\prime},\sigma^{\prime})\\\
\Leftrightarrow\hfill\text{inductive hypothesis}\\\ Ra=R^{\prime}a,\text{ and
for all }b\in Ra:L(w,\sigma)_{b}=L(w^{\prime},\sigma^{\prime})_{b}\\\
\Leftrightarrow\hfill(*)\\\
L(w,\sigma.R)_{a}=L(w^{\prime},\sigma^{\prime}.R^{\prime})_{a}$

$(*)$: By definition, we have that
$L(w,\sigma.R)=L(w,\sigma)\cup\\{(\mathsf{view}_{b}(\sigma.R))_{b}\mid b\in
A\\}$. Therefore, for agent $a$, we have that
$L(w,\sigma.R)_{a}=L(w,\sigma)_{a}\cup\\{(\mathsf{view}_{a}(\sigma.R))_{a}\\}$.
As $a\in Ra$, we may assume by induction that
$L(w,\sigma)_{a}=L(w^{\prime},\sigma^{\prime})_{a}$. It therefore remains to
show that
$(\mathsf{view}_{a}(\sigma.R))_{a}=(\mathsf{view}_{a}(\sigma^{\prime}.R^{\prime}))_{a}$.
By the definition of $\mathsf{view}$, this is equivalent to requiring that
$Ra=R^{\prime}a$, and that
$(\mathsf{view}_{b}(\sigma))_{b}=(\mathsf{view}_{b}(\sigma^{\prime}))_{b}$ for
all $b\in Ra$. The latter is given above. Concerning the former: from the
inductive assumption that $L(w,\sigma)_{b}=L(w^{\prime},\sigma^{\prime})_{b}$
for all $b\in Ra$ and the definition of $\mathsf{view}$ for these agents $b$
it follows that
$(\mathsf{view}_{b}(\sigma))_{b}=(\mathsf{view}_{b}(\sigma^{\prime}))_{b}$ for
all $b\in Ra$.

In order to compare the update expressivity of action models and communication
patterns in this semantics, we must also change Def. 8 of induced action model
$\boldsymbol{U}(\boldsymbol{R})$. There are now infinitely many local
variables, so that the description of a valuation is no longer a formula but
an infinite conjunction. However, for every round of communication a
description of the valuation of a finite subset is sufficient.

######  Definition 5.27 (Induced action model for round n).

The induced action model $\boldsymbol{U}^{n}(\boldsymbol{R})=(E,\sim,{\rm
Phys.~{}Rev.~{}E})$ for round $n$ of iterated execution of $\boldsymbol{R}$ is
defined as follows, where $R,R^{\prime}\in\boldsymbol{R}$,
$Q,Q^{\prime}\subseteq P\cup\Sigma^{<{n}}$, and $a\in A$:

$\begin{array}[]{lcl}E&=&\boldsymbol{R}\times\mathcal{P}(P\cup\Sigma^{<{n}})\\\
(R,Q)\sim_{a}(R^{\prime},Q^{\prime})&\text{iff}&Ra=R^{\prime}a\text{ and
}Q_{Ra}=Q^{\prime}_{R^{\prime}a}\\\ {\rm
Phys.~{}Rev.~{}E}(R,Q)&=&\delta_{Q,P\cup\Sigma^{<{n}}}\end{array}$

Although $P\cup\boldsymbol{\Sigma}$ infinite, $P\cup\Sigma^{<{n}}$ is finite.
Note that $\boldsymbol{U}(\boldsymbol{R})$ is
$\boldsymbol{U}^{1}(\boldsymbol{R})$, where $\delta_{Q}$ is now
$\delta_{Q,P}$, as $\Sigma^{<1}=\Sigma^{0}=\emptyset$. We recall the
definition of $\delta_{Q,P\cup\Sigma^{<{n}}}$ from Sect. 2.1. From Prop. 5.25
and Prop. 9 we directly obtain:

######  Proposition 5.28.

Let interpreted system $M$ and communication pattern $\boldsymbol{R}$ be
given. Then $M\dot{\odot}\boldsymbol{R}^{n}$ is bisimilar to
$M\otimes\boldsymbol{U}^{1}(\boldsymbol{R})\otimes\dots\otimes\boldsymbol{U}^{n}(\boldsymbol{R})$.

By abbreviation inductively define $(\boldsymbol{R}^{0},\epsilon):=\epsilon$
and
$(\boldsymbol{R}^{n+1},\sigma.R):=(\boldsymbol{R}^{n},\sigma).(\boldsymbol{R},R)$,
where $\sigma\in\boldsymbol{R}^{n}$. Recalling the definition of
$[\boldsymbol{R}]\varphi$ as
$\bigwedge_{R\in\boldsymbol{R}}[\boldsymbol{R},R]\varphi$, we let
$[\boldsymbol{R}^{n}]\varphi$ stand for
$\bigwedge_{\sigma\in\boldsymbol{R}^{n}}[\boldsymbol{R}^{n},\sigma]\varphi$.
Just as $[\boldsymbol{R}^{n}]\varphi$ is equivalent to
$[\boldsymbol{R}]^{n}\varphi$, $[\boldsymbol{R},\sigma]\varphi$ is equivalent
to $[\boldsymbol{R},R_{1}]\dots[\boldsymbol{R},R_{n}]\varphi$, where
$\sigma=R_{1}\dots R_{n}$.

In the $\odot$ semantics, the answer to the question whether a communication
pattern $(\boldsymbol{R},R)$ is update equivalent to an action model
$(\boldsymbol{U}(\boldsymbol{R}),T)$ where $T=\\{(R,Q)\mid Q\subseteq P\\}$,
on the class of epistemic models, was ‘no’ (Example 3.12). This now becomes
the question whether in the history-based $\dot{\odot}$ semantics an iterated
communication pattern $(\boldsymbol{R}^{n},\sigma)$ is update equivalent to a
multi-pointed action model on the class of interpreted systems with empty
histories. The answer to that is ‘yes’. However, communication pattern
modalities occurring in a formula may not be interpreted in the empty history.
For example, given $[\boldsymbol{R},R](p_{a}\rightarrow
D_{B}[\boldsymbol{R},R^{\prime}]p_{b})$, subformula
$[\boldsymbol{R},R^{\prime}]p_{b}$ will be interpreted in some world $(w,R)$,
not in some world $(w,\epsilon)$. We want it equivalent to some formula of
shape $[\boldsymbol{R},RR^{\prime}]\psi$. We therefore show that any formula
$\varphi\in\mathcal{L}^{\circ}$ is equivalent to one wherein all subformulas
$[\boldsymbol{R}^{n},\sigma]\psi$ have that $\psi\in\mathcal{L}^{-}$ (without
dynamic modalities). All dynamic modalities are then interpreted in an empty
history epistemic model.

Define the iterated update normal form (IUNF), the language
$\mathcal{L}^{\circ}_{\mathsf{iunf}}$ (with members $\varphi$) by BNF as:

$\begin{array}[]{lll}\varphi&:=&p_{a}\mid\neg\varphi\mid\varphi\wedge\varphi\mid
D_{B}\varphi\mid[\boldsymbol{R}^{n},\sigma]\psi\\\
\psi&:=&p_{a}\mid\neg\psi\mid\psi\wedge\psi\mid D_{B}\psi\end{array}$

######  Lemma 5.29.

Every formula in $\mathcal{L}^{\circ}$ is equivalent to one in
$\mathcal{L}^{\circ}_{\mathsf{iunf}}$, in iterated update normal form.

######  Proof 5.30.

We define a translation
$t:\mathcal{L}^{\circ}\rightarrow\mathcal{L}^{\circ}_{\mathsf{iunf}}$. We
prove by induction that any $\varphi$ is equivalent to $t(\varphi)$. All
clauses are trivial, and the one for the dynamic modality has a subinduction.
The subinduction uses the reduction axioms for communication patterns found in
[7].

$\begin{array}[]{lll}t([\boldsymbol{R},R]p_{a})&:=&[\boldsymbol{R},R]p_{a}\\\
t([\boldsymbol{R},R](\varphi\wedge\psi))&:=&t([\boldsymbol{R},R]\varphi)\wedge
t([\boldsymbol{R},R]\psi)\\\ t([\boldsymbol{R},R]\neg\varphi)&:=&\neg
t([\boldsymbol{R},R]\varphi)\\\
t([\boldsymbol{R},R]D_{B}\varphi)&:=&\bigwedge_{R^{\prime}B\equiv
RB}D_{RB}t([\boldsymbol{R},R^{\prime}]\varphi)\\\
t([\boldsymbol{R},R][\boldsymbol{R}^{\prime},R^{\prime}]\varphi)&:=&t([\boldsymbol{R},R]t([\boldsymbol{R}^{\prime},R^{\prime}]\varphi))\end{array}$

In particular, we have that

$\begin{array}[]{llllllll}t([\boldsymbol{R},R](\varphi\vee\psi))&=&t([\boldsymbol{R},R]\neg(\neg\varphi\wedge\neg\psi))&=&\neg
t([\boldsymbol{R},R](\neg\varphi\wedge\neg\psi))&=\\\
\neg(t([\boldsymbol{R},R]\neg\varphi)\wedge
t([\boldsymbol{R},R]\neg\psi))&=&\neg(\neg
t([\boldsymbol{R},R]\varphi)\wedge\neg
t([\boldsymbol{R},R]\psi))&=&t([\boldsymbol{R},R]\varphi)\vee
t([\boldsymbol{R},R]\psi)\end{array}$

We recall that notation $R^{\prime}B\equiv RB$ was defined in Sect. 2.2.
Further proof details are omitted.

######  Proposition 5.31.

Action model logic is at least as update expressive as communication pattern
logic on the class of interpreted systems, in the history-based semantics.

######  Proof 5.32.

Let an interpreted system $M$ and a communication pattern $\boldsymbol{R}$ be
given. Then $M\dot{\odot}\boldsymbol{R}^{n}$ is bisimilar to
$M\otimes\boldsymbol{U}^{1}(\boldsymbol{R})\otimes\dots\otimes\boldsymbol{U}^{n}(\boldsymbol{R})$
(Prop. 5.28). Consider the action model $\boldsymbol{U}$ that is the
_composition_ of $\boldsymbol{U}^{1}(\boldsymbol{R})$, …,
$\boldsymbol{U}^{n}(\boldsymbol{R})$, where we note that, unlike communication
patterns, action models are indeed closed under composition (see [3] for the
definition of action model composition).

Let us now consider what action model some $(\boldsymbol{R}^{n},\sigma)$ is
update equivalent to. We can assume that modalities
$[\boldsymbol{R}^{n},\sigma]$ are only interpreted in $M$, a history epistemic
model for an empty history (Lemma 5.29). Iterated communication pattern
$\boldsymbol{R}^{n}$ is clearly update equivalent to $\boldsymbol{U}$. It is
almost worded as such in Prop. 5.31. Also, any $(\boldsymbol{R}^{n},\sigma)$
is update equivalent to $(\boldsymbol{U},T)$, where, if
$\sigma=R^{1}R^{2}\dots R^{n}$,

$T=\\{(R^{1},Q^{1})(R^{2},Q^{2})\dots(R^{n},Q^{n})\mid Q^{1}\subseteq
P,Q^{2}\subseteq\Sigma^{1},\dots,Q^{n}\subseteq\Sigma^{n-1}\\}.$

Details are omitted. Note that
$P\cup\Sigma^{1}\cup\dots\Sigma^{n-1}=P\cup\Sigma^{<n}$, the set of all atoms
considered at round $n$.

It is easy to see that Prop. 4.15 still holds for the history-based semantics.
Therefore:

######  Corollary 5.33.

Action model logic is more update expressive than communication pattern logic
on the class of interpreted systems, in the history-based semantics.

This story on history-based semantics could just as well have been told for
sequences $\boldsymbol{R}_{1},\dots,\boldsymbol{R}_{n}$ of possibly different
communication patterns, instead of for $n$ iterations of a given communication
pattern $\boldsymbol{R}$. We would then get models
$M\dot{\odot}\boldsymbol{R}_{1}\dot{\odot}\dots\dot{\odot}\boldsymbol{R}_{n}$
instead of models $M\dot{\odot}\boldsymbol{R}^{n}$, and we would get induced
action models
$M\otimes\boldsymbol{U}^{1}(\boldsymbol{R}_{1})\otimes\dots\otimes\boldsymbol{U}^{n}(\boldsymbol{R}_{n})$,
etcetera. However, in distributed computing it is common to consider arbitrary
iteration of the same communication pattern (the mentioned oblivious model).

Although in such a generalization we can continue to view histories as
sequences of communication graphs, it is important to realize that the same
communication graph can then be the point of a different communication
pattern, which may give their execution a different meaning. For example,
recall $R^{ab}b=\\{a,b\\}\cup I$. Given $R^{ab}\in\boldsymbol{\textit{IS}}$,
agent $b$ is uncertain whether $a$ has received his message. But given
$R^{ab}\in\\{R^{ab}\\}$, the singleton communication pattern, agent $b$ knows
that agent $a$ has not received his message.

##  6 Conclusions and further research

We have shown that action model logic and communication pattern logic are
incomparable in update expressivity on epistemic models, and that action model
logic is more update expressive than communication pattern logic on
interpreted systems. It seems promising to investigate communication patterns
further, also on epistemic models that are not local (clearly, incomparability
does not depend on that). Induced action models are exponentially larger than
communication patterns. Communication patterns intuitively specify system
dynamics that abstracts from message content. Results in temporal epistemics
on synchronous and asynchronous computation should carry over to dynamic
epistemics.

#### Acknowledgements

We thank the TARK reviewers for their comments. This work was partially
supported by Programa de Apoyo a Proyectos de Investigación e Innovación
Tecnológica (PAPIIT), project grants IN108720 and IN108723. Diego A. Velázquez
is the recipient of a fellowship from CONACyT.

## References

  * [1]
  * [2] T. Ågotnes & Y.N. Wáng (2017): _Resolving distributed knowledge_.  Artif. Intell. 252, pp. 1–21, 10.1016/j.artint.2017.07.002.
  * [3] A. Baltag, L.S. Moss & S. Solecki (1998): _The Logic of Public Announcements, Common Knowledge, and Private Suspicions_.  In: Proc. of 7th TARK, pp. 43–56.
  * [4] A. Baltag & S. Smets (2020): _Learning What Others Know_.  In: Proc. of 23rd LPAR, EPiC Series in Computing 73, pp. 90–119, 10.29007/plm4.
  * [5] J. van Benthem, J. van Eijck & B. Kooi (2006): _Logics of Communication and Change_.  Information and Computation 204(11), pp. 1620–1662, 10.1016/j.ic.2006.04.006.
  * [6] P. Blackburn, M. de Rijke & Y. Venema (2001): _Modal Logic_.  Cambridge University Press, 10.1017/CBO9781107050884.
  * [7] A. Castañeda, H. van Ditmarsch, D.A. Rosenblueth & D.A. Velázquez (2022): _Communication Pattern Logic: Epistemic and Topological Views_.  CoRR abs/2207.00823, 10.48550/arXiv.2207.00823.  To appear in Journal of Philosophical Logic.
  * [8] H. van Ditmarsch, W. van der Hoek, B. Kooi & L.B. Kuijer (2020): _Arrow Update Synthesis_.  Information and Computation, p. 104544, 10.1016/j.ic.2020.104544.
  * [9] H. van Ditmarsch, J. Ruan & W. van der Hoek (2013): _Connecting Dynamic Epistemic and Temporal Epistemic Logics_.  Logic journal of the IGPL 21(3), pp. 380–403, 10.1093/jigpal/jzr038.
  * [10] C. Dwork & Y. Moses (1990): _Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures_.  Inf. Comput. 88(2), pp. 156–186, 10.1016/0890-5401(90)90014-9.
  * [11] J. van Eijck, J. Ruan & T. Sadzik (2012): _Action emulation_.  Synthese 185(1), pp. 131–151, 10.1007/s11229-012-0083-1.
  * [12] M. Herlihy, D. Kozlov & S. Rajsbaum (2013): _Distributed Computing Through Combinatorial Topology_.  Morgan Kaufmann, 10.1016/C2011-0-07032-1.
  * [13] B. Kooi & B. Renne (2011): _Generalized Arrow Update Logic_.  In: Proc. of 13th TARK, pp. 205–211, 10.1145/2000378.2000403.
  * [14] L. Lamport, R. Shostak & M. Pease (1982): _The Byzantine Generals Problem_.  ACM Trans. Program. Lang. Syst. 4(3), pp. 382–401, 10.1145/357172.357176.
  * [15] Y. Moses & M.R. Tuttle (1988): _Programming Simultaneous Actions Using Common Knowledge_.  Algorithmica 3, pp. 121–169, 10.1007/BF01762112.
  * [16] J.A. Plaza (1989): _Logics of Public Communications_.  In: Proc. of the 4th ISMIS, Oak Ridge National Laboratory, pp. 201–216.
  * [17] F. Roelofsen (2007): _Distributed knowledge_.  Journal of Applied Non-Classical Logics 17(2), pp. 255–273, 10.3166/jancl.17.255-273.
  * [18] D.A. Velázquez, A. Castañeda & D.A. Rosenblueth (2021): _Communication Pattern Models: an Extension of Action Models for Dynamic-Network Distributed Systems_.  In: Proc. of TARK XVIII, EPTCS 335, pp. 307–321, 10.4204/EPTCS.335.29.
  * [19] Y.N. Wáng & T. Ågotnes (2015): _Relativized common knowledge for dynamic epistemic logic_.  J. Appl. Log. 13(3), pp. 370–393, 10.1016/j.jal.2015.06.004.