# Persistent homology with non-contractible preimages

Konstantin Mischaikow  Math. Dept., Rutgers University, New Brunswick, NJ
08901, USA<EMAIL_ADDRESS>and  Charles Weibel  Math. Dept.,
Rutgers University, New Brunswick, NJ 08901, USA<EMAIL_ADDRESS>http://math.rutgers.edu/ weibel

###### Abstract.

For a fixed $N$, we analyze the space of all sequences
$z=(z_{1},\dots,z_{N})$, approximating a continuous function on the circle,
with a given persistence diagram $P$, and show that the typical components of
this space are homotopy equivalent to $S^{1}$. We also consider the space of
functions on $Y$-shaped (resp., star-shaped) trees with a 2-point persistence
diagram, and show that this space is homotopy equivalent to $S^{1}$ (resp., to
a bouquet of circles).

Mischaikow was partially supported by NSF grants 1521771, 1622401, 1839294,
1841324, 1934924, by NIH-1R01GM126555-01 as part of the Joint DMS/NIGMS
Initiative to Support Research at the Interface of the Biological and
Mathematical Science, and a grant from the Simons Foundation.

Weibel was supported by NSF grants, and the Simonyi Endowment at IAS

## Introduction

Topological Data Analysis (TDA) is a rapidly developing body of techniques for
the analysis of high dimensional data associated with nonlinear structures.
Persistent homology has become one of the primary tools in TDA, for reasons
including efficiency of computation, robustness with respect to perturbations
in the data, and dramatic data compression. The focus of this paper is on
understanding the loss of information due to this compression.

To the best of our knowledge, all applications of persistent homology to
experimental data can be characterized as follows. There exists a finite
simplicial complex $K$ and a function $\varphi:K\to\mathbb{R}$ such that each
sublevel set $K_{r}=\varphi^{-1}((-\infty,r])$ defines a subcomplex of $K$.
With this input, the persistent homology algorithm outputs persistence
diagrams $P=\\{P_{i}\\}$, one for each dimension of homology; we will view
them as point clouds in $\mathbb{R}^{2}$.

With regard to compression, an obvious question is: given a fixed complex $K$
and persistence diagrams $\\{P_{i}\\}$, what is the ”preimage” space of
functions $\varphi$ that produce these diagrams? A detailed exposition of the
polyhedral structure of these preimages is given in [LT]. While this geometric
structure is clearly valuable, it does not necessarily translate into an
understanding of what information is lost due to compression.

We will consider the slightly more restrictive setting in which
$\varphi:K\to\mathbb{R}$ is completely determined at $\sigma$ by its values on
the set of adjacent vertices of $K$ by the formula
$\varphi(\sigma)=\max_{v\prec\sigma}\varphi(v)$. If $K$ has $N$ vertices, then
$\varphi$ can be characterized by the vector
$z=(z_{1},\ldots,z_{N})\in\mathbb{R}^{N}$. Therefore, for fixed $K$ we can
view persistent homology as inducing a function

$PH\colon\mathbb{R}^{N}\to\mathbf{Per},$

where $\mathbf{Per}$ denotes the space of persistence diagrams. Given
$P\in\mathbf{Per}$, our long term goal is to understand the preimage
$\mathbf{data}_{P}=PH^{-1}(P)$ as a subset of $\mathbb{R}^{N}$.

In [CMW], we considered the case where $K$ is a simplicial complex
representing an interval, i.e., $K$ consists of $N$ vertices, $N-1$ edges, and
each vertex is the boundary of at most two edges. The primary result is that
each component of $\mathbf{data}_{P}$ is contractible (for the number of
components see [C]). The work in [CMW] was motivated in part to apply
topological fixed point theorems to nonlinear dynamics tracked via persistence
diagrams. In this setting, contractibility is a sufficiently strong condition,
and thus, the collapse of geometry does not result in a loss of information.
We hasten to remark that, even in this simple setting, the geometry of
$\mathbf{data}_{P}$ is nontrivial (see [LT]). However, the machinery of [CMW]
that determines the topology of the preimage is fairly simple and thus worth
pursuing in and of itself.

We consider two families of examples in this paper. The first is where $K$ is
an $N$-gon, representing a circle, and the second is where $K$ is a simple
star-like tree, with at least three branches. In the first case, the typical
components of $\mathbf{data}_{P}$ are homotopic to a circle, reflecting the
topology of $K$; see Corollary 6.4. The reader might find it surprising that
in the second case, when $K$ is a tree with only 3 branches, each of length at
least two, then the preimage $\mathbf{data}_{P}$ is homotopic to a circle;
adding more branches yields a preimage which is homotopic to a bouquet of many
circles (see Sections 7–8).

Though based on the same machinery, the details of the proofs of these two
examples are largely independent. As a result it is easy to see that for an
arbitrary graph $K$ the topology of $\mathbf{data}_{P}$ can be quite
complicated. In fact, we limit ourselves to presenting these two examples
precisely because we do not have a general description of the homotopy type of
$\mathbf{data}_{P}$ based on $K$ and $P$.

This paper is organized into two parts. The first part of the paper considers
the circle, modelled by the $N$-gon. In Sections 2 and 3, we discuss critical
value sequences and the poset $\mathbf{Str}$ of cellular strings. In Section
4, we show that the connected components of a typical component are
homeomorphic to the geometric realization of $\mathbf{Str}$, and analyze the
homotopy type of various sub-posets of $\mathbf{Str}$ in Section 5, via a
series of simple moves. Finally, we prove the main result in Section 6.

The second family of examples is studied in Section 7 (3 branches) and Section
8 (many branches). The nontrivial topology in the preimage $\mathbf{data}_{P}$
arises from the fact that there is a larger family of moves.

##  1\. Preliminaries

As indicated in the introduction, we consider a 1-dimensional complex $K$ and
fix a labelling of the vertices by $i=1,\ldots,N$. We consider functions
$\varphi\colon K\to\mathbb{R}$ determined by the values of $\varphi$ on the
vertices, i.e., $\varphi(\sigma)=\max_{i\prec\sigma}\varphi(i)$. This allows
us to represent $\varphi$ as a vector $z=(z_{1},...,z_{N})\in\mathbb{R}^{N}$,
where $z_{i}=\varphi(i)$.

Each vector $z\in\mathbb{R}^{N}$ defines a sublevel-set filtration of $K$ as
follows. For $r\in\mathbb{R}$, let $K_{r}(z)$ denote the subcomplex of $K$
whose vertices $i$ have $z_{i}\leq r$ and whose edges $[i,j]$ satisfy
$\max\\{z_{i},z_{j}\\}\leq r$. As $r$ varies, the homology $H_{n}$ of the
$K_{r}(z)$ determines a persistence diagram $\operatorname{PH}_{n}(z)$.

We focus on $\operatorname{PH}_{0}$ in this paper, because we restrict our
attention to complexes that are either an $N$-gon or a tree. In these cases
$\operatorname{PH}_{n}(z)$ is empty for $n>1$, and $\operatorname{PH}_{1}(z)$
consists of either the single point $(\max\\{z_{i}\\},\infty)$ or the empty
set, respectively. We write $M$ for the number of points in $PH_{0}(z)$.

A persistence diagram $P$ is considered typical if the coordinates of its $M$
points are distinct, and we say that $z\in\mathbb{R}^{N}$ is a typical point
if its coordinates are distinct. Clearly, typical points have a typical
persistence diagram. We leave the proof of the following lemma to the reader.

######  Lemma 1.1.

Given a complex $K$ of the type discussed in this paper and an associated
typical persistence diagram $PH_{0}(z)=\\{(p_{m}^{b},p_{m}^{d})\\}_{m=1}^{M}$,
then there is a typical point $z^{\prime}$ with
$PH_{0}(z)=PH_{0}(z^{\prime})$.

######  Definition 1.2.

If $z$ is a typical point, we say that a coordinate $z_{i}$ is a local maximum
(resp., a local minimum) if $z_{i}\geq z_{j}$ (resp., $z_{i}\leq z_{j}$) for
all vertices $[j]$ adjacent to $[i]$. The vector $(z_{i_{1}},...,z_{i_{L}})$
in $\mathbb{R}^{L}$ of the local maxima and minima in $z$ is the critical
value sequence of the typical point $z\in\mathbb{R}^{N}$.

### Digraphs.

Given $K$ and $z$, we define a (vertex-weighted) directed graph with
underlying graph $K$ as follows. If $v$ and $w$ are adjacent vertices in $K$
and $z_{v}\geq z_{w}$, there is an edge directed from $v$ to $w$, Note that if
$z_{v}=z_{w}$ then there are two directed edges between $v$ and $w$
($v\rightleftharpoons w$); we call this a two-sided edge.

For a typical $z$, the sources and sinks of the directed graph are local
maxima and minima of $z$. In particular, a local minimum occurs at a source if
and only if it has out-degree 0 and a local maximum occurs at a source if and
only if it has in-degree 0. A vertex of out-degree 1 (and arbitrary in-degree)
plays no role in the persistence diagram; this applies in particular to local
maxima occurring at leaves of the graph.

For any typical $z$, there is a unique vertex $i_{\mathrm{min}}$ for which $z$
is a minimum; the corresponding point in the persistence diagram $P_{0}(z)$ is
$(z_{i_{\mathrm{min}}},\infty)$. All other persistence points are finite, and
each persistence point occurs exactly once.

######  Lemma 1.3.

Suppose that $z$ is a typical point, and $\textrm{out-degree}(i)\neq 1$. Then
there is a persistence point with coordinate $z_{i}$.

###### Proof.

If $i$ has out-degree 0, then $z_{i}$ is a local minima, and hence there is a
persistence point $(p^{b},p^{d})$ with $p^{b}=z_{i}$. If $i$ has out-degree
$\geq 2$ then at least 2 components of $K_{r}$ will merge at $r=z_{i}$, and
thus there is a persistence point $(p^{b},p^{d})$ with $p^{d}=z_{i}$. ∎

######  Remark 1.3.1.

If $z_{i}$ is not a typical point then, after identifying vertices connected
by 2-sided edges, a similar argument applies. We leave the verification to the
reader.

We say that $z_{i}$ is a _critical_ coordinate if the number of out-edges
(after the potential identification) from $i$ is not exactly one.

##  2\. Persistence diagrams on an $N$-gon

Throughout this section $K$ is an $N$-gon, the vertices are identified with
elements of $\mathbb{Z}/N$ (with $0=N$) and there are $N$ edges, $[i,i+1]$,
$0\leq i<N$. Our main result (Corollary 6.4) concerns the preimage
$\mathbf{data}_{P}$ in $\mathbb{R}^{N}$ of a typical persistence diagram: when
$N/2$ is greater than the number $M$ of persistence points of $P$, the
connected components of $\mathbf{data}_{P}$ are homotopy equivalent to
$S^{1}$.

The following result is analogous to [CMW, Lemma 2.4].

######  Lemma 2.1.

Let $z\in\mathbb{R}^{N}$ be a typical point with persistence diagram
$\operatorname{PH}_{0}(z)=\\{(p_{m}^{b},p_{m}^{d})\\}_{m=1}^{M}$. Then $z$ has
$2M$ local extrema; each $p_{m}^{d}$ is a local maximum, and each $p_{m}^{b}$
is a local minimum.

Since there are only finitely many critical value sequences with these local
maxima and minima, only finitely many critical value sequences arise.

######  Remark 2.1.1.

Conversely, if $PH_{0}(z)=\\{(p_{m}^{b},p_{m}^{d})\\}_{m=1}^{M}$ is a
persistence diagram with distinct values, there is a typical point
$z^{\prime}$ with $PH_{0}(z)=PH_{0}(z^{\prime})$.

When $N=2M$, every $z_{i}$ is a local extremum, so $\mathbf{data}_{P}$ is a
finite set. We shall assume that $N>2M$ for the rest of the paper.

######  Example 2.2.

When $N=2M+1$, every point $(z_{1},...,z_{N})$ has exactly one non-extremal
value, every component of $\mathbf{data}_{P}$ is homeomorphic to a circle, and
the components are indexed by the critical value sequences modulo cyclic
rotations.

To see this, fix a critical value sequence $v=(a,b,...,s,t)$ using the $2M$
values $p_{m}^{b},p_{m}^{d}$ in Lemma 2.1; there are only $N$ places to insert
a non-extremal element. Let $C_{i}(v)$, $i=0,\ldots,N-1$ denote the subspace
of points in $\mathbf{data}_{P}$ with critical value sequence $v$, where
$z_{i}$ is the non-extremal value. Then $C_{i}(v)$ is an open interval, whose
closure $\bar{C}_{i}(v)$ meets $\bar{C}_{i-1}(v)$ and $\bar{C}_{i+1}(v)$ in an
endpoint when $i\neq 0,N-1$. Writing $Rv$ for the cyclic rotation
$(t,a,b,...,s)$ of $v$, the closure of $C_{0}(v)$ meets $\bar{C}_{1}(v)$ and
$\bar{C}_{N-1}(Rv)$, as $z_{0}$ is between $z_{1}=a$ and $z_{N-1}=d$.
Similarly, the closure of $C_{N-1}(v)$ meets $\bar{C}_{N-1}(v)$ and
$\bar{C}_{0}(R^{-1}v)$.

To count the number of components, note that the cyclic order of the local
extrema cannot be changed without changing the persistence diagram, all points
in $C(z)$ must have the same critical value sequence as $z$, up to rotation.

##  3\. The poset $\mathbf{Str}$ of cellular circular strings

Throughout this section $K$ is an $N$-gon. A circular symbol string is a
string of symbols $s=s_{1}\cdots s_{N}$, where each symbol is either $0,1$ or
$X$; we will refer to 0 and 1 as bits. (Cf. [CMW].) Any associated symbol
string has a canonical representation as the concatenation
$s=\gamma_{1}\cdots\gamma_{J}$ of blocks $\gamma_{i}$, each block consisting
of the same symbol, such that adjacent blocks have different symbols. Because
of our wrap-around convention, it is possible that the last block has the same
symbol as the first.

######  Definition 3.1.

A circular symbol string $s=s_{1}\cdots s_{N}$ is a circular cellular string
of rank $M>0$ if for the canonical representation
$s=\gamma_{1}\cdots\gamma_{J}$:

  1. (i)

exactly $M$ blocks have symbol 0, and

  2. (ii)

if $\gamma_{j}$ consists of the symbol $X$ and $j\neq 1,J$, then the symbols
of $\gamma_{j-1}$ and $\gamma_{j+1}$ are different.

The _dimension_ of a cellular string $s$, $\dim(s)$, is the number of symbols
$X$ in $s$; it is at most $N-2M$.

Fix $N$ and $M<N/2$. The set $\mathbf{Str}=\mathbf{Str}(N,M)$ of circular
cellular strings of length $N$ and rank $M$ is a poset, where $s^{\prime}<s$
if the string $s$ is obtained from $s^{\prime}$ by replacing some of the bits
0 and 1 in $s^{\prime}$ by $X$. For example, in $\mathbf{Str}(3,1)$ we have
$X01>001<0X1>011<01X$.

######  Proposition 3.2.

The maximal elements of $\mathbf{Str}(N,M)$ are the strings of dimension
$N-2M$.

###### Proof.

(Cf. [CMW, Prop. 2.8].) If $s$ has smaller dimension then there is a block of
length $\geq 2$ of symbols $0$ or $1$. Replacing the first symbol in the block
by $X$ yields a symbol $s^{\prime}$ with $s<s^{\prime}$, so $s$ is not
maximal. ∎

######  Lemma 3.3.

Every string $s^{\prime}$ in $\mathbf{Str}$ is the greatest lower bound of the
set of maximal strings $s$ with $s^{\prime}<s$.

Every maximal chain in $\mathbf{Str}$ has length $N-2M$.

###### Proof.

The proof of [CMW, Lemma 2.9] goes through. Briefly, we proceed by downward
induction on the dimension $d=\dim(s^{\prime})$. Replacing the two end symbols
of a block by $X$ yields two $(d+1)$-dimensional strings whose greatest lower
bound is $s^{\prime}$. ∎

##  4\. The polytopes for the $N$-gon

Throughout this section we work the $N$-gon. Fix a critical value sequence
$(z_{n_{1}},...,z_{n_{2M}})$ of a typical point $z$. To each circular cellular
string $s$, represented in block form as $\gamma_{1}\cdots\gamma_{J}$, we
associate a polytope $T(s)=\prod T(\gamma_{j})$ as in [CMW]:

  * •

if $\gamma_{j}$ is the $k^{th}$ block involving 0 or 1 we set
$T(\gamma_{j})=\\{z_{k}\\}^{n_{k}}$;

  * •

if $\gamma_{j}$ involves $X$ and $\gamma_{j-1}$ is the $k^{th}$ block
involving 0 or 1, we define $T(\gamma_{j})$ to be the simplex of all monotone
sequences $(x_{1},...,x_{n_{j}})$ of length $n_{j}$ between $z_{k}$ and
$z_{k+1}$.

Fix a persistence diagram $P$, and a component $C$ of $\mathbf{data}_{P}$.
Then for any typical point $z$ in $C$, it is clear from the definition 1.2 of
a critical value sequence that $C$ is the union of the simplices $T(s)$, where
$s\in\mathbf{Str}(N,M)$ For this, it is convenient to work with the poset of
circular cellular strings.

Let $s$ be a circular cellular string with $k$ blocks with symbols $X$, of
lengths $n_{1},...,n_{k}$. Recall from [CMW, Example 2.10, Theorem 2.13] that
the geometric realization of the sub-poset
$\mathbf{Str}/s=\\{s^{\prime}:s^{\prime}\leq s\\}$ is homeomorphic to the
product $\Delta^{n_{1}}\times\cdots\Delta^{n_{k}}$ of simplices, i.e., to
$T(s)$.

######  Theorem 4.1.

If $z$ is a typical point, the connected component $C(z)$ of
$\mathbf{data}_{P}$ is homeomorphic to the geometric realization of
$\mathbf{Str}$.

###### Proof.

The proof in [CMW, Theorem 2.13] goes through. The key observation is that for
each $s_{1},...,s_{n}$, the intersection of the realizations of the
$\mathbf{Str}/s_{i}$ is the realization of $\mathbf{Str}/s^{\prime}$, where
$s^{\prime}$ is the greatest lower bound of the $s_{i}$. ∎

######  Example 4.2.

In [LT], a similar problem is studied with a different filtration,
intermediate between the polygon with $N$ vertices and its subdivision, which
has $2N$ vertices. The comparison is sketched in Section 5.2 of [LT].

##  5\. Homotopy operations

Let $\mathbf{Str}_{0}$ (resp., $\mathbf{Str}_{1}$) denote the sub-poset of
strings in $\mathbf{Str}$ whose initial bit is 0 (resp., 1), such that $s_{1}$
and $s_{N}$ are not both 0 (resp., 1). For example, $0X1X$, $X0101$ and
$XXX01$ are in $\mathbf{Str}_{0}$.

######  Proposition 5.1.

The classifying spaces of $\mathbf{Str}_{0}$ and $\mathbf{Str}_{1}$ are
contractible.

###### Proof.

This is the content of Proposition 3.5 and Corollary 3.6 in [CMW]. The sub-
poset of $\mathbf{Str}$ in loc. cit. consisting of strings such that $s_{1}$
and $s_{N}$ are not both 0 is our $\mathbf{Str}_{0}$, and the poset morphisms
used in that proof send $\mathbf{Str}_{0}$ to itself. The realizations of
those poset morphisms, when composed, give a homotopy from $B\mathbf{Str}_{0}$
to a point. The proof for $\mathbf{Str}_{1}$ is the same. ∎

For symbols $a,b$ we write $\mathbf{Str}_{ab}$ for the sub-poset of strings in
$\mathbf{Str}$ whose initial and terminal symbols are $a$ and $b$,
respectively; we abbreviate such a string as $a\sigma b$, where $\sigma$ is a
string of length $N-2$.

Let $\overline{\mathbf{Str}}_{00}$ denote the sub-poset of strings in
$\mathbf{Str}$ whose initial and terminal symbols are either: both 0; 0 and
$X$; or $X$ and 0. Thus $\overline{\mathbf{Str}}_{00}$ contains
$\mathbf{Str}_{00}$ as well as $\mathbf{Str}_{0X}$ and $\mathbf{Str}_{X0}$ and
is disjoint from $\mathbf{Str}_{0}$. Since the initial bit for
$s\in\mathbf{Str}_{X0}$ is 1,

(5.2)
$\overline{\mathbf{Str}}_{00}\cap\mathbf{Str}_{0}=\mathbf{Str}_{0X},\quad\overline{\mathbf{Str}}_{00}\cap\mathbf{Str}_{1}=\mathbf{Str}_{X0}.$

We define $\overline{\mathbf{Str}}_{11}$ similarly, by interchanging 0 and 1.
Thus:

(5.3)
$\overline{\mathbf{Str}}_{11}\cap\mathbf{Str}_{1}=\mathbf{Str}_{1X},\quad\overline{\mathbf{Str}}_{11}\cap\mathbf{Str}_{0}=\mathbf{Str}_{X1}.$

######  Lemma 5.4.

$B\mathbf{Str}_{00}$ is a deformation retract of
$B\overline{\mathbf{Str}}_{00}$.
By symmetry, $B\mathbf{Str}_{11}$ is a deformation retract of
$B\overline{\mathbf{Str}}_{11}$.

###### Proof.

Define $R:\overline{\mathbf{Str}}_{00}\to\mathbf{Str}_{00}$ to be the identity
on $\mathbf{Str}_{00}$, and $R(0\sigma X)=0\sigma 0$, $R(X\sigma 0)=0\sigma
0$. It is easy to see that $R$ is a poset map, and that $R(s)\leq s$, i.e.,
$R\Rightarrow\mathrm{id}$ is a natural transformation. Taking the geometric
realization, we see that $R$ is a continuous map, and that $R$ is homotopic to
the identity on $B\overline{\mathbf{Str}}_{00}$. ∎

######  Definition 5.5.

If $s$ is a circular cellular string in $\mathbf{Str}_{00}$, we define
$F_{1}(s)$ as follows (cf. [CMW, Def. 3.1]). If $s=0X\sigma 0$, set
$F_{1}(s)=s$. If not, there are two cases. Case (i): if $s$ has no 00 or 11
preceding the leftmost $X$, $F_{1}(s)$ transposes that $X$ with the bit
immediately preceding it. Case (ii): if $s$ has the form
$\sigma_{1}abb\sigma_{2}$, where $\sigma_{1}a$ is an alternating bitstring
(beginning with 0) and $\sigma_{2}$ is the remainder of the string, we set
$F_{1}(s)=\sigma_{1}aab\sigma_{2}$. Note that in case (ii), $\sigma_{2}$ is
either empty or ends in 0.

Let $\mathbf{Str}_{00}^{(\ell)}$ denote the sub-poset of $\mathbf{Str}_{00}$
consisting in strings beginning $0X\\!\cdots\\!X$ ($\ell\\!-\\!1$ symbols
$X$). The definition of
$F_{\ell}:\mathbf{Str}_{00}^{(\ell)}\to\mathbf{Str}_{00}^{(\ell)}$ mimicks
that of $F_{1}$; if $s=0\beta\sigma$ (where $\beta$ is a sequence of
$(\ell\\!-\\!1)$ symbols $X$) then $F_{\ell}(s)=0\beta F_{1}(\sigma)$.

######  Lemma 5.6.

$F_{1}:\mathbf{Str}_{00}\to\mathbf{Str}_{00}$ is a poset morphism and
$F_{1}^{k}(\mathbf{Str}_{00})=\mathbf{Str}_{00}^{(2)}$ for $k\gg 0$.

###### Proof.

We proceed by downward induction to show that if $s^{\prime}<s$ then
$F_{1}(s^{\prime})\leq F_{1}(s)$. If the initial $X$ in $s^{\prime}$ is not
preceded by a $00$ or $11$, the same is true for $s$, and the inequality is
evident. Next, suppose that $s^{\prime}=\sigma_{1}abb...b\sigma_{2}$, where
$\sigma_{1}a$ is an alternating bitstring. If
$s=\sigma_{1}abb...b\sigma_{2}^{\prime}$ with
$\sigma_{2}<\sigma_{2}^{\prime}$, we also have $F_{1}(s^{\prime})<F_{1}(s)$.
Otherwise, either $s\geq s_{1}$ or $s\geq s_{2}$, where
$s_{1}=\sigma_{1}aXb\cdots b\sigma_{2}$ and $s_{2}=\sigma_{1}ab\cdots
X\sigma_{2}$. Since $F_{1}(s^{\prime})<F_{1}(s_{1})$ and
$F_{1}(s^{\prime})<F_{1}(s_{2})$, the result follows by induction. ∎

######  Proposition 5.7.

$\mathbf{Str}_{00}$, $\overline{\mathbf{Str}}_{00}$, $\mathbf{Str}_{11}$ and
$\overline{\mathbf{Str}}_{11}$ are contractible.

###### Proof.

We give the proof for $\mathbf{Str}_{00}$; it follows by symmetry and Lemma
5.4 that $\overline{\mathbf{Str}}_{00}$, $\mathbf{Str}_{11}$ and
$\overline{\mathbf{Str}}_{11}$ are also contractible.

We first show that $\mathbf{Str}_{00}^{(2)}\to\mathbf{Str}_{00}$ is a homotopy
equivalence. As in [CMW, Proposition 3.5], we filter $\mathbf{Str}_{00}$ by
sub-posets $Fil_{i}$, where $Fil_{0}=\mathbf{Str}_{00}^{(2)}$ and $Fil_{i}$ is
the full sub-poset on the strings $s$ with
$F_{1}^{i}(s)\in\mathbf{Str}_{00}^{(2)}$. Since $F_{1}$ maps $Fil_{i}$ to
$Fil_{i-1}$, the geometric realization of $F_{1}$ restricts to a continuous
map from $BFil_{i}$ to $BFil_{i-1}$.

To see that $BFil_{i-1}\subseteq BFil_{i}$ is a homotopy equivalence, we
define a poset endomorphism $h$ on $Fil_{i}$ as follows. If $s\in Fil_{i-1}$
then $h(s)=s$. Otherwise, define $h(s)$ to be the greatest lower bound of $s$
and $F_{1}(s)$. Thus $Bh$ is a retract of $BFil_{i}$ onto $BFil_{i-1}$. For
$s\in Fil_{i}$, the inequalities $F_{1}(s)\leq h(s)\geq s$ yield natural
transformations from $h$ to $F_{1}$ and to the identity, and hence homotopies
between the identity map, $Bh$, and $BF_{1}$. These homotopies show that
$BFil_{i-1}\simeq BFil_{i}$. Composing these homotopies gives a homotopy
equivalence between $B\mathbf{Str}_{00}$ and
$BFil_{0}=B\mathbf{Str}_{00}^{(2)}$.

The same argument, mutatis mutandis, shows that each inclusion
$\mathbf{Str}_{00}^{(\ell-1)}\to\mathbf{Str}_{00}^{(\ell)}$ is a homotopy
equivalence. Since $B\mathbf{Str}_{00}^{(\ell)}$ is the point $\\{0X\cdots
X10\cdots 10\\}$ when $\ell=N-2m+1$, $B\mathbf{Str}_{00}$ is homotopy
equivalent to a point, as claimed. ∎

######  Proposition 5.8.

$\mathbf{Str}_{0X}$ and $\mathbf{Str}_{X0}$ are contractible.
By symmetry, $\mathbf{Str}_{1X}$ and $\mathbf{Str}_{X1}$ are also
contractible.

###### Proof.

Since the posets $\mathbf{Str}_{0X}$ and $\mathbf{Str}_{X0}$ are isomorphic
(by the front-to-back permutation of strings), it suffices to give the proof
for $\mathbf{Str}_{0X}$. By Example 2.2, We may assume that $N>2M+1$.
Definition 5.5 goes through word for word in this setting to yield a poset
endomorphism $F_{1}$ on $\mathbf{Str}_{0X}$, with the image of $F_{1}^{K}$
being $\mathbf{Str}_{0X}^{(2)}$ for $K\gg 0$. Now the proof of Proposition 5.7
goes through to show that $\mathbf{Str}_{0X}$ is contractible. ∎

##  6\. Circular components

Let $Q$ denote the 8-element poset on the left of diagram (6.1); the 4 corners
are minimal elements, and the 4 side-vertices are maximal. The geometric
realization $BQ$ of $Q$ has a vertex for each element of $Q$ and an edge for
each strict inequality; there are no higher simplices because the poset $Q$
has no chains $q_{0}<q_{1}<q_{2}$. Thus $BQ$ is an octagon, homeomorphic to a
circle. The sub-posets of $\mathbf{Str}$ we have described fit into the right-
hand diagram below, where the arrows indicate inclusion.

(6.1)
$\textstyle{0X\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$$\textstyle{X1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{00}$$\textstyle{Q}$$\textstyle{11}$$\textstyle{X0\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$$\textstyle{X1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
$\textstyle{\mathbf{Str}_{0X}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathbf{Str}_{0}}$$\textstyle{\mathbf{Str}_{X1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\overline{\mathbf{Str}}_{00}}$$\textstyle{\overline{\mathbf{Str}}_{11}}$$\textstyle{\mathbf{Str}_{X0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathbf{Str}_{1}}$$\textstyle{\mathbf{Str}_{1X}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

Define $f:\mathbf{Str}\to Q$ by sending elements of $\mathbf{Str}_{0X}$,
$\mathbf{Str}_{0X}$, $\mathbf{Str}_{1X}$ and $\mathbf{Str}_{X1}$ to the
corresponding minimal vertices of $Q$, as indicated by (6.1); strings in
$\mathbf{Str}_{00}$ and $\mathbf{Str}_{11}$ are sent to the vertices indicated
by $\overline{\mathbf{Str}}_{00}$ and $\overline{\mathbf{Str}}_{11}$,
respectively. The strings in $\mathbf{Str}_{0}$ not in $\mathbf{Str}_{0X}$ or
$\mathbf{Str}_{X1}$ (resp., in $\mathbf{Str}_{1}$ not in $\mathbf{Str}_{X0}$
or $\mathbf{Str}_{1X}$) are sent to the other maximal vertices of $Q$, as
indicated. It is clear that $f$ is a poset morphism.

Recall from [WK, IV.3.2.3] that for $q\in Q$, the comma category $f/q$ has
objects the pairs $(s,q)$, where $f(s)\leq q$, i.e., $s\in\mathbf{Str}$ such
that $f(s)\leq q$; and there is a morphism from $(s^{\prime},q)$ to $(s,q)$ if
and only if $s^{\prime}\leq s$ in $\mathbf{Str}$.

######  Lemma 6.2.

The right-hand side of diagram (6.1) is the diagram of the comma categories
$f/q$ for $q\in Q$.

###### Proof.

For the minimal elements $q=ab$ of $Q$, it is a tautology that
$f/q=f^{-1}(q)=\mathbf{Str}_{q}$. Since $\overline{\mathbf{Str}}_{00}$ is the
union of $f^{-1}(00)$, $f^{-1}(0X)$ and $f^{-1}(X1)$, we see that
$f/0=\overline{\mathbf{Str}}_{00}$; by symmetry we also have
$f/1=\overline{\mathbf{Str}}_{11}$. The definition of $f$ on
$\mathbf{Str}_{0}$ and $\mathbf{Str}_{1}$ ensures that we also have
$f/0=\mathbf{Str}_{0}$ and $f/1=\mathbf{Str}_{1}$. ∎

######  Theorem 6.3.

$B\mathbf{Str}$ is homotopic to the circle $S^{1}$.

###### Proof.

Quillen’s Theorem A says that if the geometric realization of every $f/q$ is
contractible, then $Bf:B\mathbf{Str}\to BQ\simeq S^{1}$ is a homotopy
equivalence (see [WK, IV.3.7]). By (5.2), (5.3), Propositions 5.7 and 5.8, the
geometric realizations of all the $f/q$ are contractible. ∎

Combining Lemma 1.1 with Theorems 4.1 and 6.3, we obtain:

######  Corollary 6.4.

If $P$ is a typical persistence diagram, every connected component of
$\mathbf{data}_{P}$ is homotopy equivalent to $S^{1}$.

##  7\. $Y$-shaped configurations

In this section we show that $\mathbf{data}_{P}$ can still be homotopic to a
circle, even for rooted trees with three branches and persistence diagram
$P=\\{(0,\infty),(1,4)\\}$ for $H_{0}$. (The choice of $0<1<4$ is for
concreteness.)

For simplicity, we focus on the case where the tree $K$ has vertex set
$V=\\{i\mid i=1,\ldots,7\\}$ and edges

$E=\\{[1,2],[2,3],[3,4],[4,5],[3,6],[6,7]\\}.$

That is, the central vertex $3$ has degree 3, and the endpoints are vertices
$1$, $5$, and $7$. The three branches ($\alpha$, $\beta$, and $\gamma$) are
generated by the vertices $\\{1,2,3\\}$, $\\{3,4,5\\}$, and $\\{3,6,7\\}$,
respectively.

Figure (7.1) illustrates six points $z_{A},z_{B},...$ in $\mathbf{data}_{P}$
with their directed graphs $\Gamma(z_{A}),\Gamma(z_{B}),\ldots$ (as in Section
1). The critical coordinates are marked by their values $0$, $1$, and $4$. The
other $z_{i}$ are marked by $X$; they not critical coordinates and their exact
value is unimportant.

(7.1) |
---|---
$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{z_{A}}$ |
---|---
$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$$\textstyle{z_{B}}$ |
---|---
$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{z_{C}}$ |
---|---
$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{z_{A^{\prime}}}$ |
---|---
$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$$\textstyle{z_{B^{\prime}}}$ |
---|---
$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{z_{C^{\prime}}}$

######  Construction 7.2.

Consider the point $z_{A}\in\mathbb{R}^{7}$, illustrated on the left of (7.1).
The extremal points $0$, $4$ and $1$ all lie on branch $\alpha$. In analogy
with [CMW], it is possible to slide the $041$ two places to the right (to
$z_{B}$ on branch $\beta$) without changing the directed edges on branch
$\gamma$. Beginning with $z_{B}$, we can slide $041$ clockwise up (to $z_{C}$
on branch $\gamma$) without changing the directed edges on branch $\alpha$. We
now slide 140 two places to the left (to $z_{A^{\prime}}$ on branch $\alpha$)
without changing the directed edges on branch $\beta$.

This maneuver (which resembles a clockwise ’K-turn’ in a car) results in the
critical coordinates $0$ and $1$ switching places. Following this with a
second K-turn ($z_{A^{\prime}}$ to $z_{B^{\prime}}$ to $z_{C^{\prime}}$ to
$z_{A}$) returns us to the starting configuration.

Construction 7.2 shows that the six points in (7.1) lie on a non-trivial loop;
it will turn out to be a generator of the fundamental group of
$\mathbf{data}_{P}$. While obvious, it is perhaps worth emphasizing that these
sequences of slides are not possible on the interval or $N$-gon. These new
moves make it possible for the topology of $\mathbf{data}_{P}$ to be more
interesting.

Let $\mathbf{Br}_{\alpha}$ be the subspace of $\mathbf{data}_{P}$ consisting
of all $z$ with $z_{i}=0$ for some vertex $i$ on branch $\alpha$, and
$z_{j}\neq 4$ for all vertices $j$ on branch $\alpha$ further from the central
vertex than vertex $i$. In Figure (7.1), $z_{A}$, $z_{B}$ and $z_{C^{\prime}}$
are in $\mathbf{Br}_{\alpha}$.

The subspaces $\mathbf{Br}_{\beta}$ and $\mathbf{Br}_{\gamma}$ are defined
similarly.

######  Lemma 7.3.

$\mathbf{Br}_{\alpha}$, $\mathbf{Br}_{\beta}$ and $\mathbf{Br}_{\gamma}$ are
contractible.

Figure (7.4) illustrates the steps in the proof, starting from
$z_{C^{\prime}}$.

###### Proof.

By symmetry, it suffices to consider $\mathbf{Br}_{\alpha}$. We shall use
three steps to construct a deformation retraction of $\mathbf{Br}_{\alpha}$ to
a point. By definition there exists a vertex $i_{0}$ closest to the endpoint
$i_{\alpha}=1$ of branch $\alpha$ with $z_{i_{0}}=0$. For the first step,
continuously decrease the value of $z_{j}$ to $0$ for every vertex between
$i_{\alpha}$ and $i_{0}$ (and do nothing if $i_{0}=i_{\alpha}$). This is a
deformation retraction onto the subspace of all $z^{\prime}$ which are 0 at
$i_{\alpha}$.

For the second step of the homotopy, given a point with $z_{i_{\alpha}}=0$,
consider the set of vertices $j$ such that the path from vertex $i_{\alpha}$
to vertex $j$ does not contain a vertex $k$ with $z_{k}=1$. We can
continuously change the values of $z_{j}$ at all these vertices to $4$. This
is a deformation retraction to the subspace of all $z^{\prime\prime}$ where
$z^{\prime\prime}=4$ at vertex 2 (the vertex adjacent to $i_{\alpha}=1$).

Finally, given $z^{\prime\prime}$, we can continuously decrease the value of
$z^{\prime\prime}_{j}$ to $1$ for all vertices $j$ other than $i_{\alpha}$ and
its neighbor. The result is deformation retraction to the point
$z=(0,4,1,...,1)$, showing that $\mathbf{Br}_{\alpha}$ is contractible. ∎

(7.4)
$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$$\textstyle{0}$$\textstyle{0\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$$\textstyle{0}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{4}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{0}$$\textstyle{4\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

We write $\mathbf{Br}_{\alpha\gamma}$ for
$\mathbf{Br}_{\alpha}\cap\mathbf{Br}_{\gamma}$. It is the subspace of all $z$
where $z=0$ at the central vertex, while the vertex with $z=1$ (and hence the
vertex with $z=4$) lies on branch $\beta$. For example, $z_{B}$ is in
$\mathbf{Br}_{\alpha\gamma}$. The subspaces $\mathbf{Br}_{\alpha\beta}$ and
$\mathbf{Br}_{\beta\gamma}$ are defined similarly.

######  Lemma 7.5.

$\mathbf{Br}_{\alpha\gamma}$, $\mathbf{Br}_{\alpha\beta}$ and
$\mathbf{Br}_{\beta\gamma}$ are contractible.

###### Proof.

By symmetry, it suffices to consider $\mathbf{Br}_{\alpha\gamma}$. For the
7-vertex tree, $\mathbf{Br}_{\alpha\gamma}$ consists of just the points of the
form $z_{B}$, illustrated by the second diagram of (7.1). In particular,
$\mathbf{Br}_{\alpha\gamma}$ is contractible. ∎

######  Remark 7.5.1.

The proofs of Lemmas 7.3 and 7.5 go through for longer $Y$-shaped trees, i.e.,
rooted trees with a central vertex of degree 3 with 3 linear branches of
length $\geq 2$ attached to it. (The vertices $1,2,3$ are at the end of branch
$\mathbf{Br}_{\alpha}$.)

By inspection, every point in the preimage $\mathbf{data}_{P}$ lies in one of
the subspaces $\mathbf{Br}_{q}$. Since the intersection of any two branches is
contractible, we see that the preimage $\mathbf{data}_{P}$ is path-connected.

Let $Q$ denote the 6-element poset on the left of diagram (7.6); the elements
$\alpha,\beta,\gamma$ are maximal and the others are minimal. Thus $BQ$ is a
hexagon, homeomorphic to the circle $S^{1}$.

Consider the topological poset $\mathbf{Br}$ of pairs $(x,q)$ with
$x\in\mathbf{Br}_{q}$, illustrated by the right of (7.6). It is clear that
there is a poset morphism $f:\mathbf{Br}\to Q$ sending elements $(x,q)$ to
$q$.

(7.6)
$\textstyle{\alpha\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\alpha\gamma}$$\textstyle{\gamma\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\alpha\beta}$$\textstyle{\beta\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\beta\gamma}$
$\textstyle{\mathbf{Br}_{\alpha}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathbf{Br}_{\alpha\gamma}}$$\textstyle{\mathbf{Br}_{\gamma}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathbf{Br}_{\alpha\beta}}$$\textstyle{\mathbf{Br}_{\beta}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathbf{Br}_{\beta\gamma}}$

######  Lemma 7.7.

The geometric realization of $\mathbf{Br}$ is homotopy equivalent to
$\mathbf{data}_{P}$.

###### Proof.

For each $q$, the realization $|\mathbf{Br}|$ contains a subspace homeomorphic
to $\mathbf{Br}_{q}$, and for each $q^{\prime}<q$ the realization contains the
mapping cylinder of the inclusion
$\mathbf{Br}_{q^{\prime}}\subset\mathbf{Br}_{q}$. Thus there is a natural map
from $|\mathbf{Br}|$ onto $\mathbf{data}_{P}$. Since
$\mathbf{Br}_{q^{\prime}}$ is a subspace of two subspaces $\mathbf{Br}_{q}$,
it is easy to see that $|\mathbf{Br}|\to\mathbf{data}_{P}$ is a homotopy
equivalence. ∎

######  Theorem 7.8.

The preimage $\mathbf{data}_{P}$ is homotopic to $S^{1}$.

###### Proof.

By Lemma 7.7, it suffices to show that $f$ induces a homotopy equivalence
$|\mathbf{Br}|\to BQ\simeq S^{1}$. By Quillen’s Theorem A, it suffices to show
that (the realization of) each comma category $f/q$ is contractible.

The comma category $f/q$ is the poset of all pairs $(x,q^{\prime}\leq q)$ with
$x\in\mathbf{Br}_{q^{\prime}}$. If $q$ is minimal in $Q$,
$f/q=f^{-1}(q)=\mathbf{Br}_{q}$, which is contractible by Lemma 7.5. If $q$ is
maximal, we still have $f^{-1}(q)=\mathbf{Br}_{q}$ but $f/q$ contains elements
$(x,q^{\prime}<q)$. The geometric realization of the natural transformation
$\eta:(x,q^{\prime}\leq q)\Rightarrow(x,q)$ is a deformation retraction from
$B(f/q)$ to the subspace $B(f^{-1}q)$, which is contractible by Lemma 7.3. ∎

##  8\. Star-like configurations

In this section, we generalize from $Y$-shaped trees to star-like trees, i.e.,
trees with a central vertex of degree $n$ and $n$ linear branches of length at
least 2 attached to it. (The $Y$-shaped trees of Section 7 form the case
$n=3$.)

For $q=1,...,n$, let $\mathbf{Br}_{q}$ be the subspace of all $z$ with
$z_{i}=0$ for some vertex on branch $q$, and $z_{j}\neq 4$ for all vertices
$j$ on branch $q$ further from the central vertex than $i$. The proof of Lemma
7.3 goes through to show that $\mathbf{Br}_{q}$ is contractible for each
$q=1,...,n$.

Set $\mathbf{Br}^{\prime}_{q}=\bigcap_{p\neq q}\mathbf{Br}_{p}$; it is the
subspace of all $z$ where $z=0$ at the central vertex, while there is a vertex
with $z=1$ (and hence a vertex with $z=4$) lies on branch $q$. The proof of
Lemma 7.5 goes through to show that each $\mathbf{Br}^{\prime}_{q}$ is
contractible.

Since each point of $\mathbf{data}_{P}$ lies on one of the branches, which are
contractible, and each $\mathbf{Br}^{\prime}_{q}$ is contractible,
$\mathbf{data}_{P}$ is path-connected.

######  Theorem 8.1.

$\mathbf{data}_{P}$ is homotopy equivalent to a bouquet $\bigvee S^{1}$ of
$(n^{2}-3n+1)$ circles.

When $n=3$, this yields 1 circle, as in Theorem 7.8; for $n=4$ branches,
$\mathbf{data}_{P}$ is homotopy equivalent to a bouquet of 5 circles.

###### Proof.

Consider the poset $Q$ whose elements are the $2n$ branches $\mathbf{Br}_{q}$
and $\mathbf{Br}^{\prime}_{q}$, with
$\mathbf{Br}^{\prime}_{q}<\mathbf{Br}_{p}$ for every $p\neq q$. The
realization of this poset is a bipartite graph $\Gamma$ such that every vertex
of $\Gamma$ has degree $n-1$. Since $\Gamma$ has $2n$ vertices and $n^{2}-n$
edges, its Euler characteristic is

$\chi=V-E=3n-n^{2}.$

Since $\Gamma$ is connected, and $\chi=\dim H_{0}(\Gamma)-\dim H_{1}(\Gamma)$,
$\Gamma$ is homotopy equivalent to a bouquet of $1-\chi=(n^{2}-3n+1)$ circles.

Consider the topological poset $\mathbf{Br}$ of pairs $(x,s),$ where
$x\in\mathbf{Br}_{s}$, and pairs $(x,s^{\prime}),$ where
$x\in\mathbf{Br}^{\prime}_{s}$; there is an obvious poset morphism
$f:\mathbf{Br}\to Q$, and hence a map $|\mathbf{Br}|\to\Gamma$. The proof of
Lemma 7.7 goes through (with ’two’ replaced by $n-1$) to show that
$|\mathbf{Br}|$ is homotopy equivalent to $\mathbf{data}_{P}$. Finally, the
proof of Theorem 7.8 goes through to show that $|\mathbf{Br}|\to\Gamma$ is a
homotopy equivalence. (One uses the version of Quillen’s Theorem A for the
realization of topological categories; see [WK, IV.3.9].) The homotopy
equivalence of the theorem follows. ∎

## References

  * [CMW] J. Cyranka, K. Mischaikow and C. Weibel, Contractibility of a persistence map preimage, J. Applied Comp. Top. 4 (2020), 509–523.
  * [C] J. Curry, The fiber of the persistence map for functions on the interval, J. Applied Comp. Top. 2 (2018), 301–321.
  * [LT] J. Leygonie and U. Tillmann, The fibre of the persistence homology map for simplicial complexes, preprint, 2021. posted at arxiv:2104.01372
  * [WK] C. Weibel, The $K$-book, Grad. Studies in Math. 145, AMS, 2013.


# A loopless and branchless $O(1)$ algorithm to generate the next Dyck word.
111This work is licensed under a Creative Commons Attribution-ShareAlike 4.0
International License.

Cassio Neri

(19 July 2014)

###### Abstract

Let `integer` be any C/C++ unsigned integer type up to $64$-bits long. Given a
Dyck word the following code returns the next Dyck word of the same size,
provided it exists.

    integer next_dyck_word(integer w) {
      integer const a = w & -w;
      integer const b = w + a;
      integer       c = w ^ b;
                    c = (c / a >> 2) + 1;
                    c = ((c * c - 1) & 0xaaaaaaaaaaaaaaaa) | b;
      return c;
    }

##  1 Introduction

A $2n$-bits Dyck word is a string containing exactly $n$ ones and $n$ zeros
and such that each of its prefix substrings contains no more zeros than ones.

Dyck words appear in a vast number of problems [1]. Consequently, generating
them has many applications. For instance, if ones and zeros are replaced with
openning and closing parentheses, then a Dyck word is a combination of $n$
properly balanced pairs of parentheses. When one denotes a move rightwards and
zero denotes a move upwards, a Dyck word represents a monotonic path along the
edges of an $n\times n$ grid that starts at the lower left corner, finishes at
the upper right corner and stays below diagonal. Figure 1 shows all $14$ such
paths on a $4\times 4$ grid.

Figure 1: Monotonic paths on a $4\times 4$ grid starting at the lower left
corner, finishing at the upper right corner and staying below diagonal. There
are 14 of them. The first path, for instance, corresponds to the Dyck word
$10101010$ and the fith one to $10111000$.

For the sake of clarity, another implementation of essentially the same
algorithm is presented. This one works on strings of two different arbitrarily
chosen symbols (e.g., opening and closing parentheses). Contrarily to the
implementation in the abstract, the second one has explicit loops and branches
and has $O(n)$ time complexity.

The apparent contradiction between being two implementations of “essentially
the same” algorithm but one being loopless, brancheless and $O(1)$ and the
other having loops, branches and being $O(n)$ can be explanained as follows.

To perform bitwise and arithmetic operations the hardware somehow “runs” loops
on its transistors but, as far as I understand, for the sake of software
complexity, these operations are considered as being loopless, branchless and
$O(1)$. In that sense we can categorize the algorithm above as loopless,
branchless and $O(1)$. The second implementation (through software code)
simply makes explicit some loops and branches “ran” by the hardware when the
first implementation is executed.

Both implementations are $O(1)$ in space.

Disclaimer: I am not a Computer Scientist and I am not aware of the state of
the art. I do not claim the algorithm above has not been discovered/invented
before but I believe there is a strict positive probability that it has not. I
have performed a not very thorought search on the net and I have failed to
find anything similar. The closest I know is the Gosper’s hack [2] which, I
must say, served as inspiration for the design of the algorithm above.
Furthermore, the algorithm above borrows its first two lines from Gosper’s
hack.

##  2 Definitions

Let $n\in\mathbb{N}$ and $B=\\{1,0\\}$. A $2n$-bits word is an element
$w=(w_{1},...,w_{2n})$ of $B^{2n}$. Throughout $n$ is fixed and, unless
necessary, we omit the $2n$ from notation. Also, we most often drop
parentheses and commas as well. (For instance, $(1,0,1,0,1,0,1,0)$ becomes
$10101010$.) Finally, by abuse of notation, we identify $w=(w_{1},...,w_{2n})$
with the number whose binary expansion is $w$. More precisely, with

$\sum_{i=1}^{2n}w_{i}2^{2n-i}.$

Thanks to this identification we can order words, talk about minimum, maximum,
etc.

For $w\in B^{2n}$ and $i\in\\{1,...,2n\\}$ we define

$\displaystyle N_{1}(w,i)$ $\displaystyle:=\\#\\{j\leq i\ ;\ w_{j}=1\\},$
$\displaystyle N_{0}(w,i)$ $\displaystyle:=\\#\\{j\leq i\ ;\ w_{j}=0\\}.$

In plain English, $N_{1}(w,i)$ is the number of ones in $w$ appearing before
or at $i$-th position. Similarly, $N_{0}$ counts the number of zeros before or
at position $i$.

We say that $w\in B^{2n}$ is a Dyck word if

$N_{1}(w,i)\geq N_{0}(w,i)\quad\forall i\in\\{1,...,2n\\},$ (1)

with equality holding for $i=2n$, that is,

$N_{1}(w,2n)=N_{1}(w,2n)=n.$ (2)

In plain English, before or at the $i$-th position, the number of ones must be
no lesser than the number of zeros. In adition the total numbers of ones and
zeros match.

For the mathematically trained eye, property (1) becomes easier to spot222At
least for small values of $n$ or not so small if you are a Lisp programmer.
when ones and zeros are replaced, respectively, with openning and closing
parentheses. In this case, the Dyck word contains $n$ pairs of correctly
matched open and close parentheses. For instance, $10101010$ becomes ()()()()
and $10111000$ becomes ()((())).

##  3 The minimum and the maximum Dyck word

The algorithm in the abstract generates the succesor of the given Dyck word.
Therefore, to kick off and stop the generation of all words, we need to know
the minimum and maximum Dyck word. (Recall that word size is fixed and
“minimum” and “maximum” refer to the order of integer numbers.)

We claim that the minimum Dyck word is

$\breve{w}:=\underbrace{10\cdots 10}_{n\text{ pairs}}$

(or $()\cdots()$ in the parenthetical representation). More precisely,
$\breve{w}=(\breve{w}_{1},...,\breve{w}_{2n})\in B^{2n}$ is given by
$\breve{w}_{i}=1$, if $i$ is odd, and $\breve{w}_{i}=0$, if $i$ is even.

Before proving our claim, we compute $\breve{w}$:

$\displaystyle\breve{w}$ $\displaystyle=2^{2n-1}+2^{2n-3}+\cdots+2^{3}+2^{1}$
$\displaystyle=2\cdot 2^{2n-2}+2\cdot 2^{2n-4}+\cdots+2\cdot 2^{2}+2\cdot
2^{0}$ $\displaystyle=2\cdot 4^{n-1}+2\cdot 4^{n-2}+\cdots+2\cdot 4+2\cdot
4^{0}=2\sum_{i=0}^{n-1}4^{i}=\frac{2}{3}(4^{n}-1).$

Calculating this number on real computers needs care to avoid overflow. For
instance, if $n=32$ then $4^{n}=4^{32}=2^{64}$ which is one more than the
maximum natural number representable by a $64$-bits unsigned integer type. In
practice, however, this is a “minor” issue because generating all $64$-bits
Dyck words would take “forever” given that the number of $2n$-bits Dyck words
grows factorially [1] with $n$.

We shall now prove that $\breve{w}$ is the minimum Dyck word. Suppose by
contradiction that there’s a Dyck word $w=(w_{1},...,w_{2n})$ such that
$w<\breve{w}$. In particular, $w\neq\breve{w}$ and let $i$ be the minimum
index such that $w_{i}\neq\breve{w}_{i}$. Since $w<\breve{w}$, we have
$w_{i}=0$ and $\breve{w}_{i}=1$. It follows that $i$ is odd. By construction
of $\breve{w}$, $N_{1}(\breve{w},i-1)=N_{0}(\breve{w},i-1)$ because $i-1$ is
even. The same holds for $w$ because it shares the first $i-1$ bits with
$\breve{w}$. Now, $w_{i}=0$ and thus $N_{0}(w,i)=N_{0}(w,i-1)+1$ and
$N_{1}(w,i)=N_{1}(w,i-1)$ which yields $N_{0}(w,i)=N_{1}(w,i)+1$,
contradicting (1).

Its much easier to see that the maximum Dyck word is

$\hat{w}:=\underbrace{1\cdots 1}_{n\text{ times}}\ \underbrace{0\cdots
0}_{n\text{ times}},$

which values $2^{2n}-2^{n}$.

##  4 The next Dyck word

Let $w=(w_{1},...,w_{2n})$ be a Dyck word. In this section we characterize the
Dyck word that succeeds $w$, that is, the smallest Dyck word which is greater
than $w$.

Assuming that $w\neq\hat{w}$, i.e., $w$ is not the maximum Dyck word, there
exists at least one index $i\in\\{1,...,2n\\}$ such that $w_{i}=0$ and
$w_{i+1}=1$. Let $k$ be the maximum of such indices. Since a Dyck word cannot
start with a zero or finish with a one, we have $1<k<2n$. Then, after position
$k$ there is no bit zero followed by a bit one. More precisely, there’s a
(possiblye empty) sequence of ones followed by a sequence of zeros up to the
end. Hence, $w$ has this form:

$w=(\underbrace{w_{1},...,w_{k-1}}_{\text{prefix}},\underbrace{0}_{w_{k}},\underbrace{1}_{w_{k+1}},\underbrace{1,...,1}_{x\text{
times}},\underbrace{0,...,0}_{y\text{ times}}),$

with $x\geq 0$ and $y>0$. We shall prove that the successor $\tilde{w}$ of $w$
has this form:

$\tilde{w}=(\underbrace{w_{1},...,w_{k-1}}_{\text{prefix}},\underbrace{1}_{\tilde{w}_{k}},\underbrace{0}_{\tilde{w}_{k+1}},\underbrace{0,...,0}_{y-x\text{
times}},\underbrace{1,0,...,1,0}_{x\text{ pairs of 1, 0}}).$

Notice that the prefixes of $w$ and $\tilde{w}$ are the same.

First we shal show that $\tilde{w}$ is well defined, that is, $y-x\geq 0$; the
size of $\tilde{w}$ is $2n$; and $\tilde{w}$ verifies the properties (1) and
(2).

The total number of ones in $w$ is $N_{1}(w,k-1)+1+x$ and the total number of
zeros is $N_{0}(w,k-1)+1+y$. Since $w$ is a Dyck word, these numbers match and
we obtain $N_{1}(w,k-1)+1+x=N_{0}(w,k-1)+1+y$. Hence,

$N_{1}(w,k-1)+1=N_{0}(w,k-1)+1+y-x\Longrightarrow
y-x=N_{1}(w,k-1)-N_{0}(w,k-1).$ (3)

Again, because $w$ is a Dyck word, $N_{1}(w,k-1)-N_{0}(w,k-1)$ is positive and
so is $y-x$.

The last two segments of $w$ have total size $x+y$ and the last two segments
of $\tilde{w}$ have total size $y-x+2x=x+y$. Hence $\tilde{w}$ is also
$2n$-bits long and $k+1+y-x=2(n-x)$.

Because of the common prefix with $w$, $\tilde{w}$ verifies property (1) for
any $i<k-1$. Obviously, it also verifies (1) for $i=k$ ($\tilde{w}$ gets an
extra $1$).

Notice that for any $i\in\\{k+1,...,2(n-x)\\}$, $\tilde{w}_{i}=0$. Hence, if
$\tilde{w}$ fails to verify (1) for any $i$ in this set of indices, then it
fails to verify (1) for $i=2(n-x)$. However,
$N_{1}(\tilde{w},2(n-x))=N_{1}(w,k-1)+1$ and
$N_{0}(\tilde{w},2(n-x))=N_{0}(w,k-1)+1+y-x$ and from (3) we obtain that these
numbers are equal. This proves that (1) holds for $i\leq 2(n-x)$. Furthermore,
we have proven that $N_{1}(\tilde{w},2(n-x))=N_{0}(\tilde{w},2(n-x))$.

From the $2(n-x)$-th bit onwards, the sequence is alternating and it follows
that

$\tilde{w}_{i}=0\quad\text{and}\quad
N_{1}(\tilde{w},i)=N_{0}(\tilde{w},i),\quad\forall i\geq 2(n-x)\text{ that is
even}.$ (4)

To prove that $\tilde{w}$ is the smallest Dyck word which is greater than $w$,
assume there’s another Dyck word $v=(v_{1},...,v_{2n})$ such that
$w<v<\tilde{w}$. Well, obviously, $v$ must have the same prefix as $w$ and
$\tilde{w}$. What about $v_{k}$? It’s either zero or one and we slipt in two
cases.

If $v_{k}=0=w_{k}$ then, because $w<v$ and $w_{i}=1$ for all
$i\in\\{k+1,...,k+1+x\\}$, the common part between $v$ and $w$ must span up to
index $k+1+x$. For $i>k+1+x$, $w_{i}=0$ and for $w<v$ to hold, at least one of
the last $y$ bits of $v$ must be one. Then the number of ones in $v$ is
greater than the number of ones in $w$ which violates the fact that any Dyck
word has exactly $n$ ones.

Similarly, if $v_{k}=1=\tilde{w}_{k}$, then because $v<\tilde{w}$ and
$\tilde{w}_{i}=0$ for $i\in\\{k+1,...,2(n-x)\\}$ the common part between $v$
and $\tilde{w}$ must span up to index $2(n-x)$. But, since $v\neq\tilde{w}$,
there exists $i>2(n-x)$ such that $v_{j}\neq\tilde{w}_{j}$. Let $i$ be the
minimum of such indices. For $v<\tilde{w}$ to hold, it is necessary that
$v_{i}=0$ and $\tilde{w}_{i}=1$. From (4) it follows that $i$ is odd and
$i-1\geq 2(n-x)$ is even. Again from (4) we obtain
$N_{1}(\tilde{w},i-1)=N_{0}(\tilde{w},i-1)$ and the same holds for $v$ thanks
to its common part with $\tilde{w}$. But $v_{i}=0$ and thus
$N_{1}(v,i)=N_{1}(v,i-1)$ and $N_{0}(v,i)=N_{0}(1,i-1)+1=N_{1}(v,i-1)+1$ which
violates (1).

##  5 Two implementations

The following C++333 The code is available at
http://github.com/cassioneri/Dyck.  function implements the algorithm
presented in the previous section. It does not allocate memory for the output
and, instead, performs the manipulations in-place. It makes no use of helper
containers and, therefore, it’s $O(1)$ on space.

The algorithm scans the word backwards up to a certain point. Then it advances
forward changing the bits up to the rightmost. Hence, in the worse case, the
program scans the whole word twice implying complexity $O(n)$ on time.

The function takes a Dyck word `w` made of `one`s and `zero`s (provided as
arguments) and transforms it into the next Dyck word, if it exists, otherwise,
it clears the word. The behaviour is undefined if `w` is not a Dyck word of
`one`s and `zero`s.

    void next_dyck_word(std::string& w, char const one, char const zero) {

      unsigned const m = w.size() - 1;
      unsigned       y = 0;
      unsigned       x = 0;

      for (unsigned i = m; i > 0; --i) {

        if (w[i] == zero)
          ++y; // Counter for trailing zeros.

        else if (w[i - 1] == zero) {

          // Found greatest i such that w[i] = zero and w[i + 1] = one.

          // Change these two chars.
          w[i - 1] = one;
          w[  i  ] = zero;

          // Overwrite the following next y - x chars to zero.
          for (y = y - x; y != 0; --y)
            w[++i] = zero;

          // Overwrite the remaining chars with alternating ones and zeros.
          while (i < m) {
            w[++i] = one;
            w[++i] = zero;
          }
          return;
        }

        else
          ++x; // Counter for ones that precede the trailing zeros.
      }
      w.clear(); // Failed to produce a Dyck word, then clear w.
    }

We shall consider now the short implementation shown in the abstract.
Similarly to the longer implementation, the short one assumes that the input
is a Dyck word. If it is not, then this is a pre-condition violation which
yields undefined behaviour. In addition (and opposite to the implementation
above), another pre-condition is that the input is not the maximum Dyck word
of its size. Failing to verify this condition, again, produces undefined
behaviour.

For easy of reference (and because it is very short) we trascript the
algorithm here.

    integer next_dyck_word(integer w) {
      integer const a = w & -w;
      integer const b = w + a;
      integer       c = w ^ b;
                    c = (c / a >> 2) + 1;
                    c = ((c * c - 1) & 0xaaaaaaaaaaaaaaaa) | b;
      return c;
    }

The abstract says that `integer` is a C/C++ unsigned integer type and the
first line in the function’s body takes the opposite of `w`! This is intended
and works as expected on C and C++ conforming implementations because on these
systems unsigned integer types have $2^{N}$-modular arithmetics, where $N$ is
the size in bits of the integer type.

Other programming languages might have different integer types and, at this
point, it is useful to list the properties the type must verify for the
algorithm to work.

The first rule is obvious but worth saying: the type must implement the
usual444For some definition of usual (e.g. two’s complement).  binary
representation of integer numbers. In particular, all values in the range
$[0,2^{N}-1[$ are representable.

$2^{N}$-modular arithmetics is sufficient but not necessary and only the
opposite of `w` must be as per $2^{N}$-modular arithmetics (simply put the
opposite of $w$ is $2^{N}-w$). For the other operations, usual arithmetic
rules are enough because the (mathematical) results of additions,
subtractions, multiplications and divisions stay in the $[0,2^{N}-1[$ range.
Moreover, `a` is a divisor of `c` (see below) and, therefore, no truncation or
division by zero occurs.

We assume usual semantics also for the bitwise operators `&`, `^`, and `|`.
Finally, the right shift rotation inserts zeros in the gaps on the left but
if, this is not the case, we can replace the right shift of two bits by a
division by four, provided that the division truncates the result.

The pleasure of verifying the details that the arithmetic and bitwise
operations above reproduce the construction explained in previous section is
left to the reader. I shall provide an overall picture though.

Let $\tilde{k}$, $x$, $y$ and $\tilde{w}$ be as in the previous section.

The expression `w & -w`, assigned to `a`, yields a number whose bits are all
zero but the one located at position $k+1+x$. The result of `w + a`, assigned
to `b`, is a number that matches $\tilde{w}$ up to position $k+1+y-x=2(n-x)$
and have only zeros afterwards. Hence, the first two lines do almost
everything. The following three fill up the last $2x$ positions with the
sequence of ones and zeros.

The first value assigned to `c` is a number with all bits zero but $x+2$ of
them which form a contiguous sequence finishing at position $k+1+x$. Recall
that at this position lies the only non null bit of `a`. Hence, `c / a` has
the effect of moving the sequence of $x+2$ ones in `c` all the way up to the
right. Shifting $2$ extra bits produces a number with all its $x$ least
significant bits set to one, that is, $2^{x}-1$. After the addition to $1$,
`c` gets the value $2^{x}$. Squaring produces $2^{2x}$ and decrementing yields
$2^{2x}-1$ which is a mask for the $2x$ rightmost bits.

Now the magic number comes in (at this point, you have probably guessed what
this is). It’s the $64$-bits number whose binary expansion is an alternating
sequence of ones and zeros or, in other terms, it’s the minimum $64$-bits Dyck
word.

Applying operator `&` to the mask and the magic number produces the $2x$-long
sequence of ones and zeros needed to fill the gap in `b`. The operator `|`
completes the task.

##  6 Acknowledgements

I thank my friend Prof. Lorenz Schneider who introduced me to the Gosper’s
hack about three years ago. I am also grateful towards mosh111, whoever he/she
is, who introduced me to the problem of Dyck word generation through his/her
post in [3] 3 days ago.

## References

  * [1] Wikipedia, Catalan numbers, http://en.wikipedia.org/wiki/Catalan_number.
  * [2] Wikipedia, Combinatorial number system, http://en.wikipedia.org/wiki/Combinatorial_number_system.
  * [3] CareerCup, Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n-pairs of parentheses, http://www.careercup.com/question?id=4815516967370752.


# Science Communications for Explainable Artificial Intelligence

Simon Hudson1111Contact Author Matija Franklin2
1BottoDAO
2University College London
<EMAIL_ADDRESS>
###### Abstract

Artificial Intelligence (AI) has a communication problem. XAI methods have
been used to make AI more understandable and helped resolve some of the
transparency issues that inhibit AI’s broader usability. However, user
evaluation studies reveal that the often numerical explanations provided by
XAI methods have not always been effective for many types of users of AI
systems. This article aims to adapt the major communications models from
Science Communications into a framework for practitioners to understand,
influence, and integrate the context of audiences both for their
communications supporting AI literacy in the public and in designing XAI
systems that are more adaptive to different users.

##  1 Intro

Artificial Intelligence (AI) is increasingly implemented in software products
employed by users with a wide variety of backgrounds and competencies. As a
new technology, its effective use depends on a great amount of effort to
educate users in a way that enables them to adapt the tool to their needs.
Making use of AI is made more difficult due to a lack of transparency Lawrence
(2017), and hoping black boxes will align with our human goals is not a good
alternative Gabriel (2020). To ensure that humans have effective oversight
over AI agents, Explainable Artificial Intelligence (XAI) techniques have been
developed to help users make sense of an AI’s decisions and predictions.

However, XAI models provide primarily numerical explanations favored by those
with numerical backgrounds Ehsan et al. (2021). For example, SHapley Additive
exPlanations (SHAP) - a method for explaining individual AI model decisions by
computing the contribution of each variable to the decision - can lead to
information overload for lay users Ferguson et al. (2022). The same research
found that simply written messages that provide a list of factors that were
considered by the AI model increased trust and understanding. There is a
dilemma where the SHAP model objectively provided more information, but a
written message provided as an alternative was perceived as more
understandable and trustworthy.

It appears that AI has a communication problem. There is scarce evidence for
what explanation should be given to a certain individual for a specific task
Franklin (2022), and therefore it is not clear how to optimize the
distribution of XAI models Franklin and Lagnado (2022). We argue that XAI, and
the AI field more broadly, can benefit from the Science Communications
(SciComms) field to better integrate missing user context. SciComms is the
practice of communicating scientific information to the public in an
accessible and engaging way. It involves researching, writing, and editing
scientific content, creating visuals, and using various digital and
traditional communication tools. The strong public discourse around AI’s
impacts sparked by Chat-GPT calls for greater use of practices developed in
the SciComms field to help build AI literacy; generative text models also
present an opportunity to integrate the SciComms approaches into AI interfaces
directly to improve their adaptability, and usefulness, to different
audiences.

##  2 AI’s Communication Challenge

Enabling users to effectively make use of AI has largely been treated as an AI
literacy problem: users having sufficient understanding of the technology’s
functioning in order to ”critically evaluate AI technologies; communicate and
collaborate effectively with AI; and use AI as a tool online, at home, and in
the workplace Long and Magerko (2020).” Treatments have followed a
communication model in SciComms referred to as the ”information-deficit
model”. This model assumes what users are missing are facts about a given
field of science or technology, and addresses that gap through top-down
dissemination of information. The information deficit model is typically a
top-down, one-way communication approach that simply relies on simply
disseminating the knowledge of experts. Even if the ideas are simplified, they
tend to ignore the individual contexts and local knowledge of users and
instead favor a one-size-fits-all approach. These efforts tend to fail in
impacting the overall literacy of a field due to not adapting to the
audience’s various perspectives or being made relevant in a way they can find
useful in their daily lives Miller (2001).

SciComms encompasses the ”skills, media, activities, and dialogue to produce”
robust engagement with science and technology in the public Burns et al.
(2003). For a technology like AI, SciComms is a critical practice in preparing
the public for its effective use. The SciComms field has been evolving out of
the “information deficit model” that pins mistrust in science on science
illiteracy Nisbet and Scheufele (2009). Meta-analysis of surveys on the public
understanding of science taken around the world since 1989 has shown that
trust in science varies even as average science literacy stays the same Allum
et al. (2008). Other contexts Nisbet and Goidel (2007), in particular,
historical experiences with science institutions Wynne (1992), are much
stronger predictors. Understanding the context of past influential
experiences, as well as the context of the present narratives and issues
around technology, helps determine the frames most effective at supporting
productive discussion in the public Nisbet and Scheufele (2009). These
contexts are a moving target as AI makes more of an impact on mainstream
culture due to the release of widely publicized products like Chat-GPT.

Other models in SciComms have been growing in favor, including the contextual
model, lay expertise model, and the participatory model Brossard and
Lewenstein (2009). The contextual model emphasizes adapting communications to
different audiences’ diverse contexts that can include a wide variety of
factors: such as attitudes, beliefs, the task being executed, the domain it is
performed in, and the current circumstance of a user. The lay expertise model
gives additional credence to local knowledge, such as cultural or domain
expertise that the science and technology experts do not have access to; it
balances the authority of the science and technology expert with that of the
end-user and knowledge of their own needs. The participatory model emphasizes
the key role of holders of local knowledge in forming goals for technology
design and even the policy regulating it. The deficit model has not been
entirely discounted, rather the SciComms field has pursued balancing it with
the strengths of these other models.

Resolving AI’s communication challenge thus should include the goal of better
understanding different stakeholders by exploring the contexts most relevant
to them so that they can give input they believe is valuable. Further, AI
outputs themselves are a kind of scientific communication of the data science
the models employ to make a prediction, and XAI would also benefit from
applying these methods directly in an AI interface’s presentation of outputs.
Recent advancements in generative AI, as they apply to XAI, provide a valuable
opportunity to integrate these models for SciComms into the design of adaptive
explainable AI to address the moving target of individual user contexts.

Taking this view, AI’s communication challenge can be divided into two
categories: creator and user. The user challenge is in preparing users’
expectations of these interfaces via AI literacy efforts - communicating the
dynamics and implications of algorithms so that people can raise their ability
to think critically about the data generated and outputs provided by
algorithms. The first creator challenge is in designing systems that are well
adapted for their intended audience, or, if for general use, can be adaptable
to a wide variety of users. The second creator challenge is in developing
systems that are capable of learning and adapting to an individual user’s
context by taking into consideration an individual’s background, the task they
are performing, the domain, the ordering of tasks, stated preferences etc. For
example, explaining an AI’s decision to a junior educator may be more detailed
and authoritative versus a senior one who may receive only more nuanced
explanations. This is of course complicated by other contexts, like their
particular AI literacy, experience with the machine, or cultural factors.

We propose a framework for addressing AI’s communication challenge through
three stages of work: Understanding Context, Influencing Context, and
Integrating Context.

##  3 Understanding Context

Understanding Context involves gathering and interpreting knowledge of the
target audience, their needs, values, and interests. It means understanding
the user’s background, their level of familiarity with AI concepts, their
cognitive style, and their information needs. A nationally representative
survey of 2,000 American adults in 2019 found that most people use AI, but
claim that they don’t and won’t in the future Zhang and Dafoe (2019).
Presenting AI as a consumer product (e.g., Netflix recommender system) versus
as an intelligent agent influences people’s receptiveness to it. On the other
hand, giving AI agentic properties can obscure the human role in AI systems
Epstein et al. (2020). It is therefore important to research how different
contextual factors can set reasonable expectations of the technology and the
public’s own sense of agency in influencing its development Bao et al. (2022).

Methods used in SciComms for understanding context involve audience research
(i.e., understanding knowledge, attitudes, and interests), psychographics
(i.e., understanding psychological attributes), demographics, narrative (i.e.,
understanding context through users’ stories), and user testing (i.e.,
empirical research on what types of explanations work best for different types
of users) van Atteveldt and Peng (2018). In addition, a growing set of
computational approaches for measuring audience reception of communications
will be helpful here August et al. (2020).

An interesting case study on how context can be understood, and how it
influences the perception of emerging technologies comes from research on
self-driving vehicles (SDVs). One notable factor is the lack of information
provided by SDVs Büscher et al. (2009). A factor that may also reduce trust in
SDVs is the widespread data collection that is necessary for a connected
network of SDVs to work efficiently Büscher et al. (2009), however recent
evidence suggests that many appear willing to share data if it improves travel
experience Wockatz and Schartau (2015). Further, individuals prefer SDVs whose
algorithms are set in a way so that they protect their passengers at all
costs, yet they would prefer if others bought vehicles that are programmed to
sacrifice passengers for the benefit of the majority (e.g., saving a higher
number of pedestrians; Bonnefon et al. (2016)). More broadly, people seem to
be concerned about hacking, misuse, legal issues, and safety Kyriakidis et al.
(2015). Although it is evident that a car’s ethical behaviour is outside the
scope of SciComms, there is a clear opportunity to provide more information,
and to be more transparent about what type of data collection is necessary for
a safer and improved travel experience. Further, it can help inform which
context to prioritize when determining a communication strategy.

SDVs also give insights into how sociodemographics are relevant to public
attitudes. Studies have identified that younger travelers Ruggeri et al.
(2018) and those living in large cities Cohen et al. (2017) are more willing
to adopt SDVs. Further, people in China and India had more positive opinions
about SDVs than people in the US, UK, and Australia Schoettle and Sivak
(2014). Identifying the sociodemographic divides in attitude is indicative of
the forthcoming potential divides in the challenges SciComms about AI will
face.

Finally, Ruggeri et al. (2018) found that attitudes towards SDVs reflect the
theoretical curve assumed in Diffusion of Innovations Theory Rogers et al.
(2014). SDVs, like other emerging technologies, will first be used by early
adopters, successively followed by second-wave adopters, mainstream users,
late adopters, and avoiders. The patterns exist within and between every age
breakdown, however, the older participants were more likely to resist SDVs.
Younger generations, considered digital natives, are more trustworthy of
intelligent systems and algorithmic decision-making; thus, as a group, they
skew towards early adoption. SciComms initiatives, thus, will have different
challenges for each group of adopters. The movement of users between these
categories as the technology spreads will also add value to strategies that
can be adaptive to shifting contexts.

We are considering a broad definition of context, involving any variety of
factors that can influence how information is received, interpreted, and
integrated or discarded. Put simply, it is considering the audience’s diverse
needs in order to reach a communication goal and goes beyond a communicator
only considering the information that they want to be known by the audience.
To that end, considering different frameworks for understanding relevant
context can be useful in identifying the priority factors to consider in the
basic design of an XAI system. One approach to understanding the context in
relation to XAI comes from Franklin and Lagnado (2022) who argue that people’s
reaction to explanations can be evaluated by measuring their mental models,
probability estimates, trust, knowledge, and performance. Here, mental models
are representations of how people understand systems. Probability estimates
are the probability of future events occurring. Trust is a multidimensional
concept predictive of whether people choose to use AI. Knowledge can be
procedural - relating to changes in abilities - or semantic - relating to
changes in factual knowledge. Finally, people’s performance on the task an AI
is assisting them with will change due to the provided XAI explanations. The
approach can identify what factors are the main barriers to communication.
Some users may not trust the AI in the first place, while others may not have
the procedural knowledge to use the tool.

##  4 Influencing Context

Influencing Context involves shaping communication about AI (the user
challenge) as well as the baseline design of interface features to address the
specific needs and concerns of a target group (the first creator challenge).
This means not only delivering explanations that the audience can understand
but also considering what issues and consequences might be most relevant to
them.

”Framing” is a key practice used in SciComms to influence public reception of
scientific and technological topics. A frame is a storyline selected to help
simply convey complex topics. Different frames prioritize different issues and
consequences, guiding attention to what the communicator wants an audience to
focus on out of the many topics within a complex set of information Nisbet and
Scheufele (2009). However, it is important SciComms practitioners make sure to
avoid emphasis framing \- the phenomenon in which the bias of presented
information also biases judgments of that information Druckman (2001). Such
framing can be used to influence a person’s perceptions of an issue, either
positively or negatively. For example, trust in the authenticity of AI work
can be increased by emphasizing human involvement in their creation or
training processes Jago (2019). The goal of framing should be to draw their
attention to the most relevant aspects of their lives so that they can
productively engage with the ideas, without biasing the judgments they go on
to make.

Picking which aspects of technology to focus on can influence whether there is
any effect on public perception and understanding at all. Studies have found
that for emerging technologies, such as carbon nanotubes and genetically
modified foods, factual information about the technologies has a lower impact
on people’s reception of such technologies than background factors such as
people’s values Druckman and Bolsen (2011). The same study found that once
people form their opinions, they tend to view factual information about a
technology’s features through motivated reasoning \- where they use this
information to reaffirm their opinions. Even if someone wanted to emphasize
features that they themselves see as positive, a receiver with a negative
opinion may not be influenced at all. Framing that first addresses the
storylines behind the beliefs may be a more effective approach.

Another approach to influencing context is message design. Message design
involves designing the message to be engaging, understandable, and memorable
Livingstone (2019). This can involve visuals, analogies, or narratives to make
explanations more engaging, or repetition and reinforcement to make messages
more memorable Nisbet and Scheufele (2009) Audience research approaches, such
as focus groups, can help inform and test narratives needed to reach specific
groups Krause et al. (2019). Gaining such an understanding will also inform
the development of AI technologies as they will emphasize user needs Ruzi et
al. (2021). For example, when individuals are given a certain amount of
control over intelligent systems, they are more likely to use them Dietvorst
et al. (2018).

While the SciComms field has discounted the deficit model, it has not
completely thrown it out. It is still important to provide groups with details
about science and technology. Public stakeholders respond strongly to being
provided information on the technology’s functioning as well as broader
implications in society Besley et al. (2008). Integrating with the other
SciComms models is a matter of incorporating feedback and adjusting the
message. This involves monitoring the audience’s reaction to the communication
and adjusting it as needed. For example, if the audience is not understanding
the explanation, understanding whether it comes from a knowledge gap or a
communications gap is important. Further, SciComms can utilize issue
prioritization - identifying the most important issues and consequences for
each group and focusing the communication on these issues.

SciComms can also influence AI literacy through a participatory approach.
Participatory approaches include dialogues and even giving stakeholders access
to decision-making discussions on design and research priorities. This not
only helps ensure a deep integration of context in the research and
development of the technology, but the process also better equips stakeholder
groups to engage with and critique the efforts of the field Boyd and Crawford
(2012) and better present perspectives that can actually be taken up in
development Franklin et al. (2022a). It is important that these “bottom-up”
strategies happen early and often, not only so that the public’s views, local
knowledge, and lay expertise can be incorporated, but so that the public feels
a part of the process, and consensus and reasonable expectations can be built
before deployment Etzioni and Etzioni (2017). This can also help supersede
unhelpful or bad-faith framing. This practice has begun to a degree RS (2020),
but we would emphasize that collective dialogues are as much a part of
influencing context as they are about understanding context Long and Magerko
(2020).

Indeed, recent approaches have looked at how explanations provided by XAI can
either nudge behaviour directly or boost people’s capability which in turn
promotes better AI use Franklin (2022). From this perspective, local feature
importance explanations and concept-based explications are harmonious to
disclosure nudges that give context-dependant information, and global feature
importance explanations and counterfactual explanations are congruous to boost
capability. A further inquiry would allow for a more optimal distribution and
selection of XAI methods and corresponding SciComms techniques. Translational
exploration utilizing already current understandings from AI, Behavioural
Science, and Human-Computer Interaction would be advantageous.

SciComms can help in the development of better human-in-the-loop (HITL)
architectures, where ML systems communicate to humans via XAI explanations,
and humans give feedback to update the model’s performance Bai et al. (2022).
HITL ML architectures are systems in which humans and machines collaborate to
create solutions Zanzotto (2019), using feedback loops where humans and
machines interact and learn from each other Mosqueira-Rey et al. (2022). This
type of architecture is particularly useful in cases where the information and
data available are not enough to provide an accurate solution. By combining
human insight with computer algorithms and datasets, a more accurate and
comprehensive solution can be created.

##  5 Integrating Context

Integrating Context focuses on creating an interactive and adaptive
communication interface that allows for a two-way dialogue between AI and
people. The goal here is to establish a feedback loop where the AI learns from
user interactions and modifies its explanations accordingly employing SciComms
models, and where the user learns from the AI and adjusts their expectations
and understanding of AI behaviour. Such communication is necessary to maintain
human agency, and integrating techniques for context discovery and adaption in
AI interfaces is an important topic of research. In other words, this is about
extending the first two stages of Understanding and Influencing Context into
an adaptive interface. To this end, computational linguistics is beginning to
use science communications principles in conversational interface design that
considers sensitive vocabulary when explaining a scientific concept so as to
not run into a bias of a user, or to create a harmful one Kocielnik (2021).
Generative AI offers a large opportunity to do this adaption for the wide
variety of context factors needed to consider in a globally distributed
technology August et al. (2020).

The SciComms field has made strides to update itself to the modern needs and
media paradigms and incorporated more computational methods that would better
enable application to the fast-moving and widely distributed field of AI
Freiling et al. (2021).

SciComms calls two-way dialogue dialogic communication. This means the AI
would not just provide explanations, but also solicit feedback, ask clarifying
questions, and adapt its responses based on user inputs. A case study for the
benefits of two-way communication comes from preferences inference and
elicitation. Russell (2019) has argued that one way forward is to align AI to
human preferences and that they can be best inferred from human behaviour.
This perspective, however, ignores the fact that preference and behaviour are
often influenced by the same factors Franklin et al. (2022b), and that
preference and behaviour have a bidirectional causal relationship
ashton2022problem. As a result, we might want to design systems that attempt
to elicit preferences or meta-preferences more directly by prompting users for
information Ashton and Franklin (2022).

Another SciComms approach that may be relevant is adaptive communication \- AI
dynamically adjusts its explanations based on the user’s feedback. For
example, if the user indicates they didn’t understand an explanation, the AI
could provide a simpler explanation or use a different analogy. The approach
can be paired with an iterative design for XAI models - continuously refining
the AI-user interface based on user feedback and testing results. This would
result in a cyclical process of design, testing, feedback, and redesign, aimed
at continuously improving the communication between the AI and the user.

One risk here is that a battery of questions probing for user info may result
in disengagement of the user. Providing explanatory features that prompt more
questioning from the user may be beneficial here. In a generative interface,
for example, showing the hidden prompts that guide its answer, showing
sources, or indicating the effect of increasing the temperature on the
likelihood of inaccurate hallucinations can help the user to discern how an
output was reached and ask follow-up questions that imply their context.
Coupled with a simple suggestion to question the output and provide more
context could prompt the user to offer more useful variables for the AI agent
to adapt to. Larger token sizes of AI models would also increase the memory of
these systems to learn and adapt to their users over time and tune them to
their needs.

Other risks included an AI model getting stuck in a particular tuning to a
user and struggling to update to a user making significant changes in attitude
or experiencing a large change in context. The user may also become
overconfident in the AI system and stop questioning the outputs. For both user
and machine it is ideal to maintain a healthy level of communicated
uncertainty, and defining parameters for measuring the success of these
systems will be a critical area of research.

##  6 Conclusion

AI has a communications challenge. To create human-centric AI, it is important
that XAI is able to adapt to different users. This has often been confused
with trying to increase users’ trust in AI without understanding why they
might not trust it in the first place. SciComms is a field with rich insights
into how to understand users so as to improve public engagement and
expectations of AI systems, and its approaches could be employed to help AI
systems better adapt to their particular users.

Such integration can result in more adaptive XAI systems that mimic the way a
skillful human communicator would adapt their explanations to different
audiences in different contexts. Building systems that have that ability of
explanation adaptation is now possible, where an explanation can be completely
changed while retaining the inherent meaning. We argue that XAI needs to move
towards adaptive explainable artificial intelligence  \- a recommender system
that predicts the preferred explanations of a specific user in a particular
context.

There is a wide area of research to pursue, and we propose a study of research
gaps to identify useful areas of overlap between SciComms and XAI. To build
adaptive XAI, data would be needed on how certain people react to different
explanations while performing distinct tasks in particular contexts. There
have been recent proposals for XAI evaluation paradigms Franklin and Lagnado
(2022). Using the data collected from such paradigms in an adaptive system
would involve building a simple, interpretable model capable of recommending
the right XAI method to the right person for a given task. That data would
contain well-understood variables, so a simple model can also produce salient
explanations of its own process by default — a kind of ‘meta-interpretability’
that stops new black boxes from hindering human-AI interaction.

## References

  * Allum et al. [2008] Nick Allum, Patrick Sturgis, Dimitra Tabourazi, and Ian Brunton-Smith.  Science knowledge and attitudes across cultures: A meta-analysis.  Public understanding of science, 17(1):35–54, 2008.
  * Ashton and Franklin [2022] Hal Ashton and Matija Franklin.  Solutions to preference manipulation in recommender systems require knowledge of meta-preferences.  arXiv preprint arXiv:2209.11801, 2022.
  * August et al. [2020] Tal August, Lauren Kim, Katharina Reinecke, and Noah A Smith.  Writing strategies for science communication: Data and computational analysis.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 5327–5344, 2020.
  * Bai et al. [2022] Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  arXiv preprint arXiv:2204.05862, 2022.
  * Bao et al. [2022] Luye Bao, Nicole M Krause, Mikhaila N Calice, Dietram A Scheufele, Christopher D Wirz, Dominique Brossard, Todd P Newman, and Michael A Xenos.  Whose ai? how different publics think about ai and its social impacts.  Computers in Human Behavior, 130:107182, 2022.
  * Besley et al. [2008] John C Besley, Victoria L Kramer, Qingjiang Yao, and Chris Toumey.  Interpersonal discussion following citizen engagement about nanotechnology: What, if anything, do they say?  Science Communication, 30(2):209–235, 2008.
  * Bonnefon et al. [2016] Jean-François Bonnefon, Azim Shariff, and Iyad Rahwan.  The social dilemma of autonomous vehicles.  Science, 352(6293):1573–1576, 2016.
  * Boyd and Crawford [2012] Danah Boyd and Kate Crawford.  Critical questions for big data: Provocations for a cultural, technological, and scholarly phenomenon.  Information, communication & society, 15(5):662–679, 2012.
  * Brossard and Lewenstein [2009] Dominique Brossard and Bruce V Lewenstein.  A critical appraisal of models of public understanding of science: Using practice to inform theory.  In Communicating science, pages 25–53. Routledge, 2009.
  * Burns et al. [2003] Terry W Burns, D John O’Connor, and Susan M Stocklmayer.  Science communication: a contemporary definition.  Public understanding of science, 12(2):183–202, 2003.
  * Büscher et al. [2009] Monika Büscher, Paul Coulton, Christos Efstratiou, Hans Gellersen, Drew Hemment, Rashid Mehmood, and Daniela Sangiorgi.  Intelligent mobility systems: some socio-technical challenges and opportunities.  In International Conference on Communications Infrastructure. Systems and Applications in Europe, pages 140–152. Springer, 2009.
  * Cohen et al. [2017] Tom Cohen, Peter Jones, and Clémence Cavoli.  Social and behavioural questions associated with automated vehicles.  Scoping study by UCL Transport Institute. Final report, London: Department for Transport, 2017.
  * Dietvorst et al. [2018] Berkeley J Dietvorst, Joseph P Simmons, and Cade Massey.  Overcoming algorithm aversion: People will use imperfect algorithms if they can (even slightly) modify them.  Management Science, 64(3):1155–1170, 2018.
  * Druckman and Bolsen [2011] James N Druckman and Toby Bolsen.  Framing, motivated reasoning, and opinions about emergent technologies.  Journal of Communication, 61(4):659–688, 2011.
  * Druckman [2001] James N Druckman.  The implications of framing effects for citizen competence.  Political behavior, 23(3):225–256, 2001.
  * Ehsan et al. [2021] Upol Ehsan, Samir Passi, Q Vera Liao, Larry Chan, I Lee, Michael Muller, Mark O Riedl, et al.  The who in explainable ai: How ai background shapes perceptions of ai explanations.  arXiv preprint arXiv:2107.13509, 2021.
  * Epstein et al. [2020] Ziv Epstein, Sydney Levine, David G Rand, and Iyad Rahwan.  Who gets credit for ai-generated art?  Iscience, 23(9):101515, 2020.
  * Etzioni and Etzioni [2017] Amitai Etzioni and Oren Etzioni.  Incorporating ethics into artificial intelligence.  The Journal of Ethics, 21(4):403–418, 2017.
  * Ferguson et al. [2022] Aidah Nakakande Ferguson, Matija Franklin, and David Lagnado.  Explanations that backfire: Explainable artificial intelligence can cause information overload.  In Proceedings of the Annual Meeting of the Cognitive Science Society, volume 44, 2022.
  * Franklin and Lagnado [2022] Matija Franklin and David Lagnado.  Human-ai interaction paradigm for evaluating explainable artificial intelligence.  In International Conference on Human-Computer Interaction, pages 404–411. Springer, 2022.
  * Franklin et al. [2022a] Matija Franklin, Hal Ashton, Edmond Awad, and David Lagnado.  Causal framework of artificial autonomous agent responsibility.  In Proceedings of the 2022 AAAI/ACM Conference on AI, Ethics, and Society, pages 276–284, 2022.
  * Franklin et al. [2022b] Matija Franklin, Hal Ashton, Rebecca Gorman, and Stuart Armstrong.  Recognising the importance of preference change: A call for a coordinated multidisciplinary research effort in the age of ai.  arXiv preprint arXiv:2203.10525, 2022.
  * Franklin [2022] Matija Franklin.  The influence of explainable artificial intelligence: Nudging behaviour or boosting capability?  arXiv preprint arXiv:2210.02407, 2022.
  * Freiling et al. [2021] Isabelle Freiling, Nicole M Krause, Dietram A Scheufele, and Kaiping Chen.  The science of open (communication) science: Toward an evidence-driven understanding of quality criteria in communication research.  Journal of Communication, 71(5):686–714, 2021.
  * Gabriel [2020] Iason Gabriel.  Artificial intelligence, values, and alignment.  Minds and machines, 30(3):411–437, 2020.
  * Jago [2019] Arthur S Jago.  Algorithms and authenticity.  Academy of Management Discoveries, 5(1):38–56, 2019.
  * Kocielnik [2021] Rafal Kocielnik.  Designing Engaging Conversational Interactions for Health & Behavior Change.  University of Washington, 2021.
  * Krause et al. [2019] Nicole M Krause, Dominique Brossard, Dietram A Scheufele, Michael A Xenos, and Keith Franke.  Trends—americans’ trust in science and scientists.  Public Opinion Quarterly, 83(4):817–836, 2019.
  * Kyriakidis et al. [2015] Miltos Kyriakidis, Riender Happee, and Joost CF de Winter.  Public opinion on automated driving: Results of an international questionnaire among 5000 respondents.  Transportation research part F: traffic psychology and behaviour, 32:127–140, 2015.
  * Lawrence [2017] Neil D. Lawrence.  Living together: Mind and machine intelligence.  arXiv preprint arXiv:1705.07996, 2017.
  * Livingstone [2019] Sonia Livingstone.  Audiences in an age of datafication: Critical questions for media research.  Television & New Media, 20(2):170–183, 2019.
  * Long and Magerko [2020] Duri Long and Brian Magerko.  What is ai literacy? competencies and design considerations.  In Proceedings of the 2020 CHI conference on human factors in computing systems, pages 1–16, 2020.
  * Miller [2001] Steve Miller.  Public understanding of science at the crossroads.  Public understanding of science, 10(1):115–120, 2001.
  * Mosqueira-Rey et al. [2022] Eduardo Mosqueira-Rey, Elena Hernández-Pereira, David Alonso-Ríos, José Bobes-Bascarán, and Ángel Fernández-Leal.  Human-in-the-loop machine learning: A state of the art.  Artificial Intelligence Review, pages 1–50, 2022.
  * Nisbet and Goidel [2007] Matthew C Nisbet and Robert K Goidel.  Understanding citizen perceptions of science controversy: bridging the ethnographic—survey research divide.  Public Understanding of science, 16(4):421–440, 2007.
  * Nisbet and Scheufele [2009] Matthew C Nisbet and Dietram A Scheufele.  What’s next for science communication? promising directions and lingering distractions.  American journal of botany, 96(10):1767–1778, 2009.
  * Rogers et al. [2014] Everett M Rogers, Arvind Singhal, and Margaret M Quinlan.  Diffusion of innovations.  In An integrated approach to communication theory and research, pages 432–448. Routledge, 2014.
  * RS [2020] RS.  Communicating ai: the role of researchers in enabling public conversations about ai.  The Royal Society, 2020.
  * Ruggeri et al. [2018] Kai Ruggeri, Ondřej Kácha, Igor G Menezes, Michaela Kos, Matija Franklin, Laurie Parma, Patrick Langdon, Brian Matthews, and John Miles.  In with the new? generational differences shape population technology adoption patterns in the age of self-driving vehicles.  Journal of Engineering and Technology Management, 50:39–44, 2018\.
  * Russell [2019] Stuart Russell.  Human compatible: Artificial intelligence and the problem of control.  Penguin, 2019.
  * Ruzi et al. [2021] Selina A Ruzi, Nicole M Lee, and Adrian A Smith.  Testing how different narrative perspectives achieve communication objectives and goals in online natural science videos.  PloS one, 16(10):e0257866, 2021.
  * Schoettle and Sivak [2014] Brandon Schoettle and Michael Sivak.  Public opinion about self-driving vehicles in china, india, japan, the us, the uk, and australia.  Technical report, University of Michigan, Ann Arbor, Transportation Research Institute, 2014.
  * van Atteveldt and Peng [2018] Wouter van Atteveldt and Tai-Quan Peng.  When communication meets computation: Opportunities, challenges, and pitfalls in computational communication science.  Communication Methods and Measures, 12(2-3):81–92, 2018.
  * Wockatz and Schartau [2015] P Wockatz and P Schartau.  Traveller needs and uk capability study.  Transport Systems, 2015.
  * Wynne [1992] Brian Wynne.  Misunderstood misunderstanding: social identities and public uptake of science.  Public understanding of science, 1(3):281, 1992.
  * Zanzotto [2019] Fabio Massimo Zanzotto.  Human-in-the-loop artificial intelligence.  Journal of Artificial Intelligence Research, 64:243–252, 2019.
  * Zhang and Dafoe [2019] Baobao Zhang and Allan Dafoe.  Artificial intelligence: American attitudes and trends.  Available at SSRN 3312874, 2019.