11institutetext: Université Paris-Saclay, CNRS, Laboratoire Interdisciplinaire
des Sciences du Numérique, 91400, Orsay, France

# Sturmian and infinitely desubstitutable words accepted by an
$\omega$-automaton

Pierre Béaur 11 0000-0002-4050-7709 Benjamin Hellouin de Menibus 11
0000-0001-5194-929X

###### Abstract

Given an $\omega$-automaton and a set of substitutions, we look at which
accepted words can also be defined through these substitutions, and in
particular if there is at least one. We introduce a method using
desubstitution of $\omega$-automata to describe the structure of preimages of
accepted words under arbitrary sequences of homomorphisms: this takes the form
of a meta-$\omega$-automaton.

We decide the existence of an accepted purely substitutive word, as well as
the existence of an accepted fixed point. In the case of multiple
substitutions (non-erasing homomorphisms), we decide the existence of an
accepted infinitely desubstitutable word, with possibly some constraints on
the sequence of substitutions (_e.g._ Sturmian words or Arnoux-Rauzy words).
As an application, we decide when a set of finite words codes _e.g._ a
Sturmian word. As another application, we also show that if an
$\omega$-automaton accepts a Sturmian word, it accepts the image of the full
shift under some Sturmian morphism.

###### Keywords:

Substitutions $\omega$-automata Sturmian words decidability.

##  1 Introduction

One-dimensional symbolic dynamics is the study of infinite words and their
associated dynamical structures, and is linked with combinatorics on words.
Two classical methods to generate words are the following: on the one hand,
sofic shifts are the set of infinite walks on a labeled graph (which can be
considered as an $\omega$-automaton) [9]; on the other hand, the substitutive
approach consists in iterating a word homomorphism on an initial letter. The
latter method was introduced by Axel Thue as a way to create counterexamples
to conjectures in combinatorics on words [3].

These two constructions usually build words and languages which are of a very
different nature. On the one hand, substitutive words tend to have a self-
similar structure, and are used to generate minimal aperiodic subshifts ; on
the other hand, sofic shifts always contain ultimately periodic words and
cannot be minimal if they contain a non-periodic word. We aim at deciding when
a given $\omega$-automaton accepts a word with a given substitutive structure,
and study the properties of sets of such accepted words. Carton and Thomas
provided a method to decide this question in the case of substitutive or
morphic words on Büchi $\omega$-automata, using verification theory and
semigroups of congruence [5]. This result was partially reproved by Salo [15],
using a more combinatorial point of view. For the last 20 years, the
substitutive approach (iterating a single homomorphism) has been generalized
to the S-adic approach [6] that lets one alternate betweeen multiple
substitutions. This more general framework lets us describe other natural
classes, such as the family of Sturmian words.

In this paper, we develop a new method based on desubstitutions of
$\omega$-automata. We can express the preimages of an $\omega$-automaton by
any sequence of substitutions through a meta-$\omega$-automaton, whose
vertices are $\omega$-automata and whose edges are labeled by substitutions.
We use this meta-$\omega$-automaton to decide whether an $\omega$-automaton
accepts a purely substitutive word (giving an alternative proof of [5]), or a
fixed point of a substitution, or a morphic word, or an infinitely
desubstitutable word (by a set of substitutions). The method is flexible
enough to enforce additional constraints on the directive sequences of
substitutions, which is powerful enough for example to decide whether an
$\omega$-automaton accepts a Sturmian word. A consequence is the decidability
of whether a given set of finite words codes some Sturmian word (or from any
family of words with an $S$-adic characterization). We also describe the set
of directive sequences of words accepted by some $\omega$-automaton, which is
an $\omega$-regular set.

The meta-$\omega$-automaton also provides a more combinatorial insight on how
Sturmian words and $\omega$-regular languages interact: namely, that an
$\omega$-automaton accepts a Sturmian word if, and only if, it accepts the
image of the full shift under a Sturmian morphism.

##  2 Definitions

###  2.1 Words and $\omega$-automata

An alphabet $\mathcal{A}$ is a finite set of symbols. The set of finite words
on $\mathcal{A}$ is denoted as $\mathcal{A}^{*}$, and contains the empty word.
A (mono)infinite word is an element of $\mathcal{A}^{\mathbb{N}}$. It is usual
to write $x=x_{0}x_{1}x_{2}x_{3}\dots$ where $x_{i}=x(i)\in\mathcal{A}$. If
$x$ is a word, $|x|$ is the length of the word (if $x$ is infinite, then
$|x|=\infty$). For a word $x$ and $0\leq j\leq k<|x|$, $x_{\llbracket
j,k\rrbracket}$ is the word $x_{j}x_{j+1}x_{j+2}\dots x_{k-1}x_{k}$. We denote
$w\sqsubseteq_{p}x$ when $w$ is a prefix of $x$, that is, $w=x_{\llbracket
0,k\rrbracket}$.

It is possible to endow $\mathcal{A}^{\mathbb{N}}$ with a topology, called
_the prodiscrete topology_. The prodiscrete topology is defined by the clopen
basis $[w]_{n}=\\{x\in\mathcal{A}^{\mathbb{N}}\ |\ x_{n}x_{n+1}\dots
x_{n+|w|-1}=w\\}$ for $w\in\mathcal{A}^{\ast}$. To this topology, we can
adjunct a dynamic with the shift operator $S$:

$S:\left(\begin{array}[]{ccc}\mathcal{A}^{\mathbb{N}}&\rightarrow&\mathcal{A}^{\mathbb{N}}\\\
x=x_{0}x_{1}x_{2}x_{3}\dots&\mapsto&S(x)=x_{1}x_{2}x_{3}x_{4}\dots\end{array}\right)$

A set $X\subseteq\mathcal{A}^{\mathbb{N}}$ is called _a shift (space)_ if it
is stable by $S$ and closed for the prodiscrete topology. In particular,
$\mathcal{A}^{\mathbb{N}}$ is a shift space, called _the full shift (space)_.

We now introduce the main computational model of this paper:
$\omega$-automata.

######  Definition 1 ($\omega$-automaton)

An $\omega$-automaton $\mathfrak{A}$ is a tuple $(\mathcal{A},Q,I,T)$, where
$\mathcal{A}$ is an alphabet, $Q$ is a finite set of states, $I\subseteq Q$ is
the set of initial states, $T\subseteq Q\times\mathcal{A}\times Q$ is the set
of transitions of $\mathfrak{A}$.

We extend several classical notions from finite automata. We write transitions
as $q_{s}\xrightarrow[]{a}q_{t}\in T$.

######  Definition 2 (Computations and walks)

For $n\geq 1$ or $n=\infty$, a sequence $(q_{k})_{0\leq k\leq n}$ with
$q_{k}\in Q$ is a _walk_ in $\mathfrak{A}$ if there is $(a_{k})_{1\leq k\leq
n}\subseteq\mathcal{A}$ such that for all $0\leq k\leq n-1$,
$q_{k}\xrightarrow[]{a_{k+1}}q_{k+1}\in T$. We then write
$q_{0}\xrightarrow[]{a_{1}}q_{1}\xrightarrow[]{a_{2}}q_{2}\xrightarrow[]{a_{3}}\cdots\xrightarrow[]{a_{n}}q_{n}$.
The word $w=(a_{k})_{1\leq k\leq n}$ _labels_ the walk, and we call
_computation_ a labeled walk. If the computation begins with an initial state,
$w$ is _accepted_ by $\mathfrak{A}$.

In the literature, $\omega$-automata usually have an acceptance condition
(such as the Büchi condition [17]). In this paper, we will consider
$\omega$-automata to have the largest acceptance condition: every walk
beginning with an initial state is accepting. This is a weaker model than
Büchi $\omega$-automata.

######  Definition 3 (Language of an $\omega$-automaton)

Let $\mathfrak{A}$ be an $\omega$-automaton. The language of finite words of
$\mathfrak{A}$ is $\mathcal{L}_{F}(\mathfrak{A})=\\{w\in\mathcal{A}^{*}\ |\
w\text{ is accepted by }\mathfrak{A}\\}$. The language of infinite words of
$\mathfrak{A}$ is
$\mathcal{L}_{\infty}(\mathfrak{A}))\\{w\in\mathcal{A}^{\mathbb{N}}\ |\
w\text{ is accepted by }\mathfrak{A}\\}$. Then, the language of $\mathfrak{A}$
is
$\mathcal{L}(\mathfrak{A})=\mathcal{L}_{F}(\mathfrak{A})\cup\mathcal{L}_{\infty}(\mathfrak{A})$.

If all states of $\mathfrak{A}$ are initial ($I=Q$), its language of infinite
words is a shift, called a _sofic shift_ [9].

###  2.2 Substitutions

######  Definition 4 (Homomorphisms and substitutions)

A homomorphism is a function
$\sigma:\mathcal{A}^{\ast}\rightarrow\mathcal{A}^{\ast}$ such that
$\sigma(uv)=\sigma(u)\sigma(v)$ (concatenation) for all
$u,v\in\mathcal{A}^{\ast}$. The homomorphism $\sigma$ is extended to
$\mathcal{A}^{\mathbb{N}}\rightarrow\mathcal{A}^{\mathbb{N}}$ by
$\sigma(x_{0}x_{1}x_{2}\dots)=\sigma(x_{0})\sigma(x_{1})\sigma(x_{2})\dots$ A
substitution is a _nonerasing_ homomorphism, that is,
$\sigma(a)\neq\varepsilon$ for all letters $a\in\mathcal{A}$.

######  Definition 5 (Fixed points, purely substitutive, substitutive and
morphic words)

Let $\sigma,\tau:\mathcal{A}^{\mathbb{N}}\rightarrow\mathcal{A}^{\mathbb{N}}$
be two homomorphisms. An infinite word $x\in\mathcal{A}^{\mathbb{N}}$ is:

  * •

a _fixed point_ of $\sigma$ if $\sigma(x)=x$;

  * •

a _purely substitutive word_ generated by $\sigma$ if there is a letter
$a\in\mathcal{A}$ such that $x=\lim\limits_{n\rightarrow\infty}\sigma^{n}(a)$,
where the limit is well-defined;

  * •

a _morphic word_ generated by $\sigma$ and $\tau$ if $x=\tau(y)$, where $y$ is
a purely substitutive word generated by $\sigma$;

  * •

a _substitutive word_ generated by $\sigma$ if $x$ is a morphic word generated
by $\sigma$ and a coding $\tau$, i.e. $\tau(\mathcal{A})\subseteq\mathcal{A}$.

It is now possible to extend these definitions to the case where we use
multiple homomorphisms. However, most of literature revolves around the use of
multiple non-erasing homomorphisms (substitutions), and we will stick to this
case. Let $(\sigma_{n})_{n\in\mathbb{N}}$ be a sequence of substitutions. The
equivalent of a fixed-point of one homomorphism is an _infinitely
desubstitutable word_ by a sequence of substitutions:

######  Definition 6 (Infinitely desubstitutable words and directive
sequences)

Let $\mathcal{S}$ be a finite set of substitutions on a single alphabet
$\mathcal{A}$, and let $(\sigma_{n})_{n\in\mathbb{N}}\subseteq\mathcal{S}$. An
infinite word $x$ is _infinitely desubstitutable_ by
$(\sigma_{n})_{n\in\mathbb{N}}$ (called a _directive sequence_ of $x$) if, and
only if, there exists a sequence of infinite words $(x_{n})_{n\in\mathbb{N}}$
such that $x_{0}=x$ and $x_{n}=\sigma_{n}(x_{n+1})$. An infinite word $x$ is
infinitely desubstitutable by $\mathcal{S}$ if $x$ is infinitely
desubstitutable by some directive sequence
$(\sigma_{n})_{n\in\mathbb{N}}\subseteq\mathcal{S}$.

Just like for words, we write $\sigma_{\llbracket
i,j\rrbracket}=\sigma_{i}\circ\sigma_{i+1}\circ\dots\circ\sigma_{j}$. Then, by
compactness of $\mathcal{A}^{\mathbb{N}}$, $x$ is infinitely desubstitutable
by $(\sigma_{n})_{n\in\mathbb{N}}$ if, and only if, there is a sequence of
infinite words $(x_{n})_{n\in\mathbb{N}}$ such that $x=\sigma_{\llbracket
0,n\rrbracket}(x_{n+1})$ for all $n\geq 0$.

##  3 Finding substitutive and infinitely desubstitutable words in
$\omega$-automata

###  3.1 Desubstituting $\omega$-automata

In this section, we explain our main technical tool: an effective
transformation of $\omega$-automaton, called desubstitution. We define it for
the broad case of possibly erasing homomorphisms.

######  Definition 7 (Desubstitution of an $\omega$-automaton)

Let $\mathfrak{A}=(\mathcal{A},Q,I,T)$ be an $\omega$-automaton, and $\sigma$
a homomorphism. We define $\sigma^{-1}(\mathfrak{A})$ as the
$\omega$-automaton $(\mathcal{A},Q,I,T^{\prime})$ where, for all
$q_{1},q_{2}\in Q$ and $a\in\mathcal{A}$, $q_{1}\xrightarrow[]{a}q_{2}\in
T^{\prime}$ iff $q_{1}\xrightarrow[]{\sigma(a)}\mathstrut^{\ast}\hskip
1.99997ptq_{2}$ is a computation in $\mathfrak{A}$.

In particular, in this case, we consider that $q\xrightarrow{\varepsilon}q$ is
a computation. Thus, if $\sigma(a)=\varepsilon$, the desubstituted automaton
$\sigma^{-1}(\mathfrak{A})$ has a loop labeled by $a$ on every state.

For example, consider the following $\omega$-automaton $\mathfrak{A}$ and
substitution $\sigma$ (Figure 1(a,b)).

$\sigma:\left\\{\begin{array}[]{ccc}0&\mapsto&01\\\
1&\mapsto&0\end{array}\right.$

(a) $\sigma$

(b) $\mathfrak{A}$

(c) Intermediate step

(d) $\sigma^{-1}(\mathfrak{A})$

Figure 1: Desubstitution of the $\omega$-automaton $\mathfrak{A}$ by $\sigma$

We build the $\omega$-automaton $\sigma^{-1}(\mathfrak{A})$. Start from an
empty automaton on the same set of states. For every computation in
$\mathfrak{A}$ labeled by $01=\sigma(0)$ — say,
$q\xrightarrow[]{\sigma(0)}\mathstrut^{\ast}\hskip 1.99997ptr$ — add an edge
$q\xrightarrow[]{0}r$ to the automaton (Figure 1(c)). To conclude, do this
with $\sigma(1)=0$ (Figure 1(d)).

Stability by inverse morphism is a classical concept in the theory of finite
automata [8], and desubstitution satisfies the following property:

###### Proposition 1

An infinite word $u$ is accepted by $\sigma^{-1}(\mathfrak{A})$ if and only if
$\sigma(u)$ is accepted by $\mathfrak{A}$. In other words,
$\mathcal{L}_{\infty}(\sigma^{-1}(\mathfrak{A}))=\sigma^{-1}(\mathcal{L}_{\infty}(\mathfrak{A}))$.

###### Proof

Let $u$ be accepted by $\sigma^{-1}(\mathfrak{A})$. Consider the associated
accepting walk $(q_{i})_{i\in\mathbb{N}}$. By definition of
$\sigma^{-1}(\mathfrak{A})$, for every $i\in\mathbb{N}$, there exists a
computation $q_{i}\xrightarrow[]{\sigma(u_{i})}\mathstrut^{\ast}\hskip
1.99997ptq_{i+1}$ in $\mathfrak{A}$. By concatenating these computations, we
get an infinite computation
$q_{0}\xrightarrow[]{\sigma(u_{0})}\mathstrut^{\ast}\hskip
1.99997ptq_{1}\xrightarrow[]{\sigma(u_{1})}\mathstrut^{\ast}\hskip
1.99997ptq_{2}\xrightarrow[]{\sigma(u_{2})}\mathstrut^{\ast}\hskip
1.99997pt\cdots$ in $\mathfrak{A}$ that accepts $\sigma(u)$ in $\mathfrak{A}$.

Conversely, suppose there is a word of the form $\sigma(u)$ accepted by
$\mathfrak{A}$. Consider the states $(q_{i})_{i\in\mathbb{N}}$ obtained after
reading each $\sigma(a)$ for $a\in\mathcal{A}$. This defines an accepting
computation labeled by $u$ in $\sigma^{-1}(\mathfrak{A})$.

This proof actuallly provides a similar result for finite words:

###### Proposition 2

Let $w$ be a finite word, $\mathfrak{A}$ an $\omega$-automaton and $\sigma$ a
homomorphism. Then $q_{s}\xrightarrow[]{\sigma(w)}\mathstrut^{\ast}\hskip
1.99997ptq_{t}$ is a computation in $\mathfrak{A}$ iff
$q_{s}\xrightarrow[]{w}\mathstrut^{\ast}\hskip 1.99997ptq_{t}$ is a
computation in $\sigma^{-1}(\mathfrak{A})$.

An easy but significant property is the composition of desubstitution of
$\omega$-automata:

###### Proposition 3

Let $\mathfrak{A}$ be an $\omega$-automaton, and $\sigma$ and $\tau$ be two
homomorphisms. Then,
$(\sigma\circ\tau)^{-1}(\mathfrak{A})=\tau^{-1}(\sigma^{-1}(\mathfrak{A}))$.

###### Proof

These two $\omega$-automata share the same sets of states and of initial
states. We prove that they have the same transitions. We have indeed:

$\displaystyle q_{s}\xrightarrow[]{a}q_{t}\text{ in
}(\sigma\circ\tau)^{-1}(\mathfrak{A})$ $\displaystyle\iff
q_{s}\xrightarrow[]{\sigma\circ\tau(a)}\mathstrut^{\ast}\hskip
1.99997ptq_{t}\text{ in }\mathfrak{A}$ $\displaystyle\iff
q_{s}\xrightarrow[]{\tau(a)}\mathstrut^{\ast}\hskip 1.99997ptq_{t}\text{ in
}\sigma^{-1}(\mathfrak{A})\text{, by Proposition \ref{WordSub} }$
$\displaystyle\iff q_{s}\xrightarrow[]{a}q_{t}\text{ in
}\tau^{-1}(\sigma^{-1}(\mathfrak{A}))\text{, by Proposition \ref{WordSub}
again.}$

###  3.2 The problem of the purely substitutive walk

We underline the following property of desubstitutions of $\omega$-automata:

###### Fact 3.1

Let $\mathfrak{A}$ be an $\omega$-automaton, let $\mathfrak{S}(\mathfrak{A})$
be the set of all $\omega$-automata which have the same alphabet, the same set
of states and the same initial states as $\mathfrak{A}$. For any homomorphism
$\sigma$ on $\mathcal{A}$, $\sigma^{-1}(\mathfrak{A})$ is an element of
$\mathfrak{S}(\mathfrak{A})$.

The crucial point is that $\mathfrak{S}(\mathfrak{A})$ is finite: given
$\mathfrak{A}=(\mathcal{A},Q,I,T)$, an element of $\mathfrak{S}(\mathfrak{A})$
is identified by its transitions, which form a subset of
$(Q\times\mathcal{A}\times Q)$, so
$\text{Card}(\mathfrak{S}(\mathfrak{A}))=2^{|Q|^{2}\times|\mathcal{A}|}$. We
could work on a subset of $\mathfrak{S}(\mathfrak{A})$ by identifying
$\omega$-automata with the same language [2], but finiteness is sufficient for
our results.

Given $\mathfrak{A}$ an $\omega$-automaton and $\sigma$ a homomorphism,
$\sigma^{-1}$ defines a dynamic on the finite set
$\mathfrak{S}(\mathfrak{A})$. By the pigeonhole principle:

###### Fact 3.2

Let $\mathfrak{A}$ be an $\omega$-automaton, and $\sigma$ be a homomorphism.
Then there exist $n<m\leq|\mathfrak{S}(\mathfrak{A})|+1$ such that
$\sigma^{-n}(\mathfrak{A})=\sigma^{-m}(\mathfrak{A})$.

In the remainder of the section, we prove that, given an $\omega$-automaton
$\mathfrak{A}$ and a substitution $\sigma$, the problems of finding a fixed
point of $\sigma$ or a purely substitutive word generated by $\sigma$ accepted
by $\mathfrak{A}$ are decidable.

A purely substitutive word generated by an erasing homomorphism $\sigma$ is
also generated by a non-erasing homomorphism $\tau$ (that is, a substitution)
that can be effectively constructed: remove every erased letter from
$\mathcal{A}$ and from the images of $\sigma$, and repeat the process. Thus,
we assume $\sigma$ itself is a substitution.

###### Proposition 4

Let $\mathfrak{A}$ be an $\omega$-automaton, let $\sigma$ be a substitution
and let $n<m\leq|\mathfrak{S}(\mathfrak{A})|+1$ such that
$\sigma^{-n}(\mathfrak{A})=\sigma^{-m}(\mathfrak{A})$. Then, $\mathfrak{A}$
accepts a fixed point for $\sigma^{k}$ for some $k\geq 1$ iff
$\mathcal{L}_{\infty}(\sigma^{-n}(\mathfrak{A}))$ is nonempty.

###### Proof

If $\mathcal{L}_{\infty}(\sigma^{-n}(\mathfrak{A}))$ is empty, then, by
Propositions 1 and 3, $\mathcal{L}_{\infty}(\sigma^{-p}(\mathfrak{A}))$ is
empty for every $p\geq n$. Let $k\geq 1$: if there were a fixed point $x$ for
$\sigma^{k}$ accepted by $\mathfrak{A}$, we would have
$x=\sigma^{k}(x)=\sigma^{kn}(x)$ by iterating. So $x$ would be in
$\mathcal{L}_{\infty}(\sigma^{-kn}(\mathfrak{A}))$ which is empty. By
contradiction, there is no fixed point for any $\sigma^{k}$.

If $\mathcal{L}_{\infty}(\sigma^{-n}(\mathfrak{A}))$ is nonempty, let $x$ be a
word accepted by $\sigma^{-n}(\mathfrak{A})$. Again by Propositions 1 and 3,
because
$\sigma^{-n}(\mathfrak{A})=\sigma^{-m}(\mathfrak{A})=\sigma^{-(m-n)}(\sigma^{-n}(\mathfrak{A}))$,
$x$ is accepted by
$\sigma^{-j(m-n)}(\sigma^{-n}(\mathfrak{A}))=\sigma^{-(n+j(m-n))}(\mathfrak{A})$
for all $j\in\mathbb{N}$. This means that $\sigma^{n+j(m-n)}(x)$ is accepted
by $\mathfrak{A}$ for all $j\in\mathbb{N}$. Consider an adherence value
$\tilde{x}$ of the sequence $(\sigma^{n+j(m-n)}(x))_{j\in\mathbb{N}}$. By
compactness of the language of an $\omega$-automaton,
$\tilde{x}\in\mathcal{L}_{\infty}(\sigma^{-n}(\mathfrak{A}))$.

We define $Q_{\sigma^{m-n}}\subseteq\mathcal{A}$ the set of quiet letters for
$\sigma^{m-n}$: $a\in Q_{\sigma^{m-n}}$ if $|\sigma^{j(m-n)}(a)|=1$ for all
$j\geq 1$. Let $k=\inf\\{i\in\mathbb{N}\ |\ \tilde{x}_{i}\notin
Q_{\sigma^{m-n}}\\}$ ($k$ may be infinite). Then, for $i<k$, because $\sigma$
is a (nonerasing) substitution and every letter in $\tilde{x}_{\llbracket
0,k-1\rrbracket}$ is quiet,
$\sigma^{(m-n)}(\tilde{x})_{i}=\sigma^{(m-n)}(\tilde{x}_{i})$. In addition,
because $\tilde{x}$ is an adherence value of
$(\sigma^{n+j(m-n)}(x))_{j\in\mathbb{N}}$, there is $r(\tilde{x}_{i})\geq 1$
such that $\sigma^{r(\tilde{x}_{i})\cdot(m-n)}(\tilde{x}_{i})=\tilde{x}_{i}$
for every position $i<k$. Since $\mathcal{A}$ is finite,
$(r(\tilde{x}_{i}))_{0\leq i<k}$ contains only finitely many values, so we can
define $r=\text{lcm}\\{r(\tilde{x}_{i})\\}$.

When $k<\infty$, there exists $q\geq 1$ such that
$|\sigma^{q(m-n)}(\tilde{x}_{k})|>1$ and
$\tilde{x}_{k}\sqsubseteq_{p}\sigma^{q(m-n)}(\tilde{x}_{k})$, for the same
reason that $\tilde{x}$ is an adherence value of
$(\sigma^{n+j(m-n)}(x))_{j\in\mathbb{N}}$. If $k=\infty$, we set $q=1$.

Then, by concatenation, $\tilde{x}_{\llbracket
0,k\rrbracket}\sqsubseteq_{p}\sigma^{rq(m-n)}(\tilde{x}_{\llbracket
0,k\rrbracket})$. Thus, $(\sigma^{jrq(m-n)}(\tilde{x}))_{j\in\mathbb{N}}$ has
a limit, which is a fixed point for $\sigma^{rq(m-n)}$, and by compactness of
$\mathcal{L}_{\infty}(\mathfrak{A})$, is accepted by $\mathfrak{A}$.

Because the emptiness of the language of an $\omega$-automaton is decidable:

###### Corollary 1

The following problem is decidable:

Input:

An $\omega$-automaton $\mathfrak{A}$ and a substitution $\sigma$

Question:

Does $\mathfrak{A}$ accept a fixed point of $\sigma^{k}$ for some $k$?

As is, this method alone cannot determine, for instance, whether
$\mathfrak{A}$ accepts a fixed point for $\sigma$ itself (without power). This
problem is still decidable, as we show later in Proposition 6 with a
refinement of this method. In appendix, we provide examples where
$\mathfrak{A}$ accepts fixed points for some $\sigma^{k}$ where $k$ does not
correspond to $m-n$ where $n<m$ are the minimal powers such that
$\sigma^{-n}(\mathfrak{A})=\sigma^{-m}(\mathfrak{A})$.

Now, we come back to purely substitutive words. A purely substitutive word
generated by $\sigma$ is also a fixed point for some $\sigma^{k}$ (in fact, it
is a fixed point for every $\sigma^{j}$ with $j\geq 1$).

###### Proposition 5

Let $\mathfrak{A}$ be an $\omega$-automaton, $\sigma$ a substitution and
$n<m\leq|\mathfrak{S}(\mathfrak{A})|+1$ such that
$\sigma^{-n}(\mathfrak{A})=\sigma^{-m}(\mathfrak{A})$. Let
$RP_{\sigma}\subseteq\mathcal{A}$ be the set of letters $b$ that are right-
prolongable for $\sigma$, i.e. $b\sqsubseteq_{p}\sigma(b)$ and
$b\neq\sigma(b)$. Then, $\mathfrak{A}$ accepts a purely substitutive word
generated by $\sigma$ iff $\sigma^{-n}(\mathfrak{A})$ accepts an infinite word
beginning with an element of $RP_{\sigma}$.

###### Proof

If $\mathfrak{A}$ accepts a purely substitutive word $u$ generated by
$\sigma$, $u=\lim_{j\rightarrow\infty}\sigma^{j}(b)$ begins by an element of
$RP_{\sigma}$. Since $\sigma(u)=u$, $\sigma^{n}(u)$ is accepted by
$\mathfrak{A}$ so $u$ is accepted by $\sigma^{-n}(\mathfrak{A})$.

On the converse, suppose that $\sigma^{-n}(\mathfrak{A})$ accepts an infinite
word beginning by $b\in RP_{\sigma}$. Then, $\sigma^{m-n}(b)$ labels an
accepting computation on
$\sigma^{-m}(\mathfrak{A})=\sigma^{-n}(\mathfrak{A})$. By iteration, for every
$k\geq 1$, we have that $\sigma^{k(m-n)}(b)$ labels an accepting computation
on $\sigma^{-n}(\mathfrak{A})$, so $\sigma^{n+k(m-n)}(b)$ always labels an
accepting computation on $\mathfrak{A}$. By compactness,
$u=\lim\limits_{k\rightarrow\infty}\sigma^{n+k(m-n)}(b)$ is accepted by
$\mathfrak{A}$. Now, because $b\in RP_{\sigma}$, the word
$\lim\limits_{j\rightarrow\infty}\sigma^{j}(b)$ is defined and equal to $u$.
Therefore $u$, the purely substitutive word generated by $\sigma$ on the
letter $b$, is accepted by $\mathfrak{A}$.

The following result already appeared in [15], but an erratum clarified that
some cases were not covered [16]. It is a parallel to a result in [5]. Our
proof is essentially the same, but writing the proof through the lens of
desubstitution makes it easier to extend the result to other decision
problems.

###### Corollary 2

The problem of the purely substitutive walk is decidable:

Input:

an $\omega$-automaton $\mathfrak{A}$, a homomorphism $\sigma$.

Question:

Does $\mathfrak{A}$ accept some purely substitutive word generated by
$\sigma$?

This result extends to morphic words: to find a morphic word generated by
$\sigma$ and $\tau$ accepted by $\mathfrak{A}$, find a purely substitutive
word generated by $\sigma$ accepted by $\tau^{-1}(\mathfrak{A})$.

We now extend the method used to prove Proposition 5 to solve the question of
finding a pure fixed point for a substitution $\sigma$ in an
$\omega$-automaton. This improves Proposition 4 where we found a fixed point
for some power of $\sigma$.

###### Proposition 6

The problem of the fixed point walk is decidable:

Input:

an $\omega$-automaton $\mathfrak{A}$, a substitution $\sigma$.

Question:

Does $\mathfrak{A}$ accepts a fixed point for $\sigma$?

###### Proof

Let $x$ be a fixed point for $\sigma$ and define
$FP_{\sigma}=\\{b\in\mathcal{A}\ |\ \sigma(b)=b\\}$ be the set of letters
which are fixed points under $\sigma$. There are two cases:

  1. 1.

$x$ is an infinite word on the alphabet $FP_{\sigma}$.

  2. 2.

there is a letter $a$ appearing in $x$ such that $\sigma(a)\neq a$. Suppose
that $a$ is the first such letter in $x$. Then $x$ can be written as
$x=pax^{\prime}$ where $p$ is a word on $FP_{\sigma}$. We have that
$x=\sigma(x)=\sigma(p)\sigma(a)\sigma(x^{\prime})=p\sigma(a)\sigma(x^{\prime})$.
So $a\sqsubseteq_{p}\sigma(a)$: $a$ is right-prolongable for $\sigma$, so
$\lim\limits_{n\rightarrow\infty}\sigma^{n}(a)$ exists. Since
$x=\sigma^{n}(x)=p\sigma^{n}(a)\sigma^{n}(x^{\prime})$ for every
$n\in\mathbb{N}$, by compactness,
$x=p\lim\limits_{n\rightarrow\infty}\sigma^{n}(a)$.

The algorithm works as follows. First (case 1), check whether $\mathfrak{A}$
accepts a word on the alphabet $FP_{\sigma}$. Second (case 2), define a new
automata $\mathfrak{A}^{\prime}$ which is equal to $\mathfrak{A}$ except that
the set of initial states is all the states reachable in $\mathfrak{A}$ by
words in $FP_{\sigma}$, and check (by the previous algorithm) if
$\mathfrak{A}^{\prime}$ accepts a purely substitutive word generated by
$\sigma$.

The algorithm outputs ”yes” if either case is satisfied, and ”no” otherwise.

###  3.3 The problem of the infinitely desubstitutable walk

In this section, we suppose that $\mathfrak{A}$ is an $\omega$-automaton and
$\mathcal{S}$ is a finite set of substitutions (i.e. nonerasing homomorphisms,
as is usual when studying multiple homomorphisms) on a single alphabet
$\mathcal{A}$. We prove that the problem of finding an infinitely
desubstitutable (infinite) word accepted by $\mathfrak{A}$ is decidable. To
study this question, we introduce a meta-$\omega$-automaton: each symbol is a
substitution, and each state is an $\omega$-automaton.

######  Definition 8 (The meta-$\omega$-automaton
$\mathcal{S}^{-\infty}(\mathfrak{A})$)

We define the $\omega$-automaton
$\mathcal{S}^{-\infty}(\mathfrak{A})=(\mathcal{S},D(\mathfrak{A}),\\{\mathfrak{A}\\},\mathcal{T})$
with the alphabet $\mathcal{S}$, the set of states
$D(\mathfrak{A})=\\{\sigma^{-1}(\mathfrak{A}),\
\sigma\in\mathcal{S}^{\ast}\\}$, $\mathfrak{A}$ the only initial state and set
of transitions
$\mathcal{T}=\\{\mathfrak{B}\xrightarrow[]{\sigma}\sigma^{-1}(\mathfrak{B})\
|\ \mathfrak{B}\in D(\mathfrak{A}),\sigma\in\mathcal{S}\\}$.

Because $D(\mathfrak{A})\subseteq\mathfrak{S}(\mathfrak{A})$ is finite (see
Fact 3.1), $\mathcal{S}^{-\infty}(\mathfrak{A})$ is computable. We prove that
directive sequences of words accepted by $\mathfrak{A}$ correspond to _non-
nilpotent_ walks in $\mathcal{S}^{-\infty}(\mathfrak{A})$, that is, walks
$(\mathfrak{B}_{n})_{n\in\mathbb{N}}$ such that
$\mathcal{L}_{\infty}(\mathfrak{B}_{n})\neq\emptyset$ for all $n$.

###### Proposition 7

There exists $x$ an infinite word infinitely desubstitutable by
$(\sigma_{n})_{n\in\mathbb{N}}$ accepted by $\mathfrak{A}$ if, and only if,
there is a non-nilpotent infinite walk in
$\mathcal{S}^{-\infty}(\mathfrak{A})$ labeled by
$(\sigma_{n})_{n\in\mathbb{N}}$.

###### Corollary 3

The set of directive sequences of infinitely desubstitutable words accepted by
$\mathfrak{A}$ is the language of some $\omega$-automaton.

######  Proof (of Proposition 7)

First, let $x$ be an infinitely desubstitutable word with directive sequence
$(\sigma_{n})_{n\in\mathbb{N}}$, and let $(x_{n})_{n\in\mathbb{N}}$ be the
sequence of desubstituted words. Then, by Proposition 1,
$x_{n}\in\mathcal{L}_{\infty}((\sigma_{1}\circ\dots\circ\sigma_{n-1})^{-1}(\mathfrak{A}))$.
So the walk $(\sigma_{\llbracket
0,n\rrbracket}^{-1}(\mathfrak{A}))_{n\in\mathbb{N}}$ is non-nilpotent and
labeled by $(\sigma_{n})_{n\in\mathbb{N}}$.

Second, let $(\sigma_{n})_{n\in\mathbb{N}}$ label a non-nilpotent infinite
walk in $\mathcal{S}^{-\infty}(\mathfrak{A})$. It means that each language
$(\sigma_{1}\circ\dots\circ\sigma_{k})^{-1}(\mathcal{L}_{\infty}(\mathfrak{A}))$
is nonempty. Now, consider the sequence
$((\sigma_{1}\circ\dots\circ\sigma_{n})(\mathcal{L}_{\infty}((\sigma_{1}\circ\dots\circ\sigma_{n})^{-1}(\mathfrak{A}))))_{n\in\mathbb{N}}$.
It satisfies the following:

  1. 1.

each element of the sequence is included in
$\mathcal{L}_{\infty}(\mathfrak{A})$;

  2. 2.

because
$\mathcal{L}_{\infty}((\sigma_{1}\circ\dots\circ\sigma_{n})^{-1}(\mathfrak{A})))$
is compact and nonempty, and $(\sigma_{1}\circ\dots\circ\sigma_{n})$ is
continuous, every element of the sequence is compact and nonempty;

  3. 3.

the sequence is decreasing for inclusion.

By Cantor’s intersection theorem, there is a point $x$ in the intersection of
every element of the sequence. This point $x$ is desubstitutable by any
$\sigma_{1}\circ\dots\circ\sigma_{k}$, thus it is infinitely desubstitutable
by the sequence $(\sigma_{n})_{n\in\mathbb{N}}$.

With Proposition 7, we can deduce the decidability of the existence of an
infinitely desubstitutable word accepted by an $\omega$-automaton
$\mathfrak{A}$. First, build $\mathcal{S}^{-\infty}(\mathfrak{A})$; second,
remove the states corresponding to $\omega$-automata with an empty language;
last, check whether there is an infinite walk.

###### Proposition 8

The problem of the infinitely desubstitutable walk is decidable:

Input:

a finite set of substitutions $\mathcal{S}$, an $\omega$-automaton
$\mathfrak{A}$

Question:

does $\mathcal{L}_{\infty}(\mathfrak{A})$ contain a word which is infinitely
desubstitutable by $\mathcal{S}$?

###  3.4 The problem of the Büchi infinitely desubstitutable walk

Proposition 8 does not apply directly to Sturmian words. Indeed, the classical
characterization of Sturmian words restricts the possible directive sequences.

$\mathcal{S}_{St}$ is the set containing the four following substitutions,
called (elementary) Sturmian morphisms, as described by [10].

$L_{0}:\left\\{\begin{array}[]{ccc}0&\mapsto&0\\\
1&\mapsto&01\end{array}\right.,\quad
L_{1}:\left\\{\begin{array}[]{ccc}0&\mapsto&10\\\
1&\mapsto&1\end{array}\right.,\quad
R_{0}:\left\\{\begin{array}[]{ccc}0&\mapsto&0\\\
1&\mapsto&10\end{array}\right.,\quad
R_{1}:\left\\{\begin{array}[]{ccc}0&\mapsto&01\\\
1&\mapsto&1\end{array}\right.$

######  Theorem 3.3 ([13])

A word is Sturmian iff it is infinitely desubstitutable by a directive
sequence $(\sigma_{n})_{n\in\mathbb{N}}\subset\mathcal{S}_{St}$ that
alternates infinitely in type, i.e.: $\nexists N\in\mathbb{N},(\forall n\geq
N,\sigma_{n}\in\\{L_{0},R_{0}\\})$ or $(\forall n\geq
N,\sigma_{n}\in\\{L_{1},R_{1}\\})$.

This characterization is usually expressed in the $S$-adic framework, but is
equivalent in this context [14]. In this section, we generalize Proposition 8
to Sturmian words and more general restrictions on the directive sequence.

###### Proposition 9

The problem of the Sturmian walk is decidable:

Input:

an $\omega$-automaton $\mathfrak{A}$.

Question:

is there a Sturmian infinite word accepted by $\mathfrak{A}$?

###### Proof

Consider the associated representation automaton
$\mathcal{S}_{St}^{-\infty}(\mathfrak{A})$. According to Proposition 7
combined with Theorem 3.3, there is a Sturmian infinite word accepted by
$\mathfrak{A}$ if, and only if, there is an infinite computation accepted by
$\mathcal{S}_{St}^{-\infty}(\mathfrak{A})$ labeled by a word
$(\sigma_{n})_{n\in\mathbb{N}}$ which alternates infinitely in type. This last
condition is decidable: compute the strong connected components of
$\mathfrak{A}$, and check that there is at least one strongly connected
component $C$ which contains two edges labeled by substitutions in
$\\{L_{0},R_{0}\\}$ and $\\{L_{1},R_{1}\\}$, respectively.

In this case, the condition of alternating infinitely in type is easy to
check: it can actually be described using a Büchi $\omega$-automaton on the
alphabet $\mathcal{S}$. Proposition 9 generalizes to every such condition.

###### Definition 9

Let $\mathcal{S}$ be a set of substitutions, and $\mathfrak{R}$ a Büchi
$\omega$-automaton on the alphabet $\mathcal{S}$. Define $X_{\mathfrak{R}}$ as
$\\{x\in\mathcal{A}^{\mathbb{N}}\ |\
\exists(\sigma_{n})_{n\in\mathbb{N}}\in\mathcal{L}_{\infty}(\mathfrak{R}),x\text{
is inf. desub. by }(\sigma_{n})\\}$.

###### Proposition 10

The following problem is decidable:

Input:

an $\omega$-automaton $\mathfrak{A}$, a finite set of substitutions
$\mathcal{S}$, a Büchi $\omega$-automaton $\mathfrak{R}$ on the alphabet
$\mathcal{S}$

Question:

is there an infinite word of $X_{\mathfrak{R}}$ accepted by $\mathfrak{A}$?

###### Proof

The question of the problem is equivalent to: is
$\mathcal{L}_{\infty}(\mathfrak{R})\cap\mathcal{L}_{\infty}(\mathcal{S}^{-\infty}(\mathfrak{A}))\neq\emptyset$?
The intersection between a Büchi $\omega$-automaton and an $\omega$-automaton
is a Büchi $\omega$-automaton that can be effectively constructed [11], and
checking the non-emptiness of a Büchi $\omega$-automaton is decidable.

The interest of Proposition 10 is that there exists a zoology of families of
words which have a characterization by infinite desubstitution. For instance,
Proposition 10 applies to Arnoux-Rauzy words [1] and to minimal dendric
ternary words [7]. We also characterize the set of allowed directive sequences
akin to Corollary 3: the set of directive sequences on $\mathcal{S}$ accepted
by the Büchi $\omega$-automaton $\mathfrak{R}$ that define a word accepted by
$\mathfrak{A}$ is itself recognized by a Büchi $\omega$-automaton.

Let us translate Proposition 10 in more dynamical terms:

###### Proposition 11

The following problem is decidable:

Input:

a set of substitutions $\mathcal{S}$, a Büchi $\omega$-automaton
$\mathfrak{R}$ on the alphabet $\mathcal{S}$ and a sofic shift $\mathbb{S}$.

Question:

Is $\mathbb{S}\cap X_{\mathfrak{R}}$ empty?

###  3.5 Application to the coding of Sturmian words

Here is an example of a natural question from combinatorics on words that we
solve on Sturmian words, even though the method generalizes easily. Let $W$ be
a finite set of finite words on $\\{0,1\\}$. Consider $W^{\omega}$ the set of
infinite concatenations of elements of $W$, i.e.
$W^{\omega}=\\{x\in\\{0,1\\}^{\mathbb{N}}\ |\
\exists(w_{n})_{n\in\mathbb{N}}\subseteq
W,x=\lim\limits_{n\rightarrow\infty}w_{0}w_{1}\dots w_{n}\\}$.

###### Proposition 12

The following problem is decidable:

Input:

$W$ a finite set of words on {0,1}

Question:

does $W^{\omega}$ contain a Sturmian word?

###### Proof

The language $W^{\omega}$ is $\omega$-regular: there is an $\omega$-automaton
$\mathfrak{A}_{W}$ such that
$\mathcal{L}_{\infty}(\mathfrak{A}_{W})=W^{\omega}$. Then, $W^{\omega}$
contains a Sturmian word iff $\mathfrak{A}_{W}$ accepts a Sturmian word, which
is decidable by Proposition 9.

##  4 About $\omega$-automata recognizing Sturmian words

In this Section, we focus on Sturmian words and show that the language of
Sturmian words is as far as possible from being regular, in the sense that an
$\omega$-automaton may only accept a Sturmian word if it accepts the image of
the full shift under a Sturmian morphism.

###### Theorem 4.1

Let $\mathcal{S}=\mathcal{S}_{St}$ be the set of elementary Sturmian morphisms
as defined earlier, and let $\mathfrak{A}$ be an $\omega$-automaton. If
$\mathfrak{A}$ accepts a Sturmian word, then
$\exists\sigma\in\mathcal{S}_{St}^{\ast},\sigma(\mathcal{A}^{\mathbb{N}})\subseteq\mathcal{L}_{\infty}(\mathfrak{A})$.

This is equivalent to the presence of a total automaton in
$\mathcal{S}^{-\infty}(\mathfrak{A})$: an $\omega$-automaton $\mathfrak{A}$ is
total if $\mathcal{L}_{\infty}(\mathfrak{A})=\mathcal{A}^{\mathbb{N}}$.
Totality is a stable property under any desubstitution.

To prove Theorem 4.1, we introduce the following technical tools.

###### Definition 10

Let $\mathfrak{A}$ be an $\omega$-automaton on $\mathcal{A}=\\{0,1\\}$. A
state $q$ of $\mathfrak{A}$ has property $(H)$ if $(\exists
q_{s},q\xrightarrow[]{0}q_{s}\xrightarrow[]{}\mathstrut^{\omega}\hskip
1.99997pt\cdots\in\mathfrak{A})\Leftrightarrow(\exists
q_{t},q\xrightarrow[]{1}q_{t}\xrightarrow[]{}\mathstrut^{\omega}\hskip
1.99997pt\cdots\in\mathfrak{A})$, where
$q_{s}\xrightarrow[]{}\mathstrut^{\omega}\hskip 1.99997pt\cdots$ means that
there is an infinite computation starting from $q_{t}$ in $\mathfrak{A}$.

If all states of $\mathfrak{A}$ have property (H), there are two
possibilities: if there is no infinite computation starting on an initial
state, the infinite language of $\mathfrak{A}$ is empty; otherwise,
$\mathfrak{A}$ is total.

###### Lemma 1

Let $\mathfrak{C}$ be an $\omega$-automaton, and
$\phi\in\mathcal{S}_{St}^{\ast}$ starting with $L_{0}$ and ending with $L_{1}$
such that $\phi^{-1}(\mathfrak{C})=\mathfrak{C}$. Then, every state of
$\mathfrak{C}$ has property $(H)$.

######  Proof (of Lemma 1)

Let
$\mathfrak{C}=(\\{0,1\\},Q_{\mathfrak{C}},I_{\mathfrak{C}},T_{\mathfrak{C}})$,
and $q\in Q_{\mathfrak{C}}$. First, suppose that
$q\xrightarrow[]{0}q_{t}\xrightarrow[]{}\mathstrut^{\omega}\hskip
1.99997pt\cdots$ is a computation in $\mathfrak{C}$. Then
$q\xrightarrow[]{0}q_{t}$ is also a transition of $\phi^{-1}(\mathfrak{C})$.
So $q\xrightarrow[]{\phi(0)}\mathstrut^{\ast}\hskip 1.99997ptq_{t}$ is a
computation in $\mathfrak{C}$. Because $\phi$ ends with $L_{1}$,
$\phi(1)\sqsubseteq_{p}\phi(0)$. So
$q\xrightarrow[]{\phi(1)}\mathstrut^{\ast}\hskip
1.99997ptq_{u}\xrightarrow[]{m}\mathstrut^{\ast}\hskip
1.99997ptq_{t}\xrightarrow[]{}\mathstrut^{\omega}\hskip 1.99997pt\cdots$ is a
computation in $\mathfrak{C}$, with some $q_{u}\in Q_{\mathfrak{C}}$ and
$\phi(0)=\phi(1)m$. Now, using $\mathfrak{C}=\phi^{-1}(\mathfrak{C})$,
$q\xrightarrow[]{1}q_{u}\xrightarrow[]{m}\mathstrut^{\ast}\hskip
1.99997ptq_{t}\xrightarrow[]{}\mathstrut^{\omega}\hskip 1.99997pt\cdots$ is a
computation in $\mathfrak{C}$.

Conversely, if
$q\xrightarrow[]{1}q_{t}\xrightarrow[]{}\mathstrut^{\omega}\hskip
1.99997pt\cdots$ is a computation in $\mathfrak{C}=\phi^{-1}(\mathfrak{C})$,
there is also $q\xrightarrow[]{\phi(1)}\mathstrut^{\ast}\hskip
1.99997ptq_{t}\xrightarrow[]{}\mathstrut^{\omega}\hskip 1.99997pt\cdots$
Because $\phi$ begins with $L_{0}$, $\phi(1)=0m$ for some finite $m$. So the
last computation can be written
$q\xrightarrow[]{0}q_{u}\xrightarrow[]{m}\mathstrut^{\ast}\hskip
1.99997ptq_{t}\xrightarrow[]{}\mathstrut^{\omega}\hskip 1.99997pt\cdots$

######  Proof (of Theorem 4.1)

Let $x$ be a Sturmian word accepted by $\mathfrak{A}$. Consider the
transformation of $\omega$-automata
$\text{forget}:(\mathcal{A},Q,I,T)\mapsto(\mathcal{A},Q,Q,T)$ which makes all
states initial. Then, $\text{forget}(\mathfrak{A})$ also accepts $x$, and
$\mathcal{L}_{\infty}(\text{forget}(\mathfrak{A}))$ is a sofic shift. Then
$\overline{\bigcup\limits_{n\geq 0}S^{n}(x)}$, which is the orbit of $x$ under
the shift $S$, is contained in
$\mathcal{L}_{\infty}(\text{forget}(\mathfrak{A}))$. Let $\chi(x)$ be the
Sturmian characteristic word associated with $x$ (see [12]): it belongs to the
orbit of $x$, so it is accepted by $\text{forget}(\mathfrak{A})$. Then,
$\chi(x)=\lim\limits_{n\rightarrow\infty}\sigma_{0}\circ\dots\circ\sigma_{n}(a_{n})$
with $(\sigma_{n})_{n\in\mathbb{N}}\subseteq\mathcal{S}_{St}$ a sequence that
alternates infinitely in type (see Theorem 3.3). Besides, because $\chi(x)$ is
a characteristic word, it represents the orbit of zero from the point of view
of circle rotation (see [12]): when combined with Proposition 2.7 of [4], it
yields that
$(\sigma_{n})_{n\in\mathbb{N}}\subseteq\\{L_{0},L_{1}\\}^{\mathbb{N}}$. By the
pigeonhole principle, there is an $\omega$-automaton $\mathfrak{B}$ that
appears infinitely often in the sequence $(\sigma_{\llbracket
0,n\rrbracket}^{-1}(\text{forget}(\mathfrak{A})))_{n\in\mathbb{N}}\subseteq\mathfrak{S}(\text{forget}(\mathfrak{A}))$.
Thus, we can find a substitution $\tau$ such that
$\mathfrak{B}=\tau^{-1}(\mathfrak{B})$ and
$\tau\in\\{L_{0},L_{1}\\}^{\ast}\setminus(L_{0}^{\ast}\cup L_{1}^{\ast})$.
Because $\tau$ contains both $L_{0}$ and $L_{1}$, there are two cases:

  1. 1.

$L_{1}L_{0}\sqsubseteq_{f}\tau$: we can write
$\tau=p_{\tau}L_{1}L_{0}s_{\tau}$. Let $\mathfrak{B}^{\prime}=(p_{\tau}\circ
L_{1})^{-1}(\mathfrak{B})$ and $\tau^{\prime}=L_{0}\circ s_{\tau}\circ
p_{\tau}\circ L_{1}$: we have that
$\tau^{\prime-1}(\mathfrak{B}^{\prime})=\mathfrak{B}^{\prime}$.

  2. 2.

$L_{1}L_{0}\not\sqsubseteq_{f}\tau$: then, $\tau$ begins with a $L_{0}$ and
ends with a $L_{1}$.

In both cases, we can come back to the case where $\tau$ begins with a $L_{0}$
and ends with a $L_{1}$.

Now, we apply Lemma 1 to show that every state of $\mathfrak{B}$ has property
$(H)$. $\mathfrak{B}$ can be written as
$\psi^{-1}(\text{forget}(\mathfrak{A}))$ for some Sturmian morphism $\psi$.
Since the transformation forget does not modify the transitions of an
$\omega$-automaton, this yields that every state of $\psi^{-1}(\mathfrak{A})$
also has property $(H)$. Since by assumption $\psi^{-1}(\mathfrak{A})$ accepts
an infinite word, it follows that it is total.

Let $f$ be the Fibonacci word, i.e. the substitutive word associated with the
substitution $\sigma_{f}(0)=01,\sigma_{f}(1)=0$. Since Lemma 1 holds when
$\phi=\sigma_{f}^{n}$ ($n\geq 1$), by adapting the proof of Theorem 4.1, we
obtain an equivalent statement for $f$:

###### Corollary 4

Let $\mathfrak{A}$ be an $\omega$-automaton which accepts $f$. Then, there
exists $n\in\mathbb{N}$ such that $\sigma_{f}^{-n}(\mathfrak{A})$ is total.

This combinatorial result can be thought in dynamical terms:

###### Corollary 5

A sofic subshift $\mathbb{S}$ contains $f$ iff $\mathbb{S}$ contains some
$\sigma_{f}^{n}(\mathcal{A}^{\mathbb{N}})$.

Because the Fibonacci word is aperiodic, containing $f$ means that there is a
substitution $\tau$ such that $\tau(\mathcal{A}^{\mathbb{N}})$ is contained in
$\mathbb{S}$. Because the Fibonacci word is Sturmian, Berstel and Séébold [10]
established that $\tau$ had to be a Sturmian morphism. This new analysis
specifies that $\tau$ can be chosen a power of $\sigma_{f}$.

##  5 Open questions

  * •

Following Proposition 8, find an algorithm to find an accepted
$\mathcal{S}$-adic word. There are technical difficulties to take into account
the growth of the directive sequence, which should be solvable using results
from [14].

  * •

Can our methods extend to Büchi $\omega$-automata, as in [5]? The difficulty
is that the language of Büchi $\omega$-automata is not always compact, so
Proposition 4 does not apply. It may be possible to extend methods from [5].

  * •

For which sets of substitutions does Theorem 4.1 hold?

## References

  * [1] Arnoux, P., Rauzy, G.: Représentation géométrique de suites de complexité 2n+1. Bulletin de la Société mathématique de France 119(2), 199–215 (1991). https://doi.org/10.24033/bsmf.2164
  * [2] Bassino, F., David, J., Sportiello, A.: Asymptotic enumeration of minimal automata. In: Dürr, C., Wilke, T. (eds.) 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), vol. 14, pp. 88–99. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2012). https://doi.org/10.4230/LIPIcs.STACS.2012.88
  * [3] Berstel, J.: Axel Thue’s papers on repetitions in words: a translation. In: Monographies du LaCIM, vol. 11, pp. 65–80. LaCIM (1992), https://hal.science/hal-00620702
  * [4] Berthé, V., Holton, C., Zamboni, L.Q.: Initial powers of sturmian sequences. Acta Arithmetica 122, 315–347 (2006). https://doi.org/10.4064/aa122-4-1
  * [5] Carton, O., Thomas, W.: The monadic theory of morphic infinite words and generalizations. Information and Computation 176(1), 51–65 (2002). https://doi.org/https://doi.org/10.1006/inco.2001.3139
  * [6] Ferenczi, S.: Rank and symbolic complexity. Ergodic Theory and Dynamical Systems 16(4), 663–682 (1996). https://doi.org/10.1017/S0143385700009032
  * [7] Gheeraert, F., Lejeune, M., Leroy, J.: _S_ -adic characterization of minimal ternary dendric subshifts. CoRR abs/2102.10092 (2021), https://arxiv.org/abs/2102.10092
  * [8] Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company (1979)
  * [9] Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press (1995). https://doi.org/10.1017/CBO9780511626302
  * [10] Lothaire, M.: Sturmian words. In: Algebraic Combinatorics on Words, chap. 2, p. 45–110. Encyclopedia of Mathematics and its Applications, Cambridge University Press (2002). https://doi.org/10.1017/CBO9781107326019.003
  * [11] Perrin, D., Pin, J.E.: Infinite Words, Pure and Applied Mathematics, vol. 141. Elsevier (2004). https://doi.org/https://doi.org/10.1016/S0079-8169(04)80002-3
  * [12] Perrin, D., Restivo, A.: A note on sturmian words. Theoretical Computer Science 429, 265–272 (2012). https://doi.org/https://doi.org/10.1016/j.tcs.2011.12.047
  * [13] Pytheas Fogg, N., Berthé, V., Ferenczi, S., Mauduit, C., Siegel, A.: Sturmian sequences. In: Substitutions in Dynamics, Arithmetics and Combinatorics, chap. 6, pp. 143–198. Springer Berlin Heidelberg (2002). https://doi.org/10.1007/3-540-45714-3_6
  * [14] Richomme, G.: On sets of indefinitely desubstitutable words. Theoretical Computer Science 857, 97–113 (2021). https://doi.org/https://doi.org/10.1016/j.tcs.2021.01.004
  * [15] Salo, V.: Decidability and universality of quasiminimal subshifts. Journal of Computer and System Sciences 89, 288–314 (2017). https://doi.org/10.1016/j.jcss.2017.05.017
  * [16] Salo, V.: Notes and errata on ”Decidability and Universality of Quasiminimal Subshifts” (2022), https://villesalo.com/notes/DaUoQSNotes.html
  * [17] Thomas, W.: Handbook of Formal Languages: Volume 3 Beyond Words. Springer Berlin Heidelberg (1997). https://doi.org/10.1007/978-3-642-59126-6

##  6 Appendix

###  6.1 Counterexamples for Proposition 4

Using the notation of Proposition 4, consider $n<m$ minimal such that
$\sigma^{-n}(\mathfrak{A})=\sigma^{-m}(\mathfrak{A})$. There is no clear
relationship between $n$, $m$ and $k$ the power of the fixed point accepted by
$\mathfrak{A}$.

Here is a example with $m-n\geq 2$, but $\mathfrak{A}$ accepts a fixed point
for $\sigma$.

$\sigma:\left\\{\begin{array}[]{ccc}0&\mapsto&0\\\ 1&\mapsto&2\\\
2&\mapsto&1\\\ \end{array}\right.$

000111

Figure 2: $n=0$ and $m=2$, but $\mathfrak{A}$ accepts $0^{\infty}$, which is a
fixed point for $\sigma$.

Next is an example where $m-n$ is lesser than the power required to have a
fixed point:

$\tau:\left\\{\begin{array}[]{ccc}0&\mapsto&11\\\
1&\mapsto&00\end{array}\right.$

Figure 3: $\tau^{-1}(\mathfrak{B})=\mathfrak{B}$, so $m=1$ and $n=0$. $\tau$
has no fixed point: $\mathfrak{B}$ cannot contain a fixed point for
$\tau^{m-n}$. However, $\mathfrak{B}$ contains a fixed point for $\tau^{2}$.

###  6.2 There is not always a total automaton in
$\mathcal{S}^{-\infty}(\mathfrak{A})$

Theorem 4.1 does not generalize straightforwardly to any set of substitutions:
in general, $\mathcal{S}^{-\infty}(\mathfrak{A})$ may not contain a total
automaton, even under classical dynamical constraints. For instance, consider
the following $\omega$-automaton $\mathfrak{A}_{H}$ and susbtitution
$\sigma_{H}$:

$\sigma_{H}:\left\\{\begin{array}[]{ccc}0&\mapsto&0120\\\
1&\mapsto&11220011\\\ 2&\mapsto&222000111222\end{array}\right.$

001122

Figure 4: An $\omega$-automaton stable by desubstitution by $\sigma_{H}$.

Notice that $\sigma_{H}$ is primitive, and that the three purely substitutive
words generated by $\sigma_{H}$ are not eventually periodic. However,
$\mathfrak{A}_{H}$ is not total, and
$\sigma_{H}^{-1}(\mathfrak{A}_{H})=\mathfrak{A}_{H}$, so there is no total
automaton in $\mathcal{S}^{-\infty}(\mathfrak{A})$. In dynamical terms, it
means that the sofic shift contains the associated purely substitutive words,
but contains no factor of the form $\sigma_{H}^{k}(\mathcal{A}^{\mathbb{N}})$.


:
1

# Learning functional sections in medical conversations:
iterative pseudo-labeling and human-in-the-loop approach

Mengqian Wang<EMAIL_ADDRESS>
University of North Carolina at Chapel Hill
Ilya Valmianski<EMAIL_ADDRESS>
Xavier Amatriain<EMAIL_ADDRESS>
Anitha Kannan<EMAIL_ADDRESS>
Curai Health Work done during an internship at Curai Health

###### Abstract

Medical conversations between patients and medical professionals have implicit
functional sections, such as “history taking”, “summarization”, “education”,
and “care plan.” In this work, we are interested in learning to automatically
extract these sections. A direct approach would require collecting large
amounts of expert annotations for this task, which is inherently costly due to
the contextual inter-and-intra variability between these sections. This paper
presents an approach that tackles the problem of learning to classify medical
dialogue into functional sections without requiring a large number of
annotations. Our approach combines pseudo-labeling and human-in-the-loop.
First, we bootstrap using weak supervision with pseudo-labeling to generate
dialogue turn-level pseudo-labels and train a transformer-based model, which
is then applied to individual sentences to create noisy sentence-level labels.
Second, we iteratively refine sentence-level labels using a cluster-based
human-in-the-loop approach. Each iteration requires only a few dozen annotator
decisions. We evaluate the results on an expert-annotated dataset of 100
dialogues and find that while our models start with 69.5% accuracy, we can
iteratively improve it to 82.5%. Code used to perform all experiments
described in this paper can be found here: https://github.com/curai/curai-
research/tree/main/functional-sections.

###### keywords:

Medical NLP, Medical Dialogue, Medical Sections, Pseudo-labeling, Human-in-
the-loop

##  1 Introduction

Recent growth in telemedicine has led to a dramatic expansion in text-based
chat communications between patients and medical professionals (Bestsennyy et
al., 2021). This creates new opportunities for improving medical professional
workflows through the introduction of natural language understanding (NLU)
systems for providing real-time decision support and automating electronic
health record (EHR) charting (Dreisbach et al., 2019; Joshi et al., 2020;
Valmianski et al., 2021). Auto-charting, in particular, benefits significantly
from proper contextualization of the dialogue (Khosla et al., 2020; Krishna et
al., 2021). For example, the History of Present Illness (HPI) section of the
progress note can be derived from the history-taking discussion in the
dialogue, while the Care Plan section can be derived from the care plan
discussion.

Figure 1: A de-identified patient-medical professional dialog color-coded with
the predictions from our approach (best seen in color). Notice how different
multiple labels may be present in the same turn of the conversation.

Similar to medical SOAP note (Podder et al., 2021) sections, we consider
labeling each medical professional written sentence into the following
functional sections:

  1. 1.

History taking: questions about the patient’s current illness including
symptoms, prior medical history, and medications they may be taking.

  2. 2.

Summarization: medical professional’s confirmation of relevant patient
symptomatology.

  3. 3.

Education: education of the patient about their medical issues.

  4. 4.

Care plan: suggestion on the course of action or treatments.

  5. 5.

Other: non-medical text.

Figure 1 shows an abridged dialogue that is color-coded with appropriate
section labels, as predicted by the model introduced in this paper. We make
two observations. First, within a single turn of the dialogue, multiple
functional sections (or classes) can co-occur e.g. educating the patient that
purple feet are a diabetes-related symptom while taking history on whether the
patient has been previously diagnosed with diabetes. Second, dialogue
sentences belonging to different functional sections may have high lexical
overlap, e.g. purple feet being discussed in the context of history taking,
summarization, and education.

We formulate the problem of inferring conversation functional sections as
sentence-level classification: Given a medical professional-patient dialogue,
how can we assign every sentence in every turn of the dialogue to the correct
functional section? Further, How can we learn such a model when we can get
only small amounts of human-generated labels?

We tackle both these questions by leveraging two key insights:

  1. 1.

_Dialogue turns carry more information than individual sentences and are thus
easier to learn with weak supervision._ We use this insight to build a noisy
turn-level labels dataset and train a language model to classify turn-level
labels. We then apply the turn level model to label individual sentences
within the turn, creating noisy sentence-level labels.

  2. 2.

_Text embeddings learned from noisy labeled data are relevant even when the
classifications are not reliable._ We use this insight to propose an iterative
human-in-the-loop cluster-based pseudo-labeling strategy. Our proposed
clustering strategy introduces variability in samples across iterations by
enabling intermixing high-confidence predictions with low-confidence ones and
choosing only class-specific ‘pure’ clusters through a simple human-in-the-
loop evaluation.

We evaluate the results on an expert-annotated dataset of 100 dialogues and
find that although the initial pseudo-labels have an accuracy of 69.5%, our
iterative refinement approach can boost accuracy to 82.5%. We also find that
the latent space representations of each class become both more tightly
clustered and more separable between different classes, which may imply higher
generalizability (Li et al., 2020).

##  2 Related Work

#### Semantic structure understanding:

The importance of identifying and assigning labels to functionally coherent
units is well-understood. As an example, in legal document understanding,
Saravanan et al. (2008); Malik et al. (2021) show that it’s easier for
downstream tasks if documents are segmented into coherent units such as facts,
arguments, statutes, etc. In conversational dialogues, the problem of
utterance-level intent classification to detect discourse boundaries is well
studied (Liu et al., 2017; Raheja and Tetreault, 2019; Qu et al., 2019; Joty
et al., 2014; Takanobu et al., 2018). These intents are broad (e.g.“original
question” and “repeat question” Qu et al. (2019)) and identified at turn-
level.

We are interested in classifying dialogue turns and also each sentence within
a turn into functional sections (history taking, summary, education, care
plan, other) that can loosely serve as intents. These sections interleave
(e.g. history taking and education) within a single dialogue turn making the
task challenging. Previous works assume access to manually labeled data. In
this paper, we bootstrap data using a weak pseudo-labeler and then iteratively
refine it with training text-classification models, clustering their
embeddings, and relabeling entire clusters using a human-in-the-loop.

#### Active learning:

This approach focuses on starting with a small labeled dataset and iteratively
retraining models with an updated labeled dataset (see references in survey
papers Settles (2009) and Ren et al. (2020)). Each update to the labeled
training set involves getting manual labels for a small (often only one)
number of most informative examples - examples of which the model at the
previous iteration is most uncertain.

In contrast, our human-in-the-loop approach aims to change labels in a much
larger number of examples in each turn. We cluster the embeddings of the
examples based on the current model, get cluster-level annotation from the
human annotators, and impute that label to all the examples of the cluster. Of
related is the work of Mottaghi et al. (2020) that uses clustering within the
active learning framework, but the technique was used to only identify
previously unseen classes and to obtain a small number of informative examples
within each cluster to increase coverage.

#### Pseudo-labeling:

Another approach to impute labels to a large number of unlabeled examples is
to (Mindermann et al., 2021; Du et al., 2020; Chen et al., 2020) use a trained
model’s prediction to self-label (self-training or pseudo-labeling hyun Lee
(2013)).

Du et al. (2020) shows that self-training with pseudo-labeling can improve
performance on text classification benchmarks without the need for in-domain
unlabeled data. While being general and domain-agnostic, pseudo-labeling
approaches can under-perform if the generated labels are noisy (e.g., high
variance model in the previous iteration of training) and hence adversely
affect performance (c.f. (Oliver et al., 2018; Rizve et al., 2021; Nair et
al., 2021) and references therein). In this paper, we combine pseudo-labeling
followed by independent clustering of the pseudo-labeled-class specific data
points. Human experts then annotate samples from each cluster to either
relabel the entire cluster or remove it from the next training iteration
(because it contains sentences from multiple functional sections).

##  3 Approach

In this section, we present a general description of our approach. We describe
the specifics of applying this approach to medical conversations in § 4.

Symbol |  Description
---|---
$D$ |  Dialogue
$T_{i}$ |  i’th turn of the dialogue
$S_{ij}$ |  j’th sentence in the i’th turn of the dialogue
$\mathcal{L}$ |  Universe of labels
$L^{\textnormal{turn}}_{i}$ |  Turn level functional section label of the i’th turn
$L^{k}_{ij}$ |  k’th iteration sentence level functional section label of i’th turn and j’th sentence
$M_{turn}$ |  Text classification model trained on turn level functional section labels
$M_{\textnormal{sent}}^{k}$ |  k’th iteration text classification model trained on sentence level functional section labels
$\hat{L}^{k}_{ij}$ |  Estimated labels for $S_{ij}$ produced by $M_{\textnormal{sent}}^{k}$
$E^{k}_{ij}$ |  Embedding of the $S_{ij}$ by $M_{\textnormal{sent}}^{k}$
Clst |  Clustering algorithm applied independently to embeddings $E$ for each functional section in $\mathcal{L}$
$C^{k}_{ij}$ |  Cluster assigned to $S_{ij}$ by Clst using embeddings and labels produced by $M_{\textnormal{sent}}^{k}$.
$H$ |  Human annotator that reviews a set of sentences and assigns the set one of the labels in $\mathcal{L}$ or marks them as “Mixed”
$L_{n}^{\textnormal{clst}}$ |  A label applied to all sentences of cluster $n$ (e.g. $C^{k}_{ij}=n$)
Table 1: Notation used in this paper.

Figure 2 presents a schematic overview of our approach. It consists of two
parts. First, in turn-to-sentence label bootstrapping, we pseudo-label turn-
level labels 111We use labels and functional sections interchangeably based on
the context which we use to train a text classification model. We then apply
this model to sentences to create noisy sentence-level labels (§ 3.1). Second,
we iterate on sentence-level labels by training a text classification model,
clustering the sentence-level embeddings, and then using a human-in-the-loop
to classify the sentences of each cluster (§ 3.2). The notation used in this
paper is described in Table 1.

###  3.1 Turn-to-sentence label bootstrapping

Figure 2: Schematic of the approach. The output of this approach is both the
labeled dataset (after step f), and a classification model (step d).

In this step, we train a turn-based model (Figure 2b) to serve as the noisy
pseudo-labeling for sentence-level labeling. We use a set of weak labelers to
generate a turn level multilabel dataset for this task (Figure 2a) of the
form: $L^{\textnormal{turn}}_{i}=\cup_{j}L_{ij}$.

$L^{\textnormal{turn}}$ are used to train a turn-level multilabel model
$M_{\textnormal{turn}}$ (Figure 2b). $M_{\textnormal{turn}}$ is then used to
generate sentence-level labels by applying directly on sentences instead of
entire turns, $L^{0}_{ij}\leftarrow M_{\textnormal{turn}}(S_{ij},D)$ (Figure
2c). Note that in § 4.2 we discuss how, in our application, we still find it
useful to apply (simple) rules on top of trained model output.

###  3.2 Iterative sentence label refinement

The iterative refinement starts with training a sentence-level text
classification model (Figure 2d), which is then used to produce both estimated
labels and embedding $(\hat{L}^{k}_{ij},E^{k}_{ij})$. These embeddings are
clustered independently for each functional section label (Figure 2e), and
then each cluster, as a whole, is relabeled by a human annotator (Figure 2f).
Examples from clusters that contain sentences belonging to different
functional sections (as judged by a human annotator and marked as “Mixed”) are
not used in the next iteration of retraining. See algorithm 1 for details.

Input : Dialogue dataset $\mathcal{D}$

Current iter. model $M^{k}_{\textnormal{sent}}$

Current iter. pseudo-labels $L^{k}_{ij}$

Clustering algorithm Clst

Cluster annotator $H$

1

Output : $\\{L^{k+1}_{ij}\\}$

2

3$None$

4{∀D∈D,∀Sij∈D,Mksent(Sij,D)}

5

6$\\{C_{ij}^{k}\\}\leftarrow\textnormal{Clst}(\\{(\hat{L}^{k}_{ij},E^{k}_{ij})\\})$

7

8$\\{S_{ij}\\}_{n}\leftarrow\textnormal{Sample}(\\{S_{ij}:C^{k}_{ij}=n\\})$

9

10$L^{\textnormal{clst}}_{n}=H(\\{S_{ij}\\}_{n})$

11

12$L^{k+1}_{ij}\leftarrow L^{clst}_{n}:n=C^{k}_{ij}$

13return $\\{L^{k+1}_{ij}:L^{k+1}_{ij}\neq\textnormal{Mixed}\\}$

Algorithm 1 Pseudocode for iterative cluster refinement of sentence level
models. Sample function draws a small number of examples (e.g. 10) from a set.
“Mixed” represents that the set of sentences has sentences that pertain to
several different functional sections.

##  4 Experimental details

###  4.1 Dataset

We use a dataset with 60,000 medical professional-patient encounters
containing over 900,000 dialogue turns and 3,000,000 sentences collected on
Curai Health virtual primary care platform. To construct a test set, we
randomly sampled 100 encounters (not used for training or validation) for
which we procured human labels for all medical professional written sentences
(3,102 sentences). In the human-labeled dataset, the distribution of sections
on the sentence and turn levels are respectively: summarization: 3.6%, 2.6%;
history taking: 26.5%, 31.7%; education: 5.3%, 8.4%; care plan: 4.1%, 7.9%;
other: 60.3%, 49.3%. We do not have any additional labels for these
encounters.

###  4.2 Turn-to-sentence label bootstrapping

As described in § 3.1, we first generate a dataset using ad hoc methods to
train a turn level multilabel classification model. We then use this model to
pseudo-label individual sentences.

#### Unsupervised clustering and human annotation of clusters.

We embed dialogue turns into fixed-sized representations by mean-pooling the
final layer of the off-the-shelf DeCLUTR222We also tried BioBERT (Lee et al.,
2019), Mirror-BERT (Liu et al., 2021), and Sentence BERT (Reimers and
Gurevych, 2019), but found that DeCLUTR produces representations that cluster
with high label-purity (Giorgi et al., 2021) sentence encoder. Following
Allaoui et al. (2020), we project the 768D original embedding space to 250D
via PCA and then project via UMAP (McInnes et al., 2018) to 50D. We then
cluster these 50D representations using the k-means++ algorithm (Arthur and
Vassilvitskii, 2007) and determine the number of clusters using the elbow
method (Thorndike, 1953) (in our dataset, this number was 10). Human
annotators manually label the resulting clusters by examining a small number
($\sim$ 10) of sentences in each cluster Figure B.1.

#### Human annotation of a cluster-derived set of examples.

Because the unsupervised clustering did not produce good clusters containing
only education or care plan turns, we procured human labels for 5000 turns
from a mixed cluster containing education and care plan turns.

#### String-based rules.

We identify turns with summarization sentences by string matching one of
[’summar’, ’sum up’].

#### Turn-level model to generate sentence pseudo-labels.

We construct the dataset for the turn-level model by assigning the same label
as the cluster after removing all mixed clusters. We then train
$M_{\textnormal{turn}}$, a multi-label classifier on top of DeCLUTR using this
turn-level labeled set. The classification head consists of a single feed-
forward layer with sigmoidal activation for each label.

To create the initial sentence level labels, we apply the turn-level model on
each sentence and assign labels according to algorithm 2 in the Appendix.

Round transition 1→2 2→3 3→4 History taking - 1/10→M 3/10→M Summarization
2/10→M 1/10→M 3/10→M 1/10→O Education 1/10→M 6/10→M 3/10→M 1/10→O Care plan
1/10→M 3/10→M 6/10→M Other (O) 7/15→M 3/10→M 6/10→M

Table 2: Cluster relabeling between rounds. Elements of the table correspond
to how many clusters of a given semantic class were re-labeled as (O)ther or
(M)ixed.

###  4.3 Iterative sentence label refinement

#### Sentence-level model.

The input to this model is the dialogue turn that contains the target
sentence. We mark the target sentence with tokens ⟨START⟩ and ⟨END⟩. The model
itself consists of a transformer language model DeCLUTR sentence encoder, with
a classification head consisting of a single feed-forward layer with a softmax
activation.

#### Clustering sentence-level model.

To cluster sentence-level embeddings, we use a similar approach to the one
described in turn-level clustering (§ 4.2). The only difference is that we use
the predicted labels to constrain that the kmeans++ algorithm is independently
applied to examples corresponding to each predicted label. As an example,
Figure B.1 in the Appendix shows the visualization of clusters predicted to be
part of ”Summarization.” Each cluster is manually assigned its label (often
simply staying with the original predicted label) by examining about ten data
points (sentences).

#### Details of relabeling between rounds.

Table 2 shows the number of clusters relabeled and the new label assigned. We
can see that most relabeling was moving clusters to the “Mixed” label, thereby
ensuring that we improve the ‘purity’ of the pseudo-labels. Examples with the
“Mixed” label are not used for the subsequent round of model training.
However, they would still be used for subsequent clustering and relabeling.
This strategy of relabeling also helps to mix high-confidence predictions with
low-confidence ones, as long as they are close in the embedding
representations.

###  4.4 Implementation details

All models discussed are trained in Pytorch 1.10.2+cu102 with the language
models implemented using HuggingFace Transformers library (Wolf et al., 2019).
The weights for the DeCLUTR models were using the johngiorgi/declutr-base
checkpoint. For training, we used the Adam optimizer with learning rate
$2e^{-5}$ and a scheduler with warm-up steps of $\text{total training
steps}/5$. We set the batch size as 12. PCA and kmeans were implemented using
scikit-learn 0.24.2 package, while UMAP used the umap-learn 0.5.1 package.

##  5 Results

Figure 3: Cosine similarity of same- and different- class pairs for each class
Figure 4: Improvement in label purity with each round (§ 5.1). Columns
represent human-assigned true labels. Each row represents the proportion of
the predicted labels as represented by the proportion of the color. The larger
the proportion of the color corresponding to the column name, the better is
the model improvement.

| F1 score
---|---
Class | Round 1 | Round 2 | Round 3 | Round 4
Summarization | 0.18$\pm$0.00 | 0.19$\pm$0.11 | 0.47$\pm$0.06 | 0.65$\pm$0.02
History Taking | 0.89$\pm$0.01 | 0.9$\pm$0.00 | 0.92$\pm$0.00 | 0.93$\pm$0.01
Education | 0.70$\pm$0.01 | 0.69$\pm$0.02 | 0.69$\pm$0.02 | 0.65$\pm$0.02
Care Plan | 0.55$\pm$0.02 | 0.56$\pm$0.03 | 0.57$\pm$0.01 | 0.55$\pm$0.02
Other | 0.90$\pm$0.00 | 0.92$\pm$0.00 | 0.93$\pm$0.00 | 0.93$\pm$0.00
Multi-class Accuracy* | 69.5%$\pm$0.00 | 74.1%$\pm$0.00 | 80.4%$\pm$0.01 | 82.5%$\pm$0.01
* Accuracy is on the four functional classes only

Table 3: Sentence-level model performance: F1 scores and accuracy after each
round of iterative training. Standard deviations by retraining models with
different seeds.

| F1 score
---|---
Class | Turn-level | Round 1 | Round 2 | Round 3 | Round 4
Summarization | 0.22$\pm$0.00 | 0.22$\pm$0.00 | 0.25$\pm$0.03 | 0.69$\pm$0.04 | 0.66$\pm$0.04
History Taking | 0.37$\pm$0.00 | 0.84$\pm$0.02 | 0.83$\pm$0.01 | 0.86$\pm$0.01 | 0.87$\pm$0.01
Education | 0.61$\pm$0.01 | 0.77$\pm$0.02 | 0.69$\pm$0.05 | 0.73$\pm$0.02 | 0.65$\pm$0.04
Care Plan | 0.31$\pm$0.04 | 0.55$\pm$0.02 | 0.55$\pm$0.03 | 0.57$\pm$0.01 | 0.51$\pm$0.02
Other | 0.75$\pm$0.00 | 0.89$\pm$0.01 | 0.93$\pm$0.00 | 0.95$\pm$0.01 | 0.95$\pm$0.00
Binary Accuracy | 84.7%$\pm$0.00 |  95.6%$\pm$0.00 | 95.2%$\pm$0.01 |  95.6%$\pm$0.00 | 94.9%$\pm$0.00
* Accuracy is on the four functional classes only

Table 4: Turn-based inference improved with sentence-level model ( § 5.2). The
column “Turn-level” is the initial turn-level model from which sentence level
model was bootstrapped. Columns Round 1–4 show the F1-score when we pool
sentence-level predictions to produce turn level labels. The standard
deviations are derived by retraining models with different seeds.

###  5.1 Main result: Sentence-level model performance

Table 4 provides our main results, comparing F1 and accuracy scores from each
training round of the sentence-level model. The overall performance increased
from accuracy of 69.5% to 82.5%. The “Summarization” class has the most
improvement (F1 score from 0.18 to 0.65). This three-fold improvement of the
F1 score shows that our iterative approach can improve labeling quality (and
hence the model) even when the initial labels are noisy. The sentences in this
class are hard to identify solely from the turn-level-model-based pseudo-
labeling. The pseudo-labeler successfully labels the sentences that contain
“to summarize” but fails on e.g. ”he experiences no pain.” However, our
iterative clustering-based labeling introduces less-confident predictions that
are semantically similar to the more confident ones to improve the overall
identifiability.

Figure 4 provides a graphical representation of the errors the model makes.
Each column represents the human-assigned true label, and each row represents
the proportion of the predicted labels in each true label for each training
round. The two classes that see the F1 score uplift, “History taking” and
“Summarization”, start with a significant confusion with the “Other” class,
which gradually decreases. Even though the additional iterations did not
improve the “Care plan” and “Education” classes, their overall confusion
changed between rounds. Initially, both “Education” and “Care plan” were
confused with the “Other” class, while in later rounds, they were confused
with each other. We expect this inter-class confusion as they can be hard to
differentiate even for human annotators, e.g. “It is recommended that a person
having a fever should drink more water.” could be annotated as either
“Education” or “Care plan”, depending on the context.

Figure 3 sheds light on another perspective on the change in the quality of
the embeddings of the sentence-level models. Here, at every round, we randomly
sampled 1,000 examples for each predicted class and used their embeddings to
compute the distribution of cosine similarities between pairs of the same
class (“self”) and pairs of different classes (“other”). The distributions are
always bimodal, but the full width at half max of the peaks decreases. Even
for classes where the F1 metrics did not improve, there is an increase in the
‘peakiness” of the two distributions, making them more separable. This is the
separation between positive and negative contrastive learning examples, where
recent literature on sentence embeddings (Li et al., 2020; Liu et al., 2021)
suggests that the increased separation corresponds to better generalization
performance.

###  5.2 Can we obtain a better turn-level inference using the sentence-level
model?

In the previous experiments, we evaluated the output of the sentence-level
model for each sentence in the input. Here, we investigate if training models
at the sentence level also improve turn-level performance. For this, we max
pool the predictions of all the sentences in a turn. For comparison, we use
the initial turn level model (§ 3.1) as the baseline.

Table 4 shows the F1 and accuracy scores of the sentence-aggregated turn-level
predictions. Like the sentence-level models, we see the most marked
improvement in the “Summarization” class. Note how the Round 1 sentence-level
model outperforms the turn-level model even though the turn-level model is
used to generate the sentence-level pseudo-labels at the beginning with no
human relabeling. This suggests that the sentence-level model can learn better
semantics that the turn-level model.

Overall, the improvement from the later rounds is less pronounced at the turn
level. While sentence-level evaluation benefits from multiple rounds of
disentangling the class confusion between sentences within a turn, this is
less of a concern for turn-level evaluation. This is also evidenced by overall
higher F1 scores when compared to evaluation at the sentence level in Table 4.
The improved performance and decreased effect from additional iterations is
likely because the sentences that are more difficult to classify into a
particular class tend to appear in mixed class turns and therefore doing well
on these sentences does not improve turn-level metrics.

##  6 Discussion

We proposed a method for automatically inferring functional sections of a
patient-medical professional dialogue with minimal human supervisory data.
While we focused on the four dominant medically relevant functional sections,
“History taking”, “Summarization,” “Education,” and “Care plan” along with a
background (“Other”) class, the approach can be easily extended to additional
classes.

Starting with very little annotated data, we build a highly accurate model
using a human-in-the-loop cluster-based pseudo-labeling strategy. We show that
the approach increases embedding anisotropy, effectively increasing the
contrast between labels. We think this is because our approach intermixes high
and low-confidence predictions which are then relabeled on a per-cluster basis
through a simple human-in-the-loop evaluation. This makes our label-refinement
strategy potentially useful for other applications, where the starting pseudo-
labels are noisy or insufficient to capture the data variability, and getting
additional human labels is expensive.

#### Ethics

This work was done as part of a quality improvement activity as defined in
45CFR §46.104(d)(4)(iii) – secondary research for which consent is not
required for the purposes of “health care operations.” All human annotators
were full-time employees of the company while performing this work.

## References

  * Allaoui et al. (2020) Mebarka Allaoui, Mohammed Lamine Kherfi, and Abdelhakim Cheriet.  Considerably improving clustering algorithms using umap dimensionality reduction technique: A comparative study.  In Abderrahim El Moataz, Driss Mammass, Alamin Mansouri, and Fathallah Nouboud, editors, _Image and Signal Processing_ , pages 317–325, Cham, 2020. Springer International Publishing.  ISBN 978-3-030-51935-3.
  * Arthur and Vassilvitskii (2007) David Arthur and Sergei Vassilvitskii.  k-means++: the advantages of careful seeding.  In _SODA ’07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms_ , pages 1027–1035, Philadelphia, PA, USA, 2007\. Society for Industrial and Applied Mathematics.  ISBN 978-0-898716-24-5.
  * Bestsennyy et al. (2021) Oleg Bestsennyy, Greg Gilbert, Alex Harris, and Jennifer Rost.  Telehealth: A quarter-trillion-dollar post-covid-19 reality?  https://tinyurl.com/2ead8992, 2021.  [Online; accessed 31-March-2022].
  * Chen et al. (2020) Jiaao Chen, Zichao Yang, and Diyi Yang.  Mixtext: Linguistically-informed interpolation of hidden space for semi-supervised text classification.  _CoRR_ , abs/2004.12239, 2020.  URL https://arxiv.org/abs/2004.12239.
  * Dreisbach et al. (2019) Caitlin Dreisbach, Theresa A Koleck, Philip E Bourne, and Suzanne Bakken.  A systematic review of natural language processing and text mining of symptoms from electronic patient-authored text data.  _International journal of medical informatics (Shannon, Ireland)_ , 125:37–46, 2019.  ISSN 1386-5056.
  * Du et al. (2020) Jingfei Du, Edouard Grave, Beliz Gunel, Vishrav Chaudhary, Onur Celebi, Michael Auli, Ves Stoyanov, and Alexis Conneau.  Self-training improves pre-training for natural language understanding.  _CoRR_ , abs/2010.02194, 2020.  URL https://arxiv.org/abs/2010.02194.
  * Giorgi et al. (2021) John Giorgi, Osvald Nitski, Bo Wang, and Gary Bader.  DeCLUTR: Deep contrastive learning for unsupervised textual representations.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 879–895, Online, August 2021. Association for Computational Linguistics.  10.18653/v1/2021.acl-long.72.  URL https://aclanthology.org/2021.acl-long.72.
  * hyun Lee (2013) Dong hyun Lee.  Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks, 2013.
  * Joshi et al. (2020) Anirudh Joshi, Namit Katariya, Xavier Amatriain, and Anitha Kannan.  Dr. summarize: Global summarization of medical dialogue by exploiting local structures.  _EMNLP-Findings_ , 2020.
  * Joty et al. (2014) Shafiq Rayhan Joty, Giuseppe Carenini, and Raymond T. Ng.  Topic segmentation and labeling in asynchronous conversations.  _CoRR_ , abs/1402.0586, 2014.
  * Khosla et al. (2020) Sopan Khosla, Shikhar Vashishth, Jill Lehman, and Carolyn Rose.  Medfilter: Improving extraction of task-relevant utterances through integration of discourse structure and ontological knowledge.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 7781–7797, 01 2020.  10.18653/v1/2020.emnlp-main.626.
  * Krishna et al. (2021) Kundan Krishna, Sopan Khosla, Jeffrey P. Bigham, and Zachary Chase Lipton.  Generating soap notes from doctor-patient conversations using modular summarization techniques.  In _ACL_ , 2021.
  * Lee et al. (2019) Jinhyuk Lee, Wonjin Yoon, Sungdong Kim, Donghyeon Kim, Sunkyu Kim, Chan Ho So, and Jaewoo Kang.  BioBERT: a pre-trained biomedical language representation model for biomedical text mining.  _Bioinformatics_ , 36(4):1234–1240, 09 2019.  ISSN 1367-4803.  10.1093/bioinformatics/btz682.  URL https://doi.org/10.1093/bioinformatics/btz682.
  * Li et al. (2020) Bohan Li, Hao Zhou, Junxian He, Mingxuan Wang, Yiming Yang, and Lei Li.  On the sentence embeddings from pre-trained language models.  In _EMNLP_ , 2020.
  * Liu et al. (2021) Fangyu Liu, Ivan Vulić, Anna Korhonen, and Nigel Collier.  Fast, effective, and self-supervised: Transforming masked language models into universal lexical and sentence encoders.  In _EMNLP 2021_ , 2021.
  * Liu et al. (2017) Yang Liu, Kun Han, Zhao Tan, and Yun Lei.  Using context information for dialog act classification in DNN framework.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, 2017\.
  * Malik et al. (2021) Vijit Malik, Rishabh Sanjay, Shouvik Kumar Guha, Shubham Kumar Nigam, Angshuman Hazarika, Arnab Bhattacharya, and Ashutosh Modi.  Semantic segmentation of legal documents via rhetorical roles.  _ArXiv_ , abs/2112.01836, 2021.
  * McInnes et al. (2018) Leland McInnes, John Healy, Nathaniel Saul, and Lukas Großberger.  Umap: Uniform manifold approximation and projection.  _Journal of Open Source Software_ , 3(29):861, 2018.  10.21105/joss.00861.  URL https://doi.org/10.21105/joss.00861.
  * Mindermann et al. (2021) Sören Mindermann, Muhammed Razzak, Winnie Xu, Andreas Kirsch, Mrinank Sharma, Adrien Morisot, Aidan N Gomez, Sebastian Farquhar, Jan Brauner, and Yarin Gal.  Prioritized training on points that are learnable, worth learning, and not yet learned.  _arXiv preprint arXiv:2107.02565_ , 2021.
  * Mottaghi et al. (2020) Ali Mottaghi, Prathusha K. Sarma, Xavier Amatriain, Serena Yeung, and Anitha Kannan.  Medical symptom recognition from patient text: An active learning approach for long-tailed multilabel distributions.  _CoRR_ , abs/2011.06874, 2020.
  * Nair et al. (2021) Varun Nair, Namit Katariya, Xavier Amatriain, Ilya Valmianski, and Anitha Kannan.  Adding more data does not always help: A study in medical conversation summarization with PEGASUS.  _CoRR_ , abs/2111.07564, 2021.  URL https://arxiv.org/abs/2111.07564.
  * Oliver et al. (2018) Avital Oliver, Augustus Odena, Colin Raffel, Ekin D. Cubuk, and Ian J. Goodfellow.  Realistic evaluation of deep semi-supervised learning algorithms.  _CoRR_ , abs/1804.09170, 2018.
  * Podder et al. (2021) Vivek Podder, Valerie Lew, and Sassan Ghassemzadeh.  Soap notes.  In _StatPearls_ , page https://www.ncbi.nlm.nih.gov/books/NBK482263/. Treasure Island (FL): StatPearls Publishing, 2021.  [Online; accessed 31-March-2022].
  * Qu et al. (2019) Chen Qu, Liu Yang, W. Bruce Croft, Yongfeng Zhang, Johanne R. Trippas, and Minghui Qiu.  User intent prediction in information-seeking conversations.  _CoRR_ , abs/1901.03489, 2019.
  * Raheja and Tetreault (2019) Vipul Raheja and Joel Tetreault.  Dialogue Act Classification with Context-Aware Self-Attention.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , Minneapolis, Minnesota, 2019\. Association for Computational Linguistics.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych.  Sentence-BERT: Sentence embeddings using Siamese BERT-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3982–3992, Hong Kong, China, November 2019. Association for Computational Linguistics.  10.18653/v1/D19-1410.  URL https://aclanthology.org/D19-1410.
  * Ren et al. (2020) Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B. Gupta, Xiaojiang Chen, and Xin Wang.  A survey of deep active learning, 2020.
  * Rizve et al. (2021) Mamshad Nayeem Rizve, Kevin Duarte, Yogesh S. Rawat, and Mubarak Shah.  In defense of pseudo-labeling: An uncertainty-aware pseudo-label selection framework for semi-supervised learning.  _CoRR_ , abs/2101.06329, 2021.
  * Saravanan et al. (2008) M. Saravanan, B. Ravindran, and S. Raman.  Automatic identification of rhetorical roles using conditional random fields for legal document summarization.  In _Proceedings of the Third International Joint Conference on Natural Language Processing: Volume-I_ , 2008.  URL https://aclanthology.org/I08-1063.
  * Settles (2009) Burr Settles.  Active learning literature survey.  Technical report, University of Wisconsin-Madison Department of Computer Sciences, 2009.
  * Takanobu et al. (2018) Ryuichi Takanobu, Minlie Huang, Zhongzhou Zhao, Fenglin Li, Haiqing Chen, Xiaoyan Zhu, and Liqiang Nie.  A weakly supervised method for topic segmentation and labeling in goal-oriented dialogues via reinforcement learning.  In _Proceedings of the 27th International Joint Conference on Artificial Intelligence_ , page 4403–4410, 2018.
  * Thorndike (1953) Robert L. Thorndike.  Who belongs in the family.  _Psychometrika_ , pages 267–276, 1953.
  * Valmianski et al. (2021) Ilya Valmianski, Nave Frost, Navdeep Sood, Yang Wang, Baodong Liu, James J. Zhu, Sunil Karumuri, Ian M. Finn, and Daniel S. Zisook.  Smarttriage: A system for personalized patient data capture, documentation generation, and decision support.  In _Proceedings of Machine Learning for Health_ , volume 158 of _Proceedings of Machine Learning Research_ , pages 75–96. PMLR, 04 Dec 2021\.  URL https://proceedings.mlr.press/v158/valmianski21a.html.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew.  Huggingface’s transformers: State-of-the-art natural language processing.  _ArXiv_ , abs/1910.03771, 2019.

##  Appendix A Application of turn-level model on sentences

Input : Dialogue turns $\\{T_{j}\\}$

Sentences $S_{jk}\in T_{j}$

Universe of labels $\mathcal{L}$

Model $M_{\textnormal{turn}}(T_{j})$ for estimating section probability
$P(L=L_{i}|T_{j}),L_{i}\in\mathcal{L}$

Output : Sentence level labels $L_{jk}\in\mathcal{L}$

1

2$L_{\textnormal{turn},j}\leftarrow\\{l\in\mathcal{L}:P(L=l|T_{j})>\alpha_{1}\\}$
;

3

4$L_{\textnormal{filter},j}\leftarrow\\{l\in\mathcal{L}:P(L=l|T_{j})>\alpha_{2}\\}$
;

5

6foreach  _$S_{jk}\in T_{j}$_ do

7 if  _$\textnormal{‘summarization’}\in L_{\textnormal{turn},j}$_ then

8 $L_{jk}\leftarrow\textnormal{‘summarization’}$;

9

10 end if

11 else if  _$P(L=\textnormal{“history taking”}|S_{jk})\geq\alpha_{3}$_ then

12 $L_{jk}\leftarrow\textnormal{‘history taking’}$

13 end if

14 else if  _$P(L=\textnormal{“education”}|S_{jk})\geq\alpha_{3}$_ then

15 $L_{jk}\leftarrow\textnormal{‘education’}$

16 end if

17 else if  _$P(L=\textnormal{“care plan”}|S_{jk})\geq\alpha_{3}$_ then

18 $L_{jk}\leftarrow\textnormal{‘care plan’}$

19 end if

20 else

21
$l_{\textnormal{candidate}}\leftarrow\operatorname*{arg\,max}_{c}P(L=l|S_{jk}),l\in
L_{\textnormal{filter},j}$ ;

22

23 $L_{jk}\leftarrow l_{\textnormal{candidate}}\textnormal{ if
}P(L=l_{\textnormal{candidate}}|S_{jk})>\alpha_{1}\textnormal{ else
}\textnormal{“other”}$

24 end if

25

26 end foreach

27

28return $L_{jk}$

Algorithm 2 Pseudocode for applying the turn-level model to create sentence-
level labels

Where $\alpha_{1}=0.5$, $\alpha_{2}=0.1$, and $\alpha_{3}=0.9$. The values
were determined by an informal human evaluation of the pseudolabeling
performance.

##  Appendix B Example of Clustering outputs

Figure B.1: Clustering of Sentences Predicted as “Summarization” after the
First Round of Training

##  Appendix C Examples of Encounters with Color-coded Model-generated
Predictions

As our model is trained on predicting professionals’ sentences, only the
professionals’ sentences are color-coded here.

Figure C.1: Sample Encounter 1 Figure C.2: Sample Encounter 2 Figure C.3:
Sample Encounter 3 Figure C.4: Sample Encounter 4