# Polynomial Identification of $\omega$-Automata

Dana Angluin  Yale UniversityNew Haven, CTUSA<EMAIL_ADDRESS>,  Dana
Fisman  Ben-Gurion UniversityBe’er-ShevaIsrael<EMAIL_ADDRESS>and  Yaara
Shoval  Ben-Gurion UniversityBe’er-ShevaIsrael<EMAIL_ADDRESS>
(2022)

###### Abstract.

We study identification in the limit using polynomial time and data for models
of $\omega$-automata. On the negative side we show that non-deterministic
$\omega$-automata (of types Büchi, coBüchi, Parity, Rabin, Street, or Muller)
cannot be polynomially learned in the limit. On the positive side we show that
the $\omega$-language classes $\mathbb{IB}$, $\mathbb{IC}$, $\mathbb{IP}$,
$\mathbb{IR}$, $\mathbb{IS}$, and $\mathbb{IM}$, which are defined by
deterministic Büchi, coBüchi, Parity, Rabin, Streett, and Muller acceptors
that are isomorphic to their right-congruence automata, are identifiable in
the limit using polynomial time and data.

We give polynomial time inclusion and equivalence algorithms for deterministic
Büchi, coBüchi, Parity, Rabin, Streett, and Muller acceptors, which are used
to show that the characteristic samples for $\mathbb{IB}$, $\mathbb{IC}$,
$\mathbb{IP}$, $\mathbb{IR}$, $\mathbb{IS}$, and $\mathbb{IM}$ can be
constructed in polynomial time.

We also provide polynomial time algorithms to test whether a given
deterministic automaton of type $\mathbb{X}$ (for
$\mathbb{X}\in\\{\mathbb{B},\mathbb{C},\mathbb{P},\mathbb{R},\mathbb{S},\mathbb{M}\\}$)
is in the class $\mathbb{IX}$ (i.e. recognizes a language that has a
deterministic automaton that is isomorphic to its right congruence automaton).

This is an extended version of a paper with the same name that appeared in
TACAS’20 (Angluin et al., 2020b).

††copyright: acmcopyright††journalyear: 2022††doi: XXXXXXX.XXXXXXX

##  1\. Introduction

With the growing success of machine learning in efficiently solving a wide
spectrum of problems, we are witnessing an increased use of machine learning
techniques in formal methods for system design. One thread in recent
literature uses general purpose machine learning techniques for obtaining more
efficient verification/synthesis algorithms. Another thread, following the
_automata theoretic approach to verification_ (Vardi, 1995; Kupferman et al.,
2000) works on developing grammatical inference algorithms for verification
and synthesis purposes. _Grammatical inference_ (aka _automata learning_)
refers to the problem of automatically inferring from examples a finite
representation (e.g. an automaton, a grammar, or a formula) for an unknown
language. The term _model learning_ (Vaandrager, 2017) was coined for the task
of learning an automaton model for an unknown system. A large body of works
has developed learning techniques for different automata types (e.g. I/O
automata (Aarts and Vaandrager, 2010), register automata (Howar et al., 2012),
symbolic automata (Drews and D’Antoni, 2017), $\omega$-automata (Angluin and
Fisman, 2014), and program automata (Manevich and Shoham, 2018)) and has shown
its usability in a diverse range of tasks.111E.g., tasks such as black-box
checking (Peled et al., 1999), specification mining (Ammons et al., 2002),
assume-guarantee reasoning (Cobleigh et al., 2003), regular model checking
(Habermehl and Vojnar, 2005), learning verification fixed-points (Vardhan et
al., 2005), learning interfaces (Nam and Alur, 2006), analyzing botnet
protocols (Cho et al., 2010) or smart card readers (Chalupar et al., 2014),
finding security bugs (Chalupar et al., 2014), error localization (Chapman et
al., 2015), and code refactoring (Margaria et al., 2004; Schuts et al., 2016).

In grammatical inference, the learning algorithm does not learn a _language_ ,
but rather a finite _representation_ of it. Complexity of learning algorithms
may vary greatly by switching representations. For instance, if one wishes to
learn regular languages, she may consider representations using deterministic
finite automata (DFAs), non-deterministic finite automata (NFAs), regular
expressions, linear grammars etc. Since the translation results between two
such formalisms are not necessarily polynomial, a polynomial learnability
result for one representation does not necessarily imply a polynomial
learnability result for another representation. Let $\mathbb{C}$ be a class of
representations $\mathcal{C}$ with a size measure $\textit{size}(\mathcal{C})$
(e.g. for DFAs the size measure can be the number of states in the minimal
automaton). We extend $\textit{size}(\cdot)$ to the languages recognized by
representations in $\mathbb{C}$ by defining $\textit{size}(L)$ to be the
minimum of $\textit{size}(\mathcal{C})$ over all $\mathcal{C}$ representing
$L$. In this paper we restrict attention to automata representations, namely,
_acceptors_.

There are various learning paradigms considered in the grammatical inference
literature, roughly classified into _passive_ and _active_. We mention here
the two central ones. In _passive learning_ the model of _learning from finite
data_ refers to the following problem: given a finite sample
$T\subseteq\Sigma^{*}\times\\{0,1\\}$ of labeled words, a learning algorithm
$\mathbf{A}$ should return an acceptor $\mathcal{C}$ that agrees with the
sample $T$. That is, for every $(w,l)\in T$ the following holds:
$w\in{\llbracket}\mathcal{C}{\rrbracket}$ iff $l=1$ (where
${\llbracket}\mathcal{C}{\rrbracket}$ is the language accepted by
$\mathcal{C}$). The class $\mathbb{C}$ is _identifiable in the limit using
polynomial time and data_ if and only if there exists a polynomial time
algorithm $\mathbf{A}$ that takes as input a labeled sample $T$ and outputs an
acceptor $\mathcal{C}\in\mathbb{C}$ that is consistent with $T$, and
$\mathbf{A}$ also satisfies the following condition. If $L$ is any language
recognized by an automaton from class $\mathbb{C}$, then there exists a
labeled sample $T_{L}$ consistent with $L$ of length bounded by a polynomial
in $\textit{size}(L)$, and for any labeled sample $T$ consistent with $L$ such
that $T_{L}\subseteq T$, on input $T$ the algorithm $\mathbf{A}$ produces an
acceptor $\mathcal{C}$ that recognizes $L$. In this case, $T_{L}$ is termed a
_characteristic sample_ for the algorithm $\mathbf{A}$. In some cases (e.g.,
DFAs) there is also a polynomial time algorithm to compute a characteristic
sample for $\mathbf{A}$, given an acceptor $\mathcal{C}\in\mathbb{C}$.

In _active learning_ the model of _query learning_ (Angluin, 1987) assumes the
learner communicates with an _oracle_ (sometimes called _teacher_) that can
answer certain types of queries about the language. The most common type of
queries are _membership queries_ (is $w\in L$ where $L$ is the unknown
language) and _equivalence queries_ (is
${\llbracket}\mathcal{A}{\rrbracket}=L$ where $\mathcal{A}$ is the current
hypothesis for an acceptor recognizing $L$). Equivalence queries are typically
assumed to return a counterexample, i.e. a word in
${\llbracket}\mathcal{A}{\rrbracket}\setminus L$ or in
$L\setminus{\llbracket}\mathcal{A}{\rrbracket}$.

With regard to $\omega$-automata (automata on infinite words) most of the
works consider _query learning_ using _membership queries_ and _equivalence
queries_. The representations learned so far include: $(L)_{\$}$ (Farzan et
al., 2008), a non-polynomial reduction to finite words; families of DFAs
($\mathbb{FDFA}$) (Angluin and Fisman, 2014, 2016; Angluin et al., 2016; Li et
al., 2017); strongly unambiguous Büchi automata ($\mathbb{SUBA}$) (Angluin et
al., 2020a); mod-2-multiplicity automata ($\mathbb{M}$2$\mathbb{MA}$) (Angluin
et al., 2022); and deterministic weak Parity automata ($\mathbb{DWPA}$) (Maler
and Pnueli, 1995). Among these only the latter two are known to be learnable
in polynomial time using membership queries and proper equivalence queries.222
Query learning with an additional type of query, _loop-index queries_ , was
studied for deterministic Büchi automata (Michaliszyn and Otop, 2020).

One of the main obstacles in obtaining a polynomial learning algorithm for
regular $\omega$-languages is that they do not in general have a Myhill-Nerode
characterization; that is, there is no theorem correlating the states of a
minimal automaton of some of the common automata types (Büchi, Parity, Muller,
etc.) to the equivalence classes of the right congruence of the language. The
_right congruence relation_ for an $\omega$-language $L$ relates two finite
words $x$ and $y$ iff there is no infinite suffix $z$ differentiating them,
that is $x\sim_{L}y$ (for $x,y\in\Sigma^{*}$) iff $\forall
z\in\Sigma^{\omega}.\ xz\in L\iff yz\in L$. In our quest for finding a
polynomial query learning algorithm for a subclass of the regular
$\omega$-languages, we have studied subclasses of languages for which such a
relation holds (Angluin and Fisman, 2018), and termed them _fully
informative_. We use
$\mathbb{IB},\mathbb{IC},\mathbb{IP},\mathbb{IR},\mathbb{IS},\mathbb{IM}$ to
denote the classes of languages that are fully informative of type Büchi,
coBüchi, Parity, Rabin, Streett, and Muller, respectively. A language $L$ is
said to be fully informative of type $\mathbb{X}$ for
$\mathbb{X}\in\\{\mathbb{B},\mathbb{C},\mathbb{P},\mathbb{R},\mathbb{S},\mathbb{M}\\}$
if there exists a deterministic automaton of type $\mathbb{X}$ which is
isomorphic to the automaton derived from $\sim_{L}$. While many properties of
these classes are now known, in particular that they span the entire hierarchy
of $\omega$-regular properties (Wagner, 1975), a polynomial learning algorithm
for them is not known.

In this paper we show (in §4-8) that the classes
$\mathbb{IB},\mathbb{IC},\mathbb{IP},\mathbb{IR},\mathbb{IS},\mathbb{IM}$ can
be identified in the limit using polynomial time and data. We further show (in
§9) that there is a polynomial time algorithm to compute a characteristic
sample given an acceptor $\mathcal{C}\in\mathbb{IX}$. A corollary of this
result is that the class of languages accepted by $\mathbb{DWPA}$s (which as
mentioned above is polynomially learnable in the query learning setting) also
has a polynomial size characteristic sample. On the negative side, we show (in
§3) that the classes $\mathbb{NBA}$, $\mathbb{NCA}$, $\mathbb{NPA}$,
$\mathbb{NRA}$, $\mathbb{NSA}$, $\mathbb{NMA}$ of non-deterministic Büchi,
coBüchi, Parity, Rabin, Streett, and Muller automata, respectively, cannot be
identified in the limit using polynomial data.

To obtain the above results we needed a polynomial time algorithm for
inclusion and equivalence of automata in these types. Such an algorithm is
known to exist for the classes $\mathbb{NBA}$, $\mathbb{NCA}$, $\mathbb{NPA}$,
since these classes have inclusion algorithms in NL. For the other classes, we
are not aware of results in the literature showing a polynomial time
algorithm. We provide such algorithms in §10-13.

The last part of this manuscript (§14-15) is devoted to the question of
deciding whether a given automaton $\mathcal{A}$ of type $\mathbb{X}$ that is
isomorphic to its right congruence, or if this is not the case whether there
exists an automaton $\mathcal{A}^{\prime}$ of the same type that recognizes
the same language and is isomorphic to its right congruence, namely whether
the given automaton is in the class $\mathbb{IX}$.

##  2\. Preliminaries

###  2.1. Automata

An _automaton_ is a tuple
$\mathcal{M}=\langle\Sigma,Q,q_{\iota},\delta\rangle$ consisting of a finite
alphabet $\Sigma$ of symbols, a finite set $Q$ of states, an initial state
$q_{\iota}\in Q$, and a transition function ${\delta:Q\times\Sigma\rightarrow
2^{Q}}$. We extend $\delta$ to domain $Q\times\Sigma^{*}$ in the usual way:
$\delta(q,\varepsilon)=q$ and $\delta(q,\sigma
x)=\cup_{q^{\prime}\in\delta(q,\sigma)}\delta(q^{\prime},x)$ for all $q\in Q$
and $\sigma\in\Sigma$.

We define the _size_ of an automaton to be $|\Sigma|\cdot|Q|$. A state $q\in
Q$ is _reachable_ iff there exists $x\in\Sigma^{*}$ such that
$q=\delta(q_{\iota},x)$. For $q\in Q$, $\mathcal{M}^{q}$ is the automaton
$\mathcal{M}$ with its initial state replaced by $q$. We say that
${\mathcal{A}}$ is _deterministic_ if $|\delta(q,\sigma)|\leq 1$ and
_complete_ if $|\delta(q,\sigma)|\geq 1$, for every $q\in Q$ and
$\sigma\in\Sigma$. For deterministic automata we abbreviate
$\delta(q,\sigma)=\\{q^{\prime}\\}$ as $\delta(q,\sigma)=q^{\prime}$. Two
automata $\mathcal{M}$ and $\mathcal{M}^{\prime}$ with the same alphabet
$\Sigma$ are isomorphic if there exists a bijection $f$ from the states $Q$ of
$\mathcal{M}$ to the states $Q^{\prime}$ of $\mathcal{M}^{\prime}$ such that
$f(q_{\iota})=q_{\iota}^{\prime}$ and for every $q\in Q$ and
$\sigma\in\Sigma$, $\\{f(r)\mid
r\in\delta(q,\sigma)\\}=\delta^{\prime}(f(q),\sigma)$.

We assume a fixed total ordering on $\Sigma$, which induces the _shortlex_
total ordering on $\Sigma^{*}$, defined as follows. For $x,y\in\Sigma^{*}$,
$x$ precedes $y$ in the shortlex ordering if $|x|<|y|$ or $|x|=|y|$ and $x$
precedes $y$ in the lexicographic ordering induced by the ordering on
$\Sigma$.

A _run_ of an automaton on a finite word ${v=a_{1}a_{2}\ldots a_{n}}$ is a
sequence of states ${q_{0},q_{1},\ldots,q_{n}}$ such that $q_{0}=q_{\iota}$,
and for each $i\geq 1$, ${q_{i}\in\delta(q_{i-1},a_{i})}$. A _run_ on an
infinite word is defined similarly and consists of an infinite sequence of
states. For an infinite run $\rho=q_{0},q_{1},\ldots$, we define the set of
states visited infinitely often, denoted $\textit{inf}_{\mathcal{M}}(\rho)$,
as the set of $q\in Q$ such that $q=q_{i}$ for infinitely many indices
$i\in\mathbb{N}$. This is abbreviated to ${\textsl{inf}}(\rho)$ if
$\mathcal{M}$ is understood.

##### The Product of Two Automata.

Let ${{\mathcal{M}}}_{1}$ and ${{\mathcal{M}}}_{2}$ be two deterministic
complete automata with the same alphabet $\Sigma$, where for $i=1,2$,
${{\mathcal{M}}}_{i}=\langle\Sigma,Q_{i},(q_{\iota})_{i},\delta_{i}\rangle$.
Their product automaton, denoted
${{\mathcal{M}}}_{1}\times{{\mathcal{M}}}_{2}$, is the deterministic complete
automaton ${\mathcal{M}}=\langle\Sigma,Q,q_{\iota},\delta\rangle$ such that
$Q=Q_{1}\times Q_{2}$, the set of ordered pairs of states of
${{\mathcal{M}}}_{1}$ and ${{\mathcal{M}}}_{2}$,
$q_{\iota}=((q_{\iota})_{1},(q_{\iota})_{2})$, the pair of initial states of
the two automata, and for all $(q_{1},q_{2})\in Q$ and $\sigma\in\Sigma$,
$\delta((q_{1},q_{2}),\sigma)=(\delta_{1}(q_{1},\sigma),\delta_{2}(q_{2},\sigma))$.
For $i=1,2$, let $\pi_{i}$ be projection onto the $i$th coordinate, so that
for a subset $S$ of $Q$, $\pi_{1}(S)=\\{q_{1}\mid\exists q_{2}(q_{1},q_{2})\in
S\\}$, and analogously for $\pi_{2}$.

###  2.2. Acceptors

By augmenting an automaton
$\mathcal{M}=\langle\Sigma,Q,q_{\iota},\delta\rangle$ with an acceptance
condition $\alpha$, obtaining a tuple $\mathcal{A}=\langle\Sigma,Q,q_{\iota},$
$\delta,\alpha\rangle$, we get an _acceptor_ , a machine that accepts some
words and rejects others. We may also denote $\mathcal{A}$ by
$(\mathcal{M},\alpha)$. An acceptor accepts a word if at least one of the runs
on that word is accepting. If the automaton is not complete, a given word $w$
may not have any run in the automaton, in which case $w$ is rejected.

For finite words the acceptance condition is a set $F\subseteq Q$ and a run on
a word $v$ is accepting if it ends in an accepting state, i.e., if $\delta(v)$
contains an element of $F$. For infinite words, there are various acceptance
conditions in the literature, and we consider six of them: Büchi, coBüchi,
Parity, Rabin, Streett, and Muller, all based on the set of states visited
infinitely often in a given run. For each model we define the related quantity
of the size of the acceptor, taking into account the acceptance condition.

A _Büchi_ or _coBüchi_ acceptance condition is a set of states $F\subseteq Q$.
A run $\rho$ of a Büchi acceptor is accepting if it visits $F$ infinitely
often, that is, ${\textsl{inf}}(\rho)\cap F\neq\emptyset$. A run $\rho$ of a
coBüchi acceptor is accepting if it visits $F$ only finitely many times, that
is, ${\textsl{inf}}(\rho)\cap F=\emptyset$. The _size_ of a Büchi or coBüchi
acceptor is the size of its automaton.

A _Parity_ acceptance condition is a map $\kappa:Q\rightarrow\mathbb{N}$
assigning to each state a natural number termed a color (or priority). A run
of a Parity acceptor is accepting if the minimum color visited infinitely
often is odd. The _size_ of a Parity acceptor is the size of its automaton.

A _Rabin_ or _Streett_ acceptance condition consists of a finite set of pairs
of sets of states $\alpha=\\{(G_{1},B_{1}),\ldots,(G_{k},B_{k})\\}$ for some
$k\in\mathbb{N}$ and $G_{i}\subseteq Q$ and $B_{i}\subseteq Q$ for
$i\in[1..k]$. A run of a Rabin acceptor is accepting if there exists an
$i\in[1..k]$ such that $G_{i}$ is visited infinitely often and $B_{i}$ is
visited finitely often. A run of a Streett acceptor is accepting if for all
$i\in[1..k]$, $G_{i}$ is visited finitely often or $B_{i}$ is visited
infinitely often. The _size_ of a Rabin or Streett acceptor is the sum of the
size of its automaton and $k-1$.

A _Muller_ acceptance condition is a set of sets of states
$\alpha=\\{F_{1},F_{2},\ldots,F_{k}\\}$ for some $k\in\mathbb{N}$ and
$F_{i}\subseteq Q$ for $i\in[1..k]$. A run of a Muller acceptor is accepting
if the set $S$ of states visited infinitely often in the run is a member of
$\alpha$. The _size_ of a Muller acceptor is the sum of the size of its
automaton and $k-1$.

The set of words accepted by an acceptor $\mathcal{A}$ is denoted by
${\llbracket}\mathcal{A}{\rrbracket}$. Two acceptors $\mathcal{A}$ and
$\mathcal{B}$ are _equivalent_ if they accept the same language, that is,
${\llbracket}\mathcal{A}{\rrbracket}={\llbracket}\mathcal{B}{\rrbracket}$. For
a state $q$, the acceptor $\mathcal{A}^{q}$ is the acceptor $\mathcal{A}$ with
its automaton initial state replaced by $q$. We say that the $\omega$-word $w$
is _accepted from state $q$_ iff
$w\in{\llbracket}\mathcal{A}^{q}{\rrbracket}$.

We use NBA, NCA, NPA, NRA, NSA, NMA (resp., DBA, DCA, DPA, DRA, DSA, DMA) for
non-deterministic (resp. deterministic) Büchi, Parity, Rabin, Street, Muller
and coBüchi, acceptors. We use $\mathbb{NBA}$, $\mathbb{NCA}$, $\mathbb{NPA}$,
$\mathbb{NMA}$, $\mathbb{NRA}$, and $\mathbb{NSA}$ (resp., $\mathbb{DBA}$,
$\mathbb{DCA}$, $\mathbb{DPA}$, $\mathbb{DRA}$, $\mathbb{DSA}$, and
$\mathbb{DMA}$) for the classes of languages they recognize. $\mathbb{NCA}$ is
the same as $\mathbb{DCA}$, and $\mathbb{DCA}$ and $\mathbb{DBA}$ are distinct
proper subclasses of the regular $\omega$-languages. The other classes are the
full class of regular $\omega$-languages.

###  2.3. Some relationships between the models

We observe the following known relationships.

###### Claim 2.1.

Let $\mathcal{A}$ be an acceptor of one of the types NBA, NCA, NPA, NRA, NSA,
or NMA with $n$ states over the alphabet $\Sigma$. There is an equivalent
complete acceptor $\mathcal{A}^{\prime}$ of the same type whose size is at
most $|\Sigma|$ larger. $\mathcal{A}^{\prime}$ may be taken to be
deterministic if $\mathcal{A}$ is deterministic.

###### Proof.

If $\mathcal{A}$ is incomplete, we modify $\mathcal{A}$ to construct
$\mathcal{A}^{\prime}$ as follows. A new _dead state_ $q_{d}$ is added to the
state set, and the transition function is extended to define
$\delta^{\prime}(q_{d},\sigma)=q_{d}$ for all $\sigma\in\Sigma$ and
$\delta^{\prime}(q,\sigma)=q_{d}$ whenever $\delta(q,\sigma)=\emptyset$.

If necessary, the acceptance condition is modified to avoid classifying a run
that ends in a consecutive sequence of visits to $q_{d}$ as accepted. For
Büchi, Rabin, and Muller acceptors, no modification is necessary. For Parity
acceptors, we extend $\kappa^{\prime}(q_{d})=0$. For coBüchi acceptors, we add
$q_{d}$ to $F$, and for Streett acceptors, we add $q_{d}$ to $G_{i}$ for all
$i\in[1..k]$. ∎

###### Claim 2.2.

Let $\mathcal{B}=\langle\Sigma,Q,q_{\iota},\delta,F\rangle$, where
$\mathcal{B}$ is an NBA. Define the NPA
$\mathcal{P}=\langle\Sigma,Q,q_{\iota},\delta,\kappa\rangle$ where
$\kappa(q)=1$ if $q\in F$ and $\kappa(q)=2$ otherwise. Then $\mathcal{B}$ and
$\mathcal{P}$ are equivalent and have the same size. $\mathcal{P}$ is
deterministic if $\mathcal{B}$ is.

###### Proof.

If $\rho$ is any infinite run of the automaton then ${\textsl{inf}}(\rho)\cap
F\neq\emptyset$ iff the minimum value of $\kappa({\textsl{inf}}(\rho))=1$. ∎

###### Claim 2.3.

Let $\mathcal{B}=\langle\Sigma,Q,q_{\iota},\delta,F\rangle$, where
$\mathcal{B}$ is an NBA. Define the NRA
$\mathcal{R}=\langle\Sigma,Q,q_{\iota},\delta,\\{(F,\emptyset)\\}\rangle$. The
$\mathcal{B}$ and $\mathcal{R}$ are equivalent and have the same size.
$\mathcal{R}$ is deterministic if $\mathcal{B}$ is.

###### Proof.

If $\rho$ is any infinite run of the automaton, then ${\textsl{inf}}(\rho)\cap
F\neq\emptyset$ iff ${\textsl{inf}}(\rho)\cap F\neq\emptyset$ and
${\textsl{inf}}(\rho)\cap\emptyset=\emptyset$. ∎

###### Claim 2.4.

Let $\mathcal{C}=\langle\Sigma,Q,q_{\iota},\delta,F\rangle$, where
$\mathcal{C}$ is a NCA. Define the NSA
$\mathcal{S}=\langle\Sigma,Q,q_{\iota},\delta,\\{(F,\emptyset)\\}\rangle$.
Then $\mathcal{S}$ and $\mathcal{C}$ are equivalent and have the same size.
$\mathcal{S}$ is deterministic if $\mathcal{C}$ is.

###### Proof.

If $\rho$ is any infinite run of the automaton, then ${\textsl{inf}}(\rho)\cap
F=\emptyset$ iff ${\textsl{inf}}(\rho)\cap F=\emptyset$ or
${\textsl{inf}}(\rho)\cap\emptyset\neq\emptyset$. ∎

###### Claim 2.5.

Let $\mathcal{B}=\mathcal{C}=\langle\Sigma,Q,q_{\iota},\delta,F\rangle$, where
$\mathcal{B}$ is a complete DBA and $\mathcal{C}$ is a complete DCA. Then
$\mathcal{B}$ and $\mathcal{C}$ are the same size and the languages they
recognize are complements of each other, that is,
${\llbracket}\mathcal{B}{\rrbracket}=\Sigma^{\omega}\setminus{\llbracket}\mathcal{C}{\rrbracket}$.

###### Proof.

If $w\in\Sigma^{\omega}$ then because the automaton is deterministic and
complete, there is a unique run $\rho$ on $w$. Then
$w\in{\llbracket}\mathcal{B}{\rrbracket}$ iff ${\textsl{inf}}(\rho)\cap
F\neq\emptyset$ iff $w\not\in{\llbracket}\mathcal{C}{\rrbracket}$. ∎

###### Claim 2.6.

Let
$\mathcal{R}=\mathcal{S}=\langle\Sigma,Q,q_{\iota},\delta,\\{(G_{1},B_{1}),\ldots,(G_{k},B_{k})\\}\rangle$,
where $\mathcal{R}$ is a complete DRA and $\mathcal{S}$ is a complete DSA.
Then $\mathcal{R}$ and $\mathcal{S}$ have the same size and the languages they
recognize are complements of each other, that is,
${\llbracket}\mathcal{R}{\rrbracket}=\Sigma^{\omega}\setminus{\llbracket}\mathcal{S}{\rrbracket}$.

###### Proof.

If $w\in\Sigma^{\omega}$ then because the automaton is deterministic and
complete, there is a unique run $\rho$ on $w$. Then
$w\in{\llbracket}\mathcal{R}{\rrbracket}$ iff there exists $i\in[1..k]$ such
that ${\textsl{inf}}(\rho)\cap G_{i}\neq\emptyset$ and
${\textsl{inf}}(\rho)\cap B_{i}=\emptyset$ iff it is not the case that for
every $i\in[1..k]$, ${\textsl{inf}}(\rho)\cap G_{i}=\emptyset$ or
${\textsl{inf}}(\rho)\cap B_{i}\neq\emptyset$ iff
$w\not\in{\llbracket}S{\rrbracket}$. ∎

###  2.4. Right congruences

An equivalence relation $\sim$ on $\Sigma^{*}$ is a _right congruence_ if
$x\sim y$ implies $x\sigma\sim y\sigma$ for all $x,y\in\Sigma^{*}$ and
$\sigma\in\Sigma$. The _index_ of $\sim$, denoted ${|\\!\sim\\!|}$ is the
number of equivalence classes of $\sim$. For a word $x\in\Sigma^{*}$ the
notation $[x]_{\sim}$ denotes the equivalence class of $\sim$ that contains
$x$.

With a right congruence $\sim$ of finite index one can naturally associate a
complete deterministic automaton
$\mathcal{M}_{\sim}=\langle\Sigma,Q,q_{\iota},\delta\rangle$ as follows: the
set of states $Q$ consists of the equivalence classes of $\sim$. The initial
state $q_{\iota}$ is the equivalence class $[\varepsilon]_{\sim}$. The
transition function $\delta$ is defined by
$\delta([u]_{\sim},\sigma)=[u\sigma]_{\sim}$ for all $\sigma\in\Sigma$. Also,
given a complete deterministic automaton
$\mathcal{M}=\langle\Sigma,Q,q_{\iota},\delta\rangle$, we can naturally
associate with it a right congruence as follows: $x\sim_{\mathcal{M}}y$ iff
$\mathcal{M}$ reaches the same state of $\mathcal{M}$ when reading $x$ or $y$,
that is, $\delta(q_{\iota},x)=\delta(q_{\iota},y)$.

Given a language $L\subseteq\Sigma^{*}$ its _canonical right congruence_
$\sim_{L}$ is defined as follows: $x\sim_{L}y$ iff ${\forall z\in\Sigma^{*}}$
we have ${xz\in L}\iff{yz\in L}$. The Myhill-Nerode Theorem states that a
language $L\subseteq\Sigma^{*}$ is regular iff $\sim_{L}$ is of finite index.
Moreover, if $L$ is accepted by a complete DFA $\mathcal{A}$, then
$\sim_{\mathcal{M}}$ refines $\sim_{L}$, where $\mathcal{M}$ is the automaton
of $\mathcal{A}$. Finally, any complete DFA of minimum size that accepts $L$
has an automaton that is isomorphic to $\mathcal{M}_{\sim_{L}}$.

For an $\omega$-language $L\subseteq\Sigma^{\omega}$, its _canonical right
congruence_ $\sim_{L}$ is defined similarly, by quantifying over
$\omega$-words. That is, $x\sim_{L}y$ iff ${\forall z\in\Sigma^{\omega}}$ we
have ${xz\in L}\iff{yz\in L}$. If $L$ is a regular $\omega$-language then
$\sim_{L}$ is of finite index, and for any complete DBA (resp., DCA, DPA, DRA,
DSA, DMA) $\mathcal{A}$ that accepts $L$, $\sim_{\mathcal{M}}$ refines
$\sim_{L}$, where $\mathcal{M}$ is the automaton of the acceptor.

However, for regular $\omega$-languages, the relation $\sim_{L}$ does not
suffice to obtain a “Myhill-Nerode” characterization. In particular, for a
regular $\omega$-language $L$ there may be no way to define an acceptance
condition for $\mathcal{M}_{\sim_{L}}$ that yields a DBA (resp., DCA, DPA,
DRA, DSA, DMA) that accepts $L$. As an example consider the language
$L=(a+b)^{*}(bba)^{\omega}$. Then $\sim_{L}$ consists of just one equivalence
class, because for any $x\in\Sigma^{*}$ and $w\in\Sigma^{\omega}$ we have that
$xw\in L$ iff $w$ has $(bba)^{\omega}$ as a suffix. But a DBA (resp., DCA,
DPA, DRA, DSA, DMA) that accepts $L$ clearly needs more than a single state.

###  2.5. The classes $\mathbb{IB}$, $\mathbb{IC}$, $\mathbb{IP}$,
$\mathbb{IR}$, $\mathbb{IS}$ and $\mathbb{IM}$

In light of the lack of a Myhill-Nerode result for regular $\omega$-languages,
we define a restricted type of deterministic Büchi (resp., coBüchi, Parity,
Rabin, Streett, Muller) acceptor. A DBA (resp., DCA, DPA, DRA, DSA, DMA)
$\mathcal{A}$ that accepts the language
$L={\llbracket}\mathcal{A}{\rrbracket}$ is an IBA (resp., ICA, IPA, IRA, ISA,
IMA) if it is complete and its automaton is isomorphic to
$\mathcal{M}_{\sim_{L}}$. A language $L$ is in $\mathbb{IB}$ (resp.,
$\mathbb{IC}$, $\mathbb{IP}$, $\mathbb{IR}$, $\mathbb{IS}$, $\mathbb{IM}$) if
there exists an IBA (resp, ICA, IPA, IRA, ISA, IMA) $\mathcal{A}$ such that
$L={\llbracket}\mathcal{A}{\rrbracket}$. We note that every state of an IBA
(resp., ICA, IPA, IRA, ISA, IMA) is reachable because every state of
$\mathcal{M}_{\sim_{L}}$ is reachable.

Despite the fact that each of these classes is a proper subset of its
corresponding deterministic class (e.g., $\mathbb{IB}$ is a proper subset of
$\mathbb{DBA}$), these classes are more expressive than one might first
conjecture. It was shown in (Angluin and Fisman, 2018) that in every class of
the infinite Wagner hierarchy (Wagner, 1975) there are languages in
$\mathbb{IM}$ and $\mathbb{IP}$. Moreover, in a small experiment reported in
(Angluin and Fisman, 2018), among randomly generated Muller automata, the vast
majority turned out to be in $\mathbb{IM}$.

###  2.6. Examples and samples

Because we require finite representations of examples, $\omega$-words in our
case, we work with ultimately periodic words, that is, words of the form
$u(v)^{\omega}$ where $u\in\Sigma^{*}$ and $v\in\Sigma^{+}$. It is known that
two regular $\omega$-languages are equivalent iff they agree on the set of
ultimately periodic words, so this choice is not limiting.

The example $u(v)^{\omega}$ is concretely represented by the pair $(u,v)$ of
finite strings, and its length is $|u|+|v|$. A _labeled example_ is a pair
$(u(v)^{\omega},l)$, where the label $l$ is either $0$ or $1$. A _sample_ is a
finite set of labeled examples such that no example is assigned two different
labels. The length of a sample is the sum of the lengths of the examples that
appear in it. A sample $T$ and a language $L$ are _consistent_ with each other
if and only if for every labeled example $(u(v)^{\omega},l)\in T$, $l=1$ iff
$u(v)^{\omega}\in L$. A sample $T$ and an acceptor $\mathcal{A}$ are
_consistent_ with each other if and only if $T$ is consistent with
${\llbracket}\mathcal{A}{\rrbracket}$. The following results give two useful
procedures on examples that are computable in polynomial time.

###### Proposition 2.7.

Let $u_{1},u_{2}\in\Sigma^{*}$ and $v_{1},v_{2}\in\Sigma^{+}$. If
$u_{1}(v_{1})^{\omega}\neq u_{2}(v_{2})^{\omega}$ then they differ in at least
one of the first $\ell$ symbols, for
$\ell=\max(|u_{1}|,|u_{2}|)+|v_{1}|\cdot|v_{2}|$.

Let $\textit{suffixes}(u(v)^{\omega})$ denote the set of all $\omega$-words
that are suffixes of $u(v)^{\omega}$.

###### Proposition 2.8.

The set $\textit{suffixes}(u(v)^{\omega})$ consists of at most $|u|+|v|$
different examples: one of the form $u^{\prime}(v)^{\omega}$ for every
nonempty suffix $u^{\prime}$ of $u$, and one of the form
$(v_{2}v_{1})^{\omega}$ for every division of $v$ into a non-empty prefix and
suffix as $v=v_{1}v_{2}$.

###  2.7. Identification in the limit using polynomial time and data

We consider the notion of identification in the limit using polynomial time
and data. This criterion of learning was introduced by Gold (Gold, 1978), who
showed that regular languages of finite strings represented by DFAs are
learnable in this sense. We follow a more general definition given by de la
Higuera (de la Higuera, 1997). The definition has two requirements: (1) a
learning algorithm $\mathbf{A}$ that runs in polynomial time on a set of
labeled examples and produces a hypothesis consistent with the examples, and
(2) that for every language $L$ in the class, there exists a set $T_{L}$ of
labeled examples of size polynomial in a measure of size of $L$ such that on
any set of labeled examples containing $T_{L}$, the algorithm $\mathbf{A}$
outputs a hypothesis correct for $L$. Condition (1) ensures polynomial time,
while condition (2) ensures polynomial data. The latter is not a worst-case
measure; there could be arbitrarily large finite samples for which
$\mathbf{A}$ outputs an incorrect hypothesis. However, de la Higuera shows
that identifiability in the limit with polynomial time and data is closely
related to a model of a learner and a helpful teacher introduced by Goldman
and Mathias (Goldman and Mathias, 1996).

##  3\. Negative Results

We start with negative results. We show that when the representation at hand
is non-deterministic, polynomial identification is not feasible.

###### Theorem 3.1.

$\mathbb{NBA}$ cannot be identified in the limit using polynomial data.

###### Proof.

The proof follows the idea given in de la Higuera’s negative result for
learning NFAs in the limit from polynomial data (de la Higuera, 1997). For any
integer $M\geq 2$, let $p_{1},\ldots,p_{m}$ be the set of all primes less than
or equal to $M$. For each such $M$, consider the NBA $\mathcal{B}_{M}$ over a
two letter alphabet $\Sigma=\\{a,b\\}$ with $p_{1}+p_{2}+\ldots+p_{m}+2$
states, where state $0$ has $a$-transitions to state $(\textbf{p},1)$ for each
$\textbf{p}\in\\{p_{1},p_{2},\ldots,p_{m}\\}$. State $(\textbf{p},i)$ has an
$a$-transition to state $(\textbf{p},i\oplus_{p}1)$ where $\oplus_{p}$ is
addition modulo $p$. All states except the states $(\textbf{p},0)$ have a
$b$-transition to state $b$. The state $b$ has a self-loop on $b$. The only
accepting state is $b$. The NBA $\mathcal{B}_{M}$ for $M=5$ is given in Fig.
1.

The NBA $\mathcal{B}_{M}$ accepts the set of all words of the form
$a^{k}b^{\omega}$ such that $k$ is _not_ a positive multiple of
$\ell=p_{1}\cdot p_{2}\cdots p_{m}$. Note that the size of the shortest
ultimately periodic word in
$a^{*}b^{\omega}\setminus{\llbracket}\mathcal{B}_{M}{\rrbracket}$ is $\ell+1$,
and thus, to distinguish the language
${\llbracket}\mathcal{B}_{M}{\rrbracket}$ from the language $a^{*}b^{\omega}$,
a word of at least this size must be provided. Since the number of primes not
greater than $M$ is $\Theta(M/\log M)$ and since each prime is of size at
least $2$ the data must be of size at least $2^{\Theta(M/\log M)}$ while the
number of states of $\mathcal{B}_{M}$ is $O(M^{2})$. ∎

$0$$b$$\textbf{2},1$$\textbf{2},0$$\textbf{3},1$$\textbf{3},2$$\textbf{3},0$$\textbf{5},1$$\textbf{5},2$$\textbf{5},3$$\textbf{5},4$$\textbf{5},0$$b$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$a$$b$$b$$b$$b$$b$$b$$b$$b$

Figure 1. The NBA $\mathcal{B}_{M}$ for $M=5$.

###### Corollary 3.2.

$\mathbb{NPA}$, $\mathbb{NRA}$, and $\mathbb{NMA}$ cannot be identified in the
limit using polynomial data.

###### Proof.

The NBA in the proof of Theorem 3.1 can be converted to an equivalent NPA of
the same size using Claim 2.2, and to an equivalent NRA of the same size using
Claim 2.3. It can be converted to an equivalent NMA of the same size with the
same automaton by specifying the acceptance condition $\\{\\{b\\}\\}$. ∎

While NBAs are not a special case of non-deterministic coBüchi automata (NCA)
it can be shown that $\mathbb{NCA}$ also cannot be identified in the limit
from polynomial data, which is in some sense surprising, since NCAs are not
more expressive than DCAs, their deterministic counterpart, and accept a very
small subclass of the regular $\omega$-languages.

###### Theorem 3.3.

$\mathbb{NCA}$ and $\mathbb{NSA}$ cannot be identified in the limit using
polynomial data.

###### Proof.

Define the NCA acceptor $\mathcal{C}_{M}$ to have the same automaton as
$\mathcal{B}_{M}$ from the proof of Theorem 3.1, with all states except $b$
accepting. Then $\mathcal{C}_{M}$ accepts the same language as
$\mathcal{B}_{M}$ and has the same size. This NCA can be converted to an
equivalent NSA of the same size using Claim 2.4. ∎

##  4\. Towards the positive results

The rest of the paper is devoted to the positive results. This section covers
some preliminary issues and gives an overview of the positive results.

###  4.1. Duality

There are reductions of the problem of identification in the limit using
polynomial time and data between $\mathbb{IB}$ and $\mathbb{IC}$ and between
$\mathbb{IR}$ and $\mathbb{IS}$, using the duality between these types of
acceptors. Consequently we focus on the classes $\mathbb{IB}$, $\mathbb{IP}$,
$\mathbb{IR}$, and $\mathbb{IM}$ in what follows.

###### Proposition 4.1.

If $\mathbb{IB}$ (resp., $\mathbb{IR}$) is identifiable in the limit using
polynomial time and data, then so is $\mathbb{IC}$ (resp., $\mathbb{IS}$).

###### Proof.

Let $\mathcal{A}$ be an ICA. Because $\mathcal{A}$ is deterministic and
complete, if we let $\mathcal{A}^{\prime}$ denote the IBA with the same
components as $\mathcal{A}$, then $\mathcal{A}^{\prime}$ accepts the
complement of the language $\mathcal{A}$, by Claim 2.5.

We modify the characteristic sample for $\mathcal{A}^{\prime}$ by
complementing all its labels to get a characteristic sample for $\mathcal{A}$.
The algorithm to learn an ICA from a sample $T$ is obtained by complementing
all the labels in the sample $T$ and calling the algorithm to learn an IBA
from a sample. The resulting IBA, now considered to be an ICA, is returned as
the answer.

Exactly the same conversion may be done with acceptors of types IRA and ISA,
by Claim 2.6. ∎

###  4.2. The default acceptor

One condition of the definition of identification in the limit using
polynomial time and data is that the learning algorithm must run in polynomial
time and return an acceptor of the required type that is consistent with the
input sample $T$, even if the sample $T$ does not subsume a characteristic
sample. To meet this condition, we use the strategy of Gold’s construction,
that is, the learning algorithm optimistically assumes that the sample
includes a characteristic sample, and if that assumption fails to produce an
acceptor consistent with the sample, the algorithm instead produces a _default
acceptor_ to ensure that its hypothesis is consistent with the sample. In
practical applications much more effort would be expended to find good
heuristic choices to avoid defaulting too easily.

###### Proposition 4.2.

There is a polynomial time algorithm that takes a sample $T$ and returns a DBA
(resp., DCA, DPA, DRA, DSA, DMA) consistent with $T$.

###### Proof.

Given a sample $T$, we find the shortest prefix of each example
$u(v)^{\omega}$ in $T$ that distinguishes it from all other examples in $T$
and place these prefixes in a deterministic prefix-tree automaton. By Prop.
2.7, this prefix-tree automaton can be constructed in time polynomial in the
length of the sample $T$. For each leaf state we define self-transitions on
each symbol in $\Sigma$, and if the automaton is incomplete, we add a new dead
state with self-transitions on each symbol in $\Sigma$, and define all
undefined transitions to go to the dead state.

For a DBA, the acceptance condition $F$ consists of all the leaf states that
are prefixes of positive examples in $T$. For a DMA, the acceptance condition
consists of $\\{\\{q\\}\mid q\in F\\}$. For a DCA, the acceptance condition
consists of the dead state (if one was added) and all the leaf states that are
not prefixes of positive examples in $T$. The DBA thus constructed may be
transformed to a DPA or a DRA using Claim 2.2 or Claim 2.3, and the DCA may be
transformed to a DSA using Claim 2.4. ∎

As an example of this construction, let the sample be

$T=\\{(a(b)^{\omega},1),((ab)^{\omega},1),(ab(baa)^{\omega},0)\\}.$

The corresponding prefixes are $abbb$, $aba$, and $abba$, and the default
acceptor of type DBA for $T$ is shown in Figure 2.

$d$$*$$*$$*$$a$$b$$a,b$$a$$b$$a$$b$$a,b$$a$$b$$a,b$$a,b$

Figure 2. Default acceptor of type DBA for $T=\\{(a(b)^{\omega},1),$
$((ab)^{\omega},1),$ $(ab(baa)^{\omega},0)\\}$. Leaf states are marked with
$*$ and the dead state with $d$.

###  4.3. Strongly connected components

The acceptance conditions that we consider are all based on the set of states
visited infinitely often in a run of the automaton on an input
$w\in\Sigma^{\omega}$. We consider only acceptors whose automata are
deterministic and complete, so for any $w\in\Sigma^{\omega}$ there is exactly
one run, which we denote $\rho(w)$, of the automaton on input $w$. Thus we may
define ${\textsl{inf}}(w)={\textsl{inf}}(\rho(w))$, the set of states visited
infinitely often in this unique run. In the run $\rho(w)$, there is some point
after which none of the states visited finitely often is visited. Because each
state in ${\textsl{inf}}(w)$ is visited infinitely often, for any states
$q_{1},q_{2}\in{\textsl{inf}}(w)$, there exists a non-empty word
$x\in\Sigma^{*}$ such that $\delta(q_{1},x)=q_{2}$ and for each prefix
$x^{\prime}$ of $x$, $\delta(q_{1},x^{\prime})\in{\textsl{inf}}(w)$, that is,
the path from $q_{1}$ to $q_{2}$ on $x$ does not visit any state outside the
set ${\textsl{inf}}(w)$.

These properties characterize the following definition. Given an automaton
$\mathcal{M}$, a _strongly connected component_ (SCC) of $\mathcal{M}$ is a
nonempty set of states $C$ such that for every $q_{1},q_{2}\in C$, there
exists a nonempty string $x\in\Sigma^{*}$ such that $\delta(q_{1},x)=q_{2}$
and for any prefix $x^{\prime}$ of $x$, $\delta(q_{1},x^{\prime})\in C$.

Note that an SCC need not be maximal, and that a singleton state set $\\{q\\}$
is an SCC if and only if the state $q$ has a self-loop, that is,
$\delta(q,\sigma)=q$ for some $\sigma\in\Sigma$. There is a close relationship
between SCCs and the set of states visited infinitely often in a run.

###### Proposition 4.3.

Let $\mathcal{M}$ be a complete deterministic automaton and
$w\in\Sigma^{\omega}$. Then ${\textsl{inf}}(w)$ is an SCC of $\mathcal{M}$. If
$w$ is the ultimately periodic word $u(v)^{\omega}$, then ${\textsl{inf}}(w)$
may be computed in time polynomial in the size of $\mathcal{M}$ and the length
of $u(v)^{\omega}$.

###### Proposition 4.4.

For any deterministic automaton
$\mathcal{M}=\langle\Sigma,Q,q_{\iota},\delta\rangle$ and any reachable SCC
$C$ of $\mathcal{M}$, there exists an ultimately periodic word $u(v)^{\omega}$
of length at most $|Q|+|C|^{2}$ such that $C={\textsl{inf}}(w)$. Such a word
may be found in time polynomial in $|Q|$ and $|\Sigma|$.

###### Proof.

Because $C$ is reachable, a word $u\in\Sigma^{*}$ of minimum length such that
$\delta(q_{\iota},u)\in C$ may be found by breadth first search. The length of
$u$ is at most $|Q|$. If $C=\\{q\\}$, then there is at least one symbol
$\sigma\in\Sigma$ such that $\delta(q,\sigma)=q$. Then the $\omega$-word
$w=u(\sigma)^{\omega}$ is such that $C={\textsl{inf}}(w)$. The length of this
ultimately periodic word is at most $|Q|+1$.

If $C$ contains at least two states, let $q_{1},\ldots,q_{k}$ be the states in
$C$ that are not $q$. Then for each $i$, there exist two nonempty finite words
$x_{i}$ and $y_{i}$ each of length at most $n$ such that
$\delta(q,x_{i})=q_{i}$ and $\delta(q_{i},y_{i})=q$, and the path on $x_{i}$
from $q$ to $q_{i}$ and the path on $y_{i}$ from $q_{i}$ to $q$ do not visit
any states outside of $C$. The words $x_{i}$ and $y_{i}$ may be found in
polynomial time by breadth-first search. Then the word $w=u(x_{1}y_{1}\cdots
x_{k}y_{k})^{\omega}$ is such that ${\textsl{inf}}(w)=C$. The length of this
ultimately periodic word is at most $|Q|+|C|^{2}$. ∎

We let $\mathbf{Witness}(C,\mathcal{M})$ denote the ultimately periodic word
$u(v)^{\omega}$ returned by the algorithm described in the proof above for the
reachable SCC $C$ of automaton $\mathcal{M}$.

###### Proposition 4.5.

If $C_{1}$ and $C_{2}$ are SCCs of automaton $\mathcal{M}$ and $C_{1}\cap
C_{2}\neq\emptyset$, then $C_{1}\cup C_{2}$ is also an SCC of $\mathcal{M}$.

If $\mathcal{M}$ is an automaton and $S$ is any set of its states, define
$\textit{SCCs}(S)$ to be the set of all $C$ such that $C\subseteq S$ and $C$
is an SCC of $\mathcal{M}$. Also define $maxSCCs(S)$ to be the maximal
elements of $\textit{SCCs}(S)$ with respect to the subset ordering. The
following is a consequence of Prop. 4.5.

###### Proposition 4.6.

If $\mathcal{M}$ is an automaton and $S$ is any set of its states, then the
elements of $\textit{maxSCCs}(S)$ are pairwise disjoint, and every set $C\in
SCCs(S)$ is a subset of exactly one element of $\textit{maxSCCs}(S)$.

There are some differences in the terminology related to strong connectivity
between graph theory and omega automata, which we resolve as follows. In graph
theory, a _path_ of length $k$ from $u$ to $v$ in a directed graph $(V,E)$ is
a finite sequence of vertices $v_{0},v_{1},\ldots,v_{k}$ such that $u=v_{0}$,
$v=v_{k}$ and for each $i$ with $i\in[1..k]$, $(v_{i-1},v_{i})\in E$. Thus,
for every vertex $v$, there is a path of length $0$ from $v$ to $v$. A set of
vertices $S$ is _strongly connected_ if and only if for all $u,v\in S$, there
is a path of some nonnegative length from $u$ to $v$ and all the vertices in
the path are elements of $S$. Thus, for every vertex $v$, the singleton set
$\\{v\\}$ is a strongly connected set of vertices. A _strongly connected
component_ of a directed graph is a maximal strongly connected set of
vertices. There is a linear time algorithm to find the set of strong
components of a directed graph (Tarjan, 1972).

In this paper, we use the terminology SCC and maximal SCC to refer to the
definitions from the theory of omega automata, and the terminology _graph
theoretic strongly connected components_ to refer to the definitions from
graph theory. We use the term _trivial strong component_ to refer to a graph
theoretic strongly connected component that is a singleton vertex $\\{v\\}$
such that there is no edge $(v,v)$.

If $\mathcal{M}$ is an automaton, we may define a related directed graph
$G(\mathcal{M})$ whose vertices are the states of $\mathcal{M}$ and whose
edges $(q_{1},q_{2})$ are the pairs of states such that
$q_{2}\in\delta(q_{1},\sigma)$ for some $\sigma\in\Sigma$. Then for any set
$S$ of states of $\mathcal{M}$, the maximal SCCs in $S$,
$\textit{maxSCCs}(S)$, are the graph theoretic strongly connected components
of the subgraph of $G(\mathcal{M})$ induced by $S$, with any trivial strong
components removed.

###### Proposition 4.7.

For automaton $\mathcal{M}$ and any subset $S$ of its states,
$\textit{maxSCCs}(S)$ can be computed in time linear in the size of
$\mathcal{M}$.

###  4.4. A decreasing forest of SCCs of an automaton

Let $\mathcal{M}$ be a deterministic automaton, and let $S$ be a subset of its
states. A _decreasing forest of SCCs of $\mathcal{M}$ rooted in $S$_ is a
finite rooted forest $\mathcal{F}$ in which every node $C$ is an SCC of
$\mathcal{M}$ that is contained in $S$, and the following properties are
satisfied.

  1. (1)

The roots of $\mathcal{F}$ are the elements of $\textit{maxSCCs}(S)$.

  2. (2)

Whenever $D_{1},\ldots,D_{k}$ are the children of node $C$, we have
$D_{1}\cup\ldots\cup D_{k}\subsetneq C$. Also, letting
$\Delta(C)=C\setminus(D_{1}\cup\ldots\cup D_{k})$, the children
$D_{1},\ldots,D_{k}$ are exactly the elements of
$\textit{maxSCCs}(C\setminus\Delta(C))$.

###### Proposition 4.8.

Let $\mathcal{M}$ be a deterministic automaton, $S$ a subset of its states,
and $\mathcal{F}$ a decreasing forest of SCCs of $\mathcal{M}$ rooted in $S$.
Then the following are true.

  1. (1)

The roots of $\mathcal{F}$ are pairwise disjoint.

  2. (2)

The children of any node are pairwise disjoint.

  3. (3)

$\mathcal{F}$ has at most $|S|$ nodes.

  4. (4)

For any $D\subseteq S$ that is an SCC of $\mathcal{M}$, there is a unique node
$C$ in $\mathcal{F}$ such that $D\subseteq C$ and $D$ is not a subset of any
of the children of $C$.

###### Proof.

The roots of $\mathcal{F}$ are the elements of $\textit{maxSCCs}(S)$, which
are pairwise disjoint. The children of a node $C$ are the elements of
$\textit{maxSCCs}(C\setminus\Delta(C))$, which are pairwise disjoint. The sets
$\Delta(C)$ for nodes $C$ in $\mathcal{F}$ are contained in $S$, nonempty, and
pairwise disjoint, so the number of nodes is at most $|S|$. If $D\subseteq S$
is an SCC of $\mathcal{M}$, then $D$ is a subset of exactly one of the roots
of $\mathcal{F}$, say $C_{1}$. If $D\cap\Delta(C_{1})\neq\emptyset$, then $D$
is not a subset of any of the children of $C_{1}$. Otherwise, $D$ must be a
subset of exactly one of the children of $C_{1}$, say $C_{2}$. If
$D\cap\Delta(C_{2})\neq\emptyset$, then $D$ is not a subset of any of the
children of $C_{2}$. Continuing in this way, we eventually arrive at the
required node $C$. ∎

Given a decreasing forest $\mathcal{F}$ of SCCs of automaton $\mathcal{M}$
rooted in $S$, and an SCC $D\subseteq S$, we denote by
$\mathbf{Node}(D,\mathcal{F})$ the unique node $C$ of $\mathcal{F}$ such that
$D\subseteq C$ and $D$ is not a subset of any of the children of $C$. We note
that if $C=\mathbf{Node}(D,\mathcal{F})$ then $D\cap\Delta(C)\neq\emptyset$.
If $D$ is a child of some $C$ in $\mathcal{F}$, we define _merging $D$ into
$C$_ as the operation of removing $D$ from $\mathcal{F}$ and making the
children of $D$ (if any) direct children of $C$.

###### Proposition 4.9.

Let $\mathcal{M}$ be a deterministic automaton and $S$ a subset of its states.
Let $\mathcal{F}$ be a decreasing forest of SCCs of $\mathcal{M}$ rooted in
$S$. Let $D$ be a child of $C$ in $\mathcal{F}$ and let $\mathcal{F}$’ be
obtained from $\mathcal{F}$ by merging $D$ into $C$. Then $\mathcal{F}$’ is
also a decreasing forest of SCCS of $\mathcal{M}$ rooted in $S$.

###### Proof.

After the merge, the roots of $\mathcal{F}$ remain the elements of
$\textit{maxSCCs}(S)$. Let $D_{1},\ldots,D_{k}$ be the children of $C$ in $F$,
where $D=D_{k}$, and let $E_{1},\ldots,E_{\ell}$ be the children of $D$ in
$F$. Because the union of $E_{1},\ldots,E_{\ell}$ is a proper subset of
$D=D_{k}$ and the union of $D_{1},\ldots,D_{k}$ is a proper subset of $C$, the
union of $D_{1},\ldots,D_{k-1}$ with the union of $E_{1},\ldots,E_{\ell}$ is a
proper subset of $C$, therefore the union of the children of $C$ in
$\mathcal{F}$ is a proper subset of $C$. Also, the children of $C$ in
$\mathcal{F}$ are the maximum SCCs of
$(C\setminus\Delta_{\mathcal{F}^{\prime}}(C))$, and no other nodes are
affected, so $\mathcal{F}$ is a decreasing forest of SCCs of $\mathcal{M}$
rooted in $S$. ∎

###  4.5. Overview of the positive results

To show that a class is identified in the limit using polynomial time and data
there are two parts: (i) constructing a sample of words $T_{L}$ of size
polynomial in the size of the given acceptor $\mathcal{A}$ for the language
$L$ at hand, called the _characteristic sample_ , and (ii) providing a
polynomial time learning algorithm $\mathbf{A}$ that for every given sample
$T$ returns an acceptor consistent with $T$, and, moreover, for any sample $T$
that subsumes $T_{L}$, returns an acceptor that accepts $L$.

The definition of an acceptor has two parts: (a) the definition of the
automaton and (b) the definition of the acceptance condition. Correspondingly,
we view the characteristic sample as a union of two parts: $T_{Aut}$ (to
specify the automaton) and $T_{Acc}$ (to specify the acceptance condition). In
Section 5 we discuss the construction of $T_{Aut}$, which is common to all the
classes we consider, as they all are isomorphic to $\mathcal{M}_{\sim_{L}}$
for the target language $L$. We also describe a polynomial time algorithm to
construct the automaton using the labeled words in $T_{Aut}$.

Because the acceptance conditions differ, $T_{Acc}$ is different for each type
of acceptor we consider. In Section 6 we describe the construction of
$T_{Acc}$ for acceptors of types IMA and IBA and learning algorithms for
acceptors of these types, showing that $\mathbb{IM}$, $\mathbb{IB}$, and
$\mathbb{IC}$ are identifiable in the limit using polynomial time and data. In
Section 7 we describe the construction of $T_{Acc}$ for acceptors of type IPA
and a learning algorithm for acceptors of this type, showing that
$\mathbb{IPA}$ is identifiable in the limit using polynomial time and data. In
Section 8 we describe the construction of $T_{Acc}$ for acceptors of type IRA
and a learning algorithm for acceptors of this type, showing that
$\mathbb{IR}$ and $\mathbb{IS}$ are identifiable in the limit using polynomial
time and data.

In Section 9 we show that the characteristic samples we have defined can be
computed in polynomial time in the size of the acceptor. These results rely on
polynomial time algorithms for the inclusion and equivalence problems for the
acceptors. These are described in Sections 10, 11, 12, and 13. In Section 14
we show the right congruence automaton $\mathcal{M}_{\sim_{L}}$ can be
computed in polynomial time, given a DBA, DCA, DPA, DRA, DSA, or DMA accepting
$L$, which yields polynomial time algorithms to test whether a DBA is an IBA,
and similarly for the other acceptor types. In Section 15, we consider the
harder problem of whether a DBA accepts a language in $\mathbb{IB}$, and give
polynomial time algorithms for DBAs, DCAs, DPAs, and DMAs, leaving open the
problem for DRAs and DSAs. In Section 16 we summarize our results and describe
some additional open problems.

##  5\. The sample $T_{Aut}$ for the automaton

In this section we describe construction of the $T_{Aut}$ part of the sample.
We first show that if two states of the automaton are distinguishable, they
are distinguishable by words of length polynomial in the number of states of
the automaton.

###  5.1. Existence of short distinguishing words

Let $A$ be an acceptor of one of the types DBA, DCA, DPA, DRA, DSA, or DMA
over alphabet $\Sigma$. We say that states $q_{1}$ and $q_{2}$ of
$\mathcal{M}$ are _distinguishable_ if there exists a word
$w\in\Sigma^{\omega}$ that is accepted from one state but not the other, that
is,
$w\in{\llbracket}\mathcal{A}^{q_{1}}{\rrbracket}\setminus{\llbracket}\mathcal{A}^{q_{2}}{\rrbracket}$
or
$w\in{\llbracket}\mathcal{A}^{q_{2}}{\rrbracket}\setminus{\llbracket}\mathcal{A}^{q_{1}}{\rrbracket}$.
In this case we say that $w$ is a _distinguishing word_.

###### Proposition 5.1.

If two states of a complete DBA, DCA, DPA, DRA, DSA, or DMA of $n$ states are
distinguishable, then they are distinguishable by an ultimately periodic
$\omega$-word of length bounded by $O(n^{4})$.

###### Proof.

We prove the result for a DMA. Because any DBA, DCA, DPA, DRA, or DSA is
equivalent to a DMA with the same automaton, this result holds for these types
of acceptors as well.

Let $\mathcal{A}$ be a complete DMA of $n$ states such that the states $q_{1}$
and $q_{2}$ are distinguishable. Then there exists an $\omega$-word $w$ that
is accepted from exactly one of the two states, that is, $w$ is accepted by
exactly one of $\mathcal{A}^{q_{1}}$ and $\mathcal{A}^{q_{2}}$.

Let $\mathcal{M}_{i}$ denote the automaton of $\mathcal{A}$ with its initial
state replaced by $q_{i}$ for $i=1,2$. Let $\mathcal{M}$ denote the product
automaton $\mathcal{M}_{1}\times\mathcal{M}_{2}$. The number of states of
$\mathcal{M}$ is $n^{2}$. By Prop. 4.3, $\textit{inf}_{M}(w)$ is a reachable
SCC $C$ of $\mathcal{M}$, and by Prop. 4.4 there exists an ultimately periodic
word $u(v)^{\omega}$ of length bounded by $O(n^{4})$ such that
$\textit{inf}_{\mathcal{M}}(u(v)^{\omega})=C$.

Then for $i=1,2$,
$\textit{inf}_{\mathcal{M}_{i}}(u(v)^{\omega})=\pi_{i}(C)=\textit{inf}_{\mathcal{M}_{i}}(w)$,
so $u(v)^{\omega}$ is also accepted by exactly one of $\mathcal{A}^{q_{1}}$
and $\mathcal{A}^{q_{2}}$, and $u(v)^{\omega}$ distinguishes $q_{1}$ and
$q_{2}$. ∎

###  5.2. Defining the sample $T_{Aut}$ for the automaton

We now define the $T_{Aut}$ part of the characteristic sample, given an
acceptor $\mathcal{A}=\langle\Sigma,Q,q_{\iota},\delta,\alpha\rangle$ that is
an IBA, ICA, IPA, IRA, ISA, or IMA. This construction is analogous to that of
the corresponding part of a characteristic sample for a DFA, with
distinguishing experiments that are ultimately periodic $\omega$-words instead
of finite strings. Let $\mathcal{M}$ be the automaton of $\mathcal{A}$ and let
$n$ be the number of states of $\mathcal{M}$.

Because $\mathcal{A}$ is an IBA, ICA, IPA, IRA, ISA, or IMA, every state is
reachable and every pair of states is distinguishable. We define a
distinguished set of $n$ _access strings_ for the states of $\mathcal{M}$ as
follows. For each state $q$, $\textit{access}(q)$ is the least string $x$ in
the shortlex ordering such that $\delta(q_{\iota},x)=q$. Given $\mathcal{A}$,
the access strings may be computed in polynomial time by breadth first search.

Because every pair of states is distinguishable, by Proposition 5.1, there
exists a set $E$ of at most $n$ distinguishing experiments, each of length at
most $n^{2}+n^{4}$, that distinguish every pair of states. The issue of
computing $E$ is addressed in Section 9.

The sample $T_{Aut}$ consists of all the examples in $(S\cdot
E)\cup(S\cdot\Sigma\cdot E)$, labeled to be consistent with $\mathcal{A}$.
There are at most $(1+|\Sigma|)n^{2}$ labeled examples in $T_{Aut}$, each of
length bounded by a polynomial in $n$. A learning algorithm using $T_{Aut}$ is
described next.

###  5.3. Learning the automaton from $T_{Aut}$

We now describe a learning algorithm $\mathbf{L}_{Aut}$ and prove the
following.

###### Theorem 5.2.

The algorithm $\mathbf{L}_{Aut}$ with a sample $T$ as input runs in polynomial
time and returns a deterministic complete automaton $\mathcal{M}$. Let
$\mathcal{A}$ be an an acceptor of type IBA, ICA, IPA, IRA, ISA, or IMA. If
$T$ is consistent with $\mathcal{A}$ and subsumes $T_{Aut}$ then the returned
automaton $\mathcal{M}$ is isomorphic to the automaton of $\mathcal{A}$.

Algorithm $\mathbf{L}_{Aut}$ on input $T$ constructs a set $E$ of words that
serve as experiments used to distinguish candidate states. For each
$(u(v)^{\omega},l)$ in $T$, all of the elements of
$\textit{suffixes}(u(v)^{\omega})$ are placed in $E$. Two strings
$x,y\in\Sigma^{*}$ are _consistent with respect to $T$_ if and only if there
does not exist any $u(v)^{\omega}\in E$ such that the examples
$xu(v)^{\omega}$ and $yu(v)^{\omega}$ are oppositely labeled in $T$.

Starting with the empty string $\varepsilon$, the algorithm builds up a
prefix-closed set $S$ of finite strings as follows. Initially,
$S_{1}=\\{\varepsilon\\}$. After $S_{k}$ has been constructed, the algorithm
considers each $s\in S_{k}$ in shortlex order, and each symbol
$\sigma\in\Sigma$ in the ordering defined on $\Sigma$. If there exists no
$s^{\prime}\in S_{k}$ such that $s\sigma$ is consistent with $s^{\prime}$ with
respect to $T$, then $S_{k+1}$ is set to $S_{k}\cup\\{s\sigma\\}$ and $k$ is
set to $k+1$. If no such pair $s$ and $\sigma$ is found, then the final set
$S$ is $S_{k}$.

In the second phase, the algorithm uses the strings in $S$ as names for states
and constructs a transition function $\delta$ using $S$ and $E$. For each
$s\in S$ and $\sigma\in\Sigma$, there is at least one $s^{\prime}\in S$ such
that $s\sigma$ and $s^{\prime}$ are consistent with respect to $T$. The
algorithm selects any such $s^{\prime}$ and defines
$\delta(s,\sigma)=s^{\prime}$. Once $S$ and $\delta$ are defined, the
algorithm returns the automaton
$\mathcal{M}=\langle\Sigma,S,\varepsilon,\delta\rangle$.

###### Proof of Theorem 5.2.

$E$ may be computed in time polynomial in the length of $T$, by Prop. 2.8.
Because the default acceptor for $T$ has a polynomial number of states and is
consistent with $T$, the number of distinguishable states, and the number of
strings added to $S$, is bounded by a polynomial in the length of $T$. The
returned automaton $\mathcal{M}$ is deterministic and complete by
construction.

Assume the sample $T$ is consistent with $\mathcal{A}$ and subsumes $T_{Aut}$.
For any pair of states of $\mathcal{A}$, the set $E$ includes an experiment to
distinguish them. Also, if $x$ and $y$ reach the same state of $\mathcal{A}$,
there is no experiment in $E$ that distinguishes them. Then the set $S$ is
precisely the access strings of $\mathcal{A}$. The choice of $s^{\prime}$ for
$\delta(s,\sigma)$ is unique in each case, and the returned automaton
$\mathcal{M}$ is isomorphic to the automaton of $\mathcal{A}$. ∎

Although the processes of constructing $T_{Aut}$ and learning an automaton
from it are the same for acceptors of types IBA, ICA, IPA, IRA, ISA, or IMA,
different types of acceptance condition require different kinds of
characteristic samples and learning algorithms.

In the following sections we describe for each type of acceptor the
corresponding sample $T_{Acc}$ and learning algorithm. Each learning algorithm
takes as input an automaton $\mathcal{M}$ and a sample $T$ and returns in
polynomial time an acceptor of the appropriate type consistent with $T$. We
show that for each type of acceptor $\mathcal{A}$, if the input automaton
$\mathcal{M}$ is isomorphic to the automaton of $\mathcal{A}$ and the sample
$T$ is consistent with $\mathcal{A}$ and subsumes the $T_{Acc}$ for
$\mathcal{A}$, then the learning algorithm returns an acceptor that is
equivalent to $\mathcal{A}$. This learning algorithm is then combined with
$\mathbf{L}_{Aut}$ to prove identification in the limit using polynomial time
and data for the relevant class of languages.

##  6\. The samples $T_{Acc}$ and learning algorithms for IMA and IBA

The straightforward cases of Muller, Büchi, and coBüchi acceptance conditions
are covered in this section. Subsequent sections cover the cases of Parity,
Rabin, and Street acceptance conditions, which are somewhat more involved.

###  6.1. Muller acceptors

Let $\mathcal{A}$ be an IMA with acceptance condition
${\alpha}=\\{F_{1},\ldots,F_{k}\\}$. By Prop. 4.3, we may assume that each
$F_{i}$ is a reachable SCC of $\mathcal{A}$. The sample
$T_{Acc}^{\mbox{\scriptsize{IMA}}}$ consists of $k$ positive examples, one for
each set $F_{i}$. The example for $F_{i}$ is $(u(v)^{\omega},1)$ where
${\textsl{inf}}(u(v)^{\omega})=F_{i}$. These examples may be found in
polynomial time in the size of $\mathcal{A}$ by Prop. 4.4.

The learning algorithm $\mathbf{L}_{Acc}^{{\mbox{\scriptsize{IMA}}}}$ takes as
input a deterministic complete automaton $\mathcal{M}$ and a sample $T$. It
constructs an acceptance condition $\alpha^{\prime}$ as follows. For each
positive labeled example $(u(v)^{\omega},1)\in T$, it computes the set
$C=\textit{inf}_{\mathcal{M}}(u(v)^{\omega})$ and makes $C$ a member of
$\alpha^{\prime}$. Once the set $\alpha^{\prime}$ is complete, the algorithm
checks whether the DMA $(\mathcal{M},\alpha^{\prime})$ is consistent with $T$.
If so, it returns $(\mathcal{M},\alpha^{\prime})$; if not, it returns the
default acceptor of type DMA for $T$.

###### Theorem 6.1.

Algorithm $\mathbf{L}_{Acc}^{{\mbox{\scriptsize{IMA}}}}$ runs in time
polynomial in the sizes of the inputs $\mathcal{M}$ and $T$. Let $\mathcal{A}$
be an IMA. If the input automaton $\mathcal{M}$ is isomorphic to the automaton
of $\mathcal{A}$, and the sample $T$ is consistent with $\mathcal{A}$ and
subsumes $T_{Acc}^{\mbox{\scriptsize{IMA}}}$, then algorithm
$\mathbf{L}_{Acc}^{{\mbox{\scriptsize{IMA}}}}$ returns an IMA
$(\mathcal{M},\alpha^{\prime})$ equivalent to $\mathcal{A}$.

###### Proof.

The construction of $\alpha^{\prime}$ can be done in time polynomial in the
sizes of $\mathcal{M}$ and $T$ by Prop. 4.3. The returned acceptor is
consistent with $T$ by construction.

Assume $\mathcal{M}$ is isomorphic to the automaton of $\mathcal{A}$ and that
$T$ is consistent with $\mathcal{A}$. For ease of notation, assume the
isomorphism is the identity. Then for each positive example
$(u(v)^{\omega},1)$ in $T$, the set $F={\textsl{inf}}(u(v)^{\omega})$ must be
in $\alpha$, so $\alpha^{\prime}$ is a subset of $\alpha$.

If $T$ subsumes $T_{Acc}^{\mbox{\scriptsize{IMA}}}$, then for every set
$F\in\alpha$ there is a positive example $(u(v)^{\omega},1)$ in $T$ with
$F={\textsl{inf}}(u(v)^{\omega})$. Thus the set $F$ is added to
$\alpha^{\prime}$, and $\alpha$ is a subset of $\alpha^{\prime}$. Thus,
$(\mathcal{M},\alpha^{\prime})$ is equivalent to $\mathcal{A}$, and because
$T$ is consistent with $\mathcal{A}$, the IMA $(\mathcal{M},\alpha^{\prime})$
is returned by $\mathbf{L}_{Acc}^{{\mbox{\scriptsize{IMA}}}}$. ∎

###### Theorem 6.2.

The class $\mathbb{IM}$ is identifiable in the limit using polynomial time and
data.

###### Proof.

Let $\mathcal{A}$ be an IMA accepting a language $L$. The characteristic
sample $T_{L}=T_{Aut}\cup T_{Acc}^{\mbox{\scriptsize{IMA}}}$ is of size
polynomial in the size of $\mathcal{A}$.

The combined learning algorithm $\mathbf{L}^{{\mbox{\scriptsize{IMA}}}}$ takes
a sample $T$ as input and runs $\mathbf{L}_{Aut}$ on $T$ to produce an
automaton $\mathcal{M}$ and then runs
$\mathbf{L}_{Acc}^{{\mbox{\scriptsize{IMA}}}}$ on $\mathcal{M}$ and $T$ and
returns the resulting acceptor. It runs in polynomial time in the size of $T$
because it is the composition of two polynomial time algorithms, and the
acceptor it returns is guaranteed to be consistent with $T$.

If the sample $T$ is consistent with $\mathcal{A}$ and subsumes $T_{L}$, then
by Theorem 5.2 the automaton $\mathcal{M}$ returned by $\mathbf{L}_{Aut}$ is
isomorphic to the automaton of $\mathcal{A}$. Then by Theorem 6.1 the acceptor
returned by $\mathbf{L}_{Acc}^{{\mbox{\scriptsize{IMA}}}}$ with inputs
$\mathcal{M}$ and $T$ is an IMA equivalent to $\mathcal{A}$. ∎

###  6.2. Büchi acceptors

The case of Büchi acceptors is nearly as straightforward as that of Muller
acceptors. Let $\mathcal{A}$ be an IBA with $n$ states and acceptance
condition $F$. For every state $q$ of $\mathcal{A}$, if there is an
$\omega$-word $w$ such that $\mathcal{A}$ rejects $w$ and
$q\in{\textsl{inf}}(w)$, then there is an example $u(v)^{\omega}$ of length
$O(n^{2})$ such that $\mathcal{A}$ rejects $u(v)^{\omega}$ and
$q\in{\textsl{inf}}(u(v)^{\omega})$, by Prop. 4.4. The negative labeled
example $(u(v)^{\omega},0)$ is included in
$T_{Acc}^{\mbox{\scriptsize{IBA}}}$.

The learning algorithm $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IBA}}}$ takes as
input a deterministic complete automaton $\mathcal{M}$ and a sample $T$. The
acceptance condition $F^{\prime}$ consists of all the states $q$ of
$\mathcal{M}$ such that for no negative example $(u(v)^{\omega},0)$ in $T$ do
we have $q\in{\textsl{inf}}_{\mathcal{M}}(u(v)^{\omega})$. Once $F^{\prime}$
has been computed, the algorithm checks whether the DBA
$(\mathcal{M},F^{\prime})$ is consistent with the sample $T$. If so, it
returns $(\mathcal{M},F^{\prime})$; if not, it returns the default acceptor of
type DBA for $T$.

###### Theorem 6.3.

Algorithm $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IBA}}}$ runs in time polynomial
in the sizes of the inputs $\mathcal{M}$ and $T$. Let $\mathcal{A}$ be an IBA.
If the input automaton $\mathcal{M}$ is isomorphic to the automaton of
$\mathcal{A}$, and the sample $T$ is consistent with $\mathcal{A}$ and
subsumes $T_{Acc}^{\mbox{\scriptsize{IBA}}}$, then algorithm
$\mathbf{L}_{Acc}^{\mbox{\scriptsize{IBA}}}$ returns an IBA
$(\mathcal{M},F^{\prime})$ equivalent to $\mathcal{A}$.

###### Proof.

The construction of $F^{\prime}$ can be done in time polynomial in the sizes
of $\mathcal{M}$ and $T$ by Prop. 4.3. The returned acceptor is consistent
with $T$ by construction.

Assume the input $\mathcal{M}$ is isomorphic to the automaton of
$\mathcal{A}$, and that $T$ is consistent with $\mathcal{A}$ and subsumes
$T_{Acc}^{\mbox{\scriptsize{IBA}}}$. For ease of notation, assume the
isomorphism is the identity. We show that the DBA $(\mathcal{M},F^{\prime})$
is equivalent to $\mathcal{A}$.

If $\mathcal{A}$ rejects the word $u(v)^{\omega}$ then let
$C=\textit{inf}_{\mathcal{M}}(u(v)^{\omega})$. Because $T$ subsumes
$T_{Acc}^{\mbox{\scriptsize{IBA}}}$, for each $q\in C$, there is a negative
example $(u^{\prime}(v^{\prime})^{\omega},0)$ in $T$ such that
$q\in\textit{inf}_{\mathcal{M}}(u^{\prime}(v^{\prime})^{\omega})$. Thus no
$q\in C$ is in $F^{\prime}$ and $(\mathcal{M},F^{\prime})$ also rejects
$u(v)^{\omega}$.

Conversely, if $\mathcal{A}$ accepts the word $u(v)^{\omega}$, then there is
at least one state $q\in F$ such that
$q\in{\textsl{inf}}_{\mathcal{M}}(u(v)^{\omega})$. Because $T$ is consistent
with $\mathcal{A}$, there is no negative example $(u(v)^{\omega},0)$ in $T$
such that $q\in\textit{inf}_{\mathcal{M}}(u(v)^{\omega})$, so $q\in
F^{\prime}$ and $(\mathcal{M},F^{\prime})$ also accepts $u(v)^{\omega}$. Thus
$(\mathcal{M},F^{\prime})$ is equivalent to $\mathcal{A}$. Because $T$ is
consistent with $\mathcal{A}$, the IBA $(\mathcal{M},F^{\prime})$ is returned
by $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IBA}}}$. ∎

###### Theorem 6.4.

The classes $\mathbb{IB}$ and $\mathbb{IC}$ are identifiable in the limit
using polynomial time and data.

###### Proof.

The result for $\mathbb{IC}$ follows from that for $\mathbb{IB}$ by Prop. 4.1.
Let $\mathcal{A}$ be an IBA accepting language $L$. The characteristic sample
$T_{L}=T_{Aut}\cup T_{Acc}^{\mbox{\scriptsize{IBA}}}$ is of size polynomial in
the size of $\mathcal{A}$.

The combined learning algorithm $\mathbf{L}^{\mbox{\scriptsize{IBA}}}$ takes a
sample $T$ as input and runs $\mathbf{L}_{Aut}$ to get a deterministic
complete automaton $\mathcal{M}$. It then runs
$\mathbf{L}_{Acc}^{\mbox{\scriptsize{IBA}}}$ on inputs $\mathcal{M}$ and $T$,
and returns the resulting acceptor. $\mathbf{L}^{\mbox{\scriptsize{IBA}}}$
runs in polynomial time in the length of $T$ and returns a DBA consistent with
$T$.

If the sample $T$ is consistent with $\mathcal{A}$ and subsumes $T_{L}$ then
$\mathbf{L}_{Aut}$ returns an automaton $\mathcal{M}$ isomorphic to the
automaton of $\mathcal{A}$ by Theorem 5.2. Then the acceptor returned by
$\mathbf{L}_{Acc}^{\mbox{\scriptsize{IBA}}}$ on inputs $\mathcal{M}$ and $T$
is an IBA equivalent to $\mathcal{A}$ by Theorem 6.3. ∎

##  7\. The sample $T_{Acc}$ and learning for IPA

The construction of $T_{Acc}^{\mbox{\scriptsize{IPA}}}$ for an IPA
$\mathcal{P}$ builds on the construction of the canonical forest of SCCs for
$\mathcal{P}$, whose construction and properties are described next.

###  7.1. Constructing the Canonical Forest and Coloring of a DPA

Let $\mathcal{P}=\langle\Sigma,Q,q_{\iota},\delta,\kappa\rangle$ be a complete
DPA. We extend the coloring function $\kappa$ to nonempty sets of states by
$\kappa(S)=\min\\{k(q)\mid q\in S\\}$, the minimum color of any state in $S$.
We define the _$\kappa$ -parity_ of $S$ to be $1$ if $\kappa(S)$ is odd, and
$0$ if $\kappa(S)$ is even. A word $w\in\Sigma^{\omega}$ is accepted by
$\mathcal{P}$ iff the $\kappa$-parity of ${\textsl{inf}}(w)$ is $1$. Note that
the union of two sets of $\kappa$-parity $b$ is also of $\kappa$-parity $b$.
For any nonempty $S\subseteq Q$, we define $\textit{minStates}(S)=\\{q\in
S\mid\kappa(q)=\kappa(S)\\}$, the states of $S$ that are assigned the minimum
color among all states of $S$.

####  7.1.1. The minStates-Forest.

We describe an algorithm to construct the _minStates -forest of
$\mathcal{P}$_. The roots of the minStates-forest are the elements of
$\textit{maxSCCs}(Q)$, each marked as unprocessed. If $C$ is unprocessed, then
${\mathcal{D}}=\textit{maxSCCs}(C\setminus\textit{minStates}(C))$ is computed.
If ${\mathcal{D}}$ is empty, $C$ becomes a leaf in the forest, and is marked
as processed. Otherwise, $C$ is marked as processed and the elements of
${\mathcal{D}}$ are made the children of $C$ and are marked as unprocessed.

###### Proposition 7.1.

Let $\mathcal{P}=\langle\Sigma,Q,q_{\iota},\delta,\kappa\rangle$ be a complete
DPA with automaton $\mathcal{M}$. Let $\mathcal{F}$ be the minStates-forest of
$\mathcal{P}$. Then $\mathcal{F}$ is a decreasing forest of SCCs of
$\mathcal{M}$ rooted in $Q$, and can be computed in polynomial time. For any
SCC $D$, $\kappa(D)=\kappa(\mathbf{Node}(D,\mathcal{F}))$.

###### Proof.

Referring to the construction of the minStates-forest $\mathcal{F}$, its roots
are the elements of $\textit{maxSCCs}(Q)$. When a node $C$ is processed, the
nonempty set $\textit{minStates}(C)$ is removed and the maximum SCCs (if any)
of the result become the children of $C$, so the union of the children of $C$
is a proper subset of $C$, and the children are the maximum SCCs of
$C\setminus\Delta(C)$. Let $D$ be an SCC. Then $D\subseteq Q$ and for the node
$C=\mathbf{Node}(D,\mathcal{F})$, we have that $D\subseteq C$ and $D$ is not a
subset of any child of $C$. Thus $D\cap\textit{minStates}(C)\neq\emptyset$,
because otherwise $D$ would be a subset of some child of $C$. This implies
that $\kappa(D)=\kappa(C)$. The minStates-forest of $\mathcal{P}$ can be
computed in polynomial time because it has at most $|Q|$ nodes, and each set
$\textit{maxSCCs}(S)$ can be computed in polynomial time by Prop. 4.7. ∎

####  7.1.2. The Canonical Forest and Coloring.

The canonical forest of $\mathcal{P}$ is constructed as follows, starting with
the minStates-forest of $\mathcal{P}$. While there exist in the forest a node
$D$ and its parent $C$ of the same $\kappa$-parity, one such pair $D$ and $C$
is selected, and the child node $D$ is merged into the parent node $C$. When
no such pair remains, the result is the _canonical forest of $\mathcal{P}$_,
denoted $\mathcal{F}^{*}(\mathcal{P})$. The canonical forest
$\mathcal{F}^{*}(\mathcal{P})$ can be computed from $\mathcal{P}$ in
polynomial time.

From the canonical forest $\mathcal{F}^{*}(\mathcal{P})$, we define the
_canonical coloring_ $\kappa^{*}$. The states in
$(Q\setminus\bigcup\textit{maxSCCs}(Q))$ are not contained in any SCC of
$\mathcal{P}$ and do not affect the acceptance or rejection of any
$\omega$-word. For definiteness, we assign them $\kappa^{*}(q)=0$. For a root
node $C$ of $\kappa$-parity $b$, we define $\kappa^{*}(q)=b$ for all
$q\in\Delta(C)$. Let $C$ be an arbitrary node of
$\mathcal{F}^{*}(\mathcal{P})$. If the states of $\Delta(C)$ have been
assigned color $k$ by $\kappa^{*}$ and $D$ is a child of $C$, then the states
of $\Delta(D)$ are assigned color $k+1$ by $\kappa^{*}$. Clearly $\kappa^{*}$
can be computed from $\mathcal{P}$ in polynomial time.

##### An Example.

Figure 3(a) shows the graph $G(\mathcal{P})$ of a DPA $\mathcal{P}$ with
states $a$ through $m$, labeled by the colors assigned by $\kappa$. Figure
3(b) shows the minStates-forest of $\mathcal{P}$, with the nodes labeled by
their $\kappa$-parities. Figure 3(c) shows the canonical forest
$\mathcal{F}^{*}(\mathcal{P})$ of $\mathcal{P}$, with the nodes labeled by
their $\kappa$-parities. Figure 3(d) shows the graph $G(\mathcal{P})$ re-
colored using the canonical coloring $\kappa^{*}$.

$a:1$$b:3$$h:4$$i:3$$c:1$$d:5$$e:4$$f:4$$g:5$$j:4$$k:5$$l:2$$m:4$(a)$a,b,c,d,e,f,g,h:1$$f,g:0$$b,d,e:1$$d,e:0$$i,j,k:1$$j,k:0$$l,m:0$$m:0$(b)$a,b,c,d,e,f,g,h:1$$f,g:0$$d,e:0$$i,j,k:1$$j,k:0$$l,m:0$$a:1$$b:1$$h:1$$i:1$$c:1$$d:2$$e:2$$f:2$$g:2$$j:2$$k:2$$l:0$$m:0$(d)(c)

Figure 3.  (a) Graph $G(\mathcal{P})$ with states colored by $\kappa$. (b) The
minStates-forest of $\mathcal{P}$, with $\kappa$-parities of nodes. (c)
Canonical forest $\mathcal{F}^{*}(\mathcal{P})$, with $\kappa$-parities of
nodes. (d) Graph $G(\mathcal{P})$ with the canonical coloring $\kappa^{*}$.

###### Theorem 7.2.

Let $\mathcal{P}=\langle\Sigma,Q,q_{\iota},\delta,\kappa\rangle$ be a complete
DPA with automaton $\mathcal{M}$. The canonical forest
$\mathcal{F}^{*}(\mathcal{P})$ is a decreasing forest of SCCs of $\mathcal{M}$
rooted in $Q$ and has the following properties.

  1. (1)

For any SCC $D$, $D$ and $\mathbf{Node}(D,\mathcal{F}^{*}(\mathcal{P}))$ have
the same $\kappa$-parity.

  2. (2)

For every node $C$ of $\mathcal{F}^{*}(\mathcal{P})$, the $\kappa$-parity of
$C$ is the same as the $\kappa^{*}$-parity of $C$.

  3. (3)

The children in $\mathcal{F}^{*}(\mathcal{P})$ of a node $C$ of
$\kappa$-parity $b$ are the maximal SCCs $D\subseteq C$ of $\kappa$-parity
$1-b$.

###### Proof.

Because $\mathcal{F}^{*}(\mathcal{P})$ is obtained from the minStates-forest
of $\mathcal{P}$ by a sequence of merges, $\mathcal{F}^{*}(\mathcal{P})$ is a
decreasing forest of SCCs of $\mathcal{M}$ rooted in $Q$ by Prop. 4.9. Let
$\mathcal{F}_{0}$ denote the minStates-forest of $\mathcal{P}$, and let
$\mathcal{F}_{i}$ denote the forest after $i$ merges have been performed in
the computation to produce the canonical acceptor
$\mathcal{F}^{*}(\mathcal{P})$.

By Prop. 7.1, for any SCC $D$,
$\kappa(D)=\kappa(\mathbf{Node}(D,\mathcal{F}_{0}))$, so property (1) holds
for $\mathcal{F}_{0}$. We show by induction that it holds for each
$\mathcal{F}_{i}$ and therefore for $\mathcal{F}^{*}(\mathcal{P})$. Assume
that property (1) holds of $\mathcal{F}_{i}$, and $\mathcal{F}_{i+1}$ is
obtained from $\mathcal{F}_{i}$ by merging child node $D$ into parent node
$C$. Let $D^{\prime}$ be any SCC. If
$\mathbf{Node}(D^{\prime},\mathcal{F}_{i})=\mathbf{Node}(D^{\prime},\mathcal{F}_{i+1})$,
then because property (1) holds in $\mathcal{F}_{i}$, we have that the
$\kappa$-parity of $D^{\prime}$ is the same as the $\kappa$-parity of
$\mathbf{Node}(D^{\prime},\mathcal{F}_{i+1})$. Otherwise, it must be that
$D=\mathbf{Node}(D^{\prime},\mathcal{F}_{i})$ and
$C=\mathbf{Node}(D^{\prime},\mathcal{F}_{i+1})$. Because $D$ is only merged to
$C$ if they are of the same $\kappa$-parity, this implies that the
$\kappa$-parity of $D^{\prime}$ is the same as the $\kappa$-parity of $C$.
Thus, property (1) holds also in $\mathcal{F}_{i+1}$.

For property (2), we note that the $\kappa$-parity and the $\kappa^{*}$-parity
of each root node of $\mathcal{F}^{*}(\mathcal{P})$ is the same. Suppose $C$
is a node of $\mathcal{F}^{*}(\mathcal{P})$ whose $\kappa$-parity and
$\kappa^{*}$-parity are equal to $b$, and $D$ is a child of $C$. Then by the
construction of $\mathcal{F}^{*}(\mathcal{P})$, the $\kappa$-parity of $D$ is
$1-b$. And by the definition of $\kappa^{*}$, the $\kappa^{*}$ parity of the
elements of $\Delta(D)$ is the opposite of the $\kappa^{*}$-parity of the
elements of $\Delta(C)$. Because the $\kappa^{*}$-parity of $C$ is $b$, the
$\kappa^{*}$-parity of $D$ is also $1-b$.

For property (3), let $D$ be any maximal SCC of $\mathcal{P}$ that is
contained in $C$ and has $\kappa$-parity $1-b$. Then
$\mathbf{Node}(D,\mathcal{F}_{0})$ is contained in $C$ and has the same
$\kappa$-parity as $D$. Because $D$ is maximal, we must have
$D=\mathbf{Node}(D,\mathcal{F}_{0})$, and any nodes on the path between $C$
and $D$ must have $\kappa$-parity $b$ and must be merged into $C$ to form
$\mathcal{F}^{*}(\mathcal{P})$. Thus, $D$ is a child of $C$ in
$\mathcal{F}^{*}(\mathcal{P})$.

Conversely, if $D$ is a child of $C$ in $\mathcal{F}^{*}(\mathcal{P})$ then
$D\subseteq C$ and the $\kappa$-parity of $D$ is $1-b$. Assume $D^{\prime}$ is
an SCC such that $D^{\prime}\subseteq C$, the $\kappa$-parity of $D^{\prime}$
is $1-b$ and $D\subsetneq D^{\prime}$. Then
$D^{\prime\prime}=\mathbf{Node}(D^{\prime},\mathcal{F}_{0})$ is a descendant
of $C$ in $\mathcal{F}_{0}$ that has $\kappa$-parity $1-b$, and $D\subsetneq
D^{\prime\prime}$, so because there is another node of parity $1-b$ on the
path between $D$ and $C$ in $\mathcal{F}_{0}$, $D$ cannot be a child of $C$ in
$\mathcal{F}^{*}(\mathcal{P})$, a contradiction. ∎

Replacing the coloring function of $\mathcal{P}$ by the canonical coloring
does not change the $\omega$-language accepted.

###### Theorem 7.3.

Let $\mathcal{P}=\langle\Sigma,Q,q_{\iota},\delta,\kappa\rangle$ be a complete
DPA, and $\mathcal{P}^{*}$ be $\mathcal{P}$ with the canonical coloring
$\kappa^{*}$ for $\mathcal{P}$ in place of $\kappa$. Then $\mathcal{P}$ and
$\mathcal{P}^{*}$ recognize the same $\omega$-language.

###### Proof.

Let $w$ be an $\omega$-word and let $D={\textsl{inf}}(w)$. This is an SCC of
the (common) automaton of $\mathcal{P}$ and $\mathcal{P}^{*}$. Let
$C=\mathbf{Node}(D,\mathcal{F}^{*}(\mathcal{P}))$. Then
$D\cap\Delta(C)\neq\emptyset$, and $\kappa^{*}(D)=\kappa^{*}(C)$, by the
definition of $\kappa^{*}$, The $\kappa^{*}$ parity of $C$ is the same as the
$\kappa$-parity of $C$, by property (2) of Theorem 7.2. The $\kappa$-parity of
$C$ is the same as the $\kappa$-parity of $D$, by property (1) of Theorem 7.2.
Thus, the $\kappa^{*}$-parity of $D$ is the same as the $\kappa$-parity of
$D$, and $w\in{\llbracket}\mathcal{P}{\rrbracket}$ iff
$w\in{\llbracket}\mathcal{P}^{*}{\rrbracket}$. ∎

###  7.2. Constructing $T_{Acc}^{\mbox{\scriptsize{IPA}}}$

We now describe the construction of $T_{Acc}^{\mbox{\scriptsize{IPA}}}$, the
second part of the characteristic sample for an IPA $\mathcal{P}$ with the
automaton $\mathcal{M}$ of $n$ states. The sample
$T_{Acc}^{\mbox{\scriptsize{IPA}}}$ consists of one example
$u(v)^{\omega}=\mathbf{Witness}(C,\mathcal{M})$ of length $O(n^{2})$ for each
reachable SCC $C$ in the canonical forest $\mathcal{F}^{*}(\mathcal{P})$. The
example $u(v)^{\omega}$ is labeled $1$ if it is accepted by $\mathcal{P}$ and
otherwise is labeled $0$. Thus $T_{Acc}^{\mbox{\scriptsize{IPA}}}$ contains at
most $n$ labeled examples, each of length $O(n^{2})$.

###  7.3. The learning algorithm $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IPA}}}$

Given a complete deterministic automaton
$\mathcal{M}=\langle\Sigma,Q,q_{\iota},\delta\rangle$ and a sample $T$ as
input, the learning algorithm $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IPA}}}$
attempts to construct a coloring of the states of $\mathcal{M}$ consistent
with $T$.

The algorithm first constructs the set $Z$ of all $C\subseteq Q$ such that for
some labeled example $(u(v)^{\omega},l)$ in $T$ we have
$C=\textit{inf}_{\mathcal{M}}(u(v)^{\omega})$. If two examples with different
labels are found to yield the same set $C$, this is evidence that the
automaton $\mathcal{M}$ is not correct, and the learning algorithm returns the
default acceptor of type DPA for $T$.

Otherwise, each set $C$ in $Z$ is associated with the label of the one or more
examples that yield $C$. The set $Z$ is partially ordered by the subset
relation. The learning algorithm then attempts to construct a rooted forest
$\mathcal{F}^{\prime}$ with nodes that are elements of $Z$, corresponding to
the canonical forest of the target acceptor. Initially, $\mathcal{F}^{\prime}$
contains as roots all the maximal elements of $Z$. If these are not pairwise
disjoint, it returns the default acceptor of type DPA for $T$. Otherwise, the
root nodes are all marked as unprocessed.

For each unprocessed node $C$ in $\mathcal{F}^{\prime}$, it computes the set
of all $D\in Z$ such that $D\subseteq C$, $D$ has the opposite label to $C$,
and $D$ is maximal with these properties, and makes $D$ a child of $C$ and
marks $D$ as unprocessed. When all the children of a node $C$ have been
determined, the algorithm checks two conditions: (1) that the children of $C$
are pairwise disjoint, and (2) there is at least one $q\in C$ that is not in
any child of $C$. If either of these conditions fail, then it returns the
default acceptor of type DPA for $T$. If both conditions are satisfied, then
the node $C$ is marked as processed. When there are no more unprocessed nodes,
the construction of $\mathcal{F}^{\prime}$ is complete. Note that
$\mathcal{F}^{\prime}$ has at most $|Q|$ nodes.

When the construction of $\mathcal{F}^{\prime}$ is complete, for each node $C$
in $\mathcal{F}^{\prime}$ let $\Delta(C)$ denote the elements of $C$ that do
not appear in any of its children. Then the learning algorithm assigns colors
to the elements of $Q$ starting from the roots of $\mathcal{F}^{\prime}$, as
follows. If $C$ is a root with label $l$, then $\kappa^{\prime}(q)=l$ for all
$q\in\Delta(C)$. If the elements of $\Delta(C)$ have been assigned color $k$
and $D$ is a child of $C$, then $\kappa^{\prime}(q)=k+1$ for all
$s\in\Delta(D)$. When this process is complete, any uncolored states $q$ are
assigned $\kappa^{\prime}(q)=0$.

If the resulting DPA $(\mathcal{M},\kappa^{\prime})$ is consistent with the
sample $T$, the algorithm $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IPA}}}$ returns
$(\mathcal{M},\kappa^{\prime})$. If not, it returns the default acceptor of
type DPA for $T$.

###### Theorem 7.4.

Algorithm $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IPA}}}$ runs in time polynomial
in the sizes of the inputs $\mathcal{M}$ and $T$. Let $\mathcal{P}$ be an IPA.
If the input automaton $\mathcal{M}$ is isomorphic to the automaton of
$\mathcal{P}$, and the sample $T$ is consistent with $\mathcal{P}$ and
subsumes $T_{Acc}^{\mbox{\scriptsize{IPA}}}$, then algorithm
$\mathbf{L}_{Acc}^{\mbox{\scriptsize{IPA}}}$ returns an IPA
$(\mathcal{M},\kappa^{\prime})$ equivalent to $\mathcal{P}$.

###### Proof.

The construction of $\kappa^{\prime}$ can be done in time polynomial in the
sizes of $\mathcal{M}$ and $T$. The returned acceptor is consistent with $T$
by construction.

Assume the input $\mathcal{M}=\langle\Sigma,Q,q_{\iota},\delta\rangle$ is
isomorphic to the automaton of $\mathcal{P}$, and that $T$ is consistent with
$\mathcal{P}$ and subsumes $T_{Acc}^{\mbox{\scriptsize{IPA}}}$. For ease of
notation, assume the isomorphism is the identity. We show that the forest
$\mathcal{F}^{\prime}$ constructed by the learning algorithm is equal to the
canonical forest of $\mathcal{F}^{*}(\mathcal{P})$, the coloring
$\kappa^{\prime}$ is equal to the canonical coloring $\kappa^{*}$, and
therefore the acceptor $(\mathcal{M},\kappa^{\prime})$ is equivalent to
$\mathcal{P}$.

The roots of $\mathcal{F}^{*}(\mathcal{P})$ are the maximal SCCs contained in
$Q$, and for each such root $C$, $T_{Acc}^{\mbox{\scriptsize{IPA}}}$ contains
an example $(u(v)^{\omega},l)$ such that $C={\textsl{inf}}(u(v)^{\omega})$.
Thus, the set of maximal elements of $Z$ is equal to the set of roots of
$\mathcal{F}^{*}(\mathcal{P})$.

Let $C$ be any node of $\mathcal{F}^{*}(\mathcal{P})$, and let $D$ be a child
of $C$ in $\mathcal{F}^{*}(\mathcal{P})$. Then $D$ is an SCC, $D\subseteq C$,
the parity of $D$ is opposite to the parity of $C$, and $D$ is maximal in the
subset ordering with these properties, by property (3) of Theorem 7.2. In the
sample $T_{Acc}^{\mbox{\scriptsize{IPA}}}$ there is an example
$(u(v)^{\omega},l)$ with $D={\textsl{inf}}(u(v)^{\omega})$, so $D$ is an
element of $Z$, and will be made a child of $C$ in $\mathcal{F}^{\prime}$
because $D\subseteq C$, the label $l$ is the opposite of the label of $C$, and
$D$ is maximal in $Z$ with these properties. Conversely, if $D$ is made a
child of $C$ in $\mathcal{F}^{\prime}$, then $D\subseteq C$, the label of $D$
is opposite to the label of $C$ (that is, they are of opposite
$\kappa$-parity), and $D$ is maximal in $Z$ with these properties. This
implies $D$ is a child of $C$ in $\mathcal{F}^{*}(\mathcal{P})$, by property
(3) of Theorem 7.2.

By induction, $\mathcal{F}^{\prime}$ is equal to
$\mathcal{F}^{*}(\mathcal{P})$, and therefore $\kappa^{\prime}$ is equal to
the canonical coloring $\kappa^{*}$. Then the IPA
$(\mathcal{M},\kappa^{\prime})$ is equivalent to $\mathcal{P}$, by Theorem
7.3. Because $T$ is consistent with $\mathcal{P}$, the IPA
$(\mathcal{M},\kappa^{\prime})$ is returned by
$\mathbf{L}_{Acc}^{\mbox{\scriptsize{IBA}}}$. ∎

###### Theorem 7.5.

The class $\mathbb{IP}$ is identifiable in the limit using polynomial time and
data.

###### Proof.

Let $\mathcal{P}$ be an IPA accepting the language $L$. The characteristic
sample $T_{L}=T_{Aut}\cup T_{Acc}$ for $\mathcal{P}$ is of size polynomial in
the size of $\mathcal{P}$.

The combined learning algorithm $\mathbf{L}^{\mbox{\scriptsize{IPA}}}$ with a
sample $T$ as input first runs $\mathbf{L}_{Aut}$ on $T$ to get a complete
deterministic automaton $\mathcal{M}$ and then runs
$\mathbf{L}_{Acc}^{\mbox{\scriptsize{IPA}}}$ on inputs $\mathcal{M}$ and $T$
and returns the resulting acceptor. The running time of
$\mathbf{L}^{\mbox{\scriptsize{IPA}}}$ is polynomial in the length of $T$ and
the returned acceptor is consistent with $T$.

Assume that the sample $T$ is consistent with $\mathcal{P}$ and subsumes
$T_{L}$. Then by Theorem 5.2, the automaton $\mathcal{M}$ is isomorphic to the
automaton of $\mathcal{P}$. By Theorem 7.4, the acceptor
$(\mathcal{M},\kappa^{\prime})$ is equivalent to $\mathcal{P}$. Because it is
consistent with $T$, the IPA $(\mathcal{M},\kappa^{\prime})$ is the acceptor
returned by $\mathbf{L}^{\mbox{\scriptsize{IPA}}}$. ∎

A corollary of Theorem 7.5 is that the class of languages recognized by
deterministic weak Parity acceptors ($\mathbb{DWPA}$), which was shown to be
polynomially learnable using membership and equivalence queries by Maler and
Pnueli (Maler and Pnueli, 1991), is identifiable in the limit using polynomial
time and data. This class (which is equivalent to the intersection of classes
$\mathbb{DBA}\cap\mathbb{DCA}$) was shown to be a subset of $\mathbb{IM}$ in
(Staiger, 1983), and to be a subset of $\mathbb{IP}$ in (Angluin and Fisman,
2018).

###### Corollary 7.6.

The class $\mathbb{DWPA}$ is identifiable in the limit using polynomial time
and data.

##  8\. The sample $T_{Acc}$ and learning for IRA

In this section we introduce some terminology, establish a normal form for
Rabin acceptors, define an ordering on sets of states of an automaton, and
then describe the learning algorithm
$\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$ and sample
$T_{Acc}^{\mbox{\scriptsize{IRA}}}$ for IRAs. We then prove that the classes
$\mathbb{IR}$ and $\mathbb{IS}$ are identifiable in the limit using polynomial
time and data.

Let $\mathcal{R}=\langle\Sigma,Q,q_{i},\delta,\alpha\rangle$ be a Rabin
acceptor, where the acceptance condition
$\alpha=\\{(G_{1},B_{1}),\ldots,(G_{k},B_{k})\\}$ is a set of ordered pairs of
states. We say that an $\omega$-word $w$ _satisfies a pair of state sets_
$(G,B)$ iff ${\textsl{inf}}(w)\cap G\neq\emptyset$ and ${\textsl{inf}}(w)\cap
B=\emptyset$. Also, $w$ _satisfies the acceptance condition_ $\alpha$ iff
there exists $i\in[1..k]$ such that $w$ satisfies $(G_{i},B_{i})$. Then an
$\omega$-word $w$ is accepted by $\mathcal{R}$ iff $w$ satisfies the
acceptance condition $\alpha$ of $\mathcal{R}$.

###  8.1. Singleton normal form for a Rabin acceptor

We say that a Rabin acceptor $\mathcal{R}$ is in _singleton normal form_ iff
for every pair $(G_{i},B_{i})$ in its acceptance condition we have
$|G_{i}|=1$, that is, every $G_{i}$ is a singleton set. To avoid extra braces,
we abbreviate the pair $(\\{q\\},B)$ by $(q,B)$. Every Rabin acceptor may be
put into singleton normal form by a polynomial time algorithm.

###### Proposition 8.1.

Let $\mathcal{R}=\langle\Sigma,Q,q_{\iota},\delta,\alpha\rangle$ be a Rabin
acceptor with acceptance condition
$\alpha=\\{(G_{1},B_{1}),\ldots,(G_{k},B_{k})\\}$. Define the acceptance
condition $\alpha^{\prime}$ to contain $(q,B_{i})$ for every $i\in[1..k]$ and
$q\in G_{i}$, and let $\mathcal{R}^{\prime}$ be $\mathcal{R}$ with $\alpha$
replaced by $\alpha^{\prime}$. Then $\mathcal{R}^{\prime}$ is in singleton
normal form and accepts the same language as $\mathcal{R}$. Also,
$\mathcal{R}^{\prime}$ is of size at most $|Q|$ times the size of
$\mathcal{R}$.

###### Proof.

If an $\omega$-word $w$ satisfies a pair $(q,B)$ of $\alpha^{\prime}$, then
there exists a pair $(G_{i},B_{i})$ of $\alpha$ with $q\in G_{i}$ and
$B_{i}=B$, so $w$ also satisfies the pair $(G_{i},B_{i})$ in $\alpha$.
Conversely, if $w$ satisfies a pair $(G_{i},B_{i})$ in $\alpha$, then there
exists $q\in G_{i}$ such that $q\in{\textsl{inf}}(w)$, so $w$ also satisfies
$(q,B_{i})$ in $\alpha^{\prime}$. Each pair $(G_{i},B_{i})$ in $\alpha$ is
replaced by at most $|Q|$ pairs in $\alpha^{\prime}$. ∎

###  8.2. An ordering on sets of states

Given an automaton, we define an ordering $\preceq$ on sets of its states that
is used to coordinate between the characteristic sample and the learning
algorithm for an IRA.

Let $\mathcal{M}=\langle\Sigma,Q,q_{\iota},\delta\rangle$ be a deterministic
complete automaton in which every state is reachable from the start state.
Recall from Section 5.2 that $\textit{access}(q)$ is the shortlex least string
$s\in\Sigma^{*}$ such that $\delta(q_{\iota},s)=q$.

For a set of states $S$, we define $\textit{access}(S)$ to be the sequence of
values $\textit{access}(q)$ for $q\in S$, sorted into increasing shortlex
order. We define the total ordering $\preceq$ on sets of states of
$\mathcal{M}$ as follows. If $S_{1},S_{2}\subseteq Q$, then $S_{1}\preceq
S_{2}$ iff either $|S_{1}|<|S_{2}|$ or $|S_{1}|=|S_{2}|$ and the sequence
$\textit{access}(S_{1})$ is less than or equal to the sequence
$\textit{access}(S_{2})$ in the lexicographic ordering, using the shortlex
ordering on $\Sigma^{*}$ to compare the component entries. For example, if
$\textit{access}(S_{1})=\langle\epsilon,a,baa\rangle$,
$\textit{access}(S_{2})=\langle a,ba\rangle$, and
$\textit{access}(S_{3})=\langle\epsilon,ab,ba\rangle$ then $S_{2}\preceq
S_{1}\preceq S_{3}$.

###  8.3. The learning algorithm $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$

We begin with the description of the learning algorithm
$\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$, which is used in the definition
of the sample $T_{Acc}^{\mbox{\scriptsize{IRA}}}$ in the next section. The
inputs to $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$ are a deterministic
complete automaton $\mathcal{M}$ and a sample $T$. The algorithm attempts to
construct a singleton normal form Rabin acceptance condition $\beta$ to
produce an acceptor $(\mathcal{M},\beta)$ consistent with $T$.

The processing of an example $w$ from $T$ depends only on
$\textit{inf}_{\mathcal{M}}(w)$. The algorithm first computes the set
$\\{\textit{inf}_{\mathcal{M}}(w)\mid(w,1)\in T\\}$, sorts its elements into
decreasing order $C_{1},C_{2},\ldots,C_{\ell}$ using $\preceq$, and for each
$i\in[1..\ell]$ chooses a positive example $(z_{i},1)\in T$ with
$C_{i}=\textit{inf}_{\mathcal{M}}(z_{i})$.

At each stage $k$ of the learning algorithm, $\beta_{k}$ is a singleton normal
form acceptance condition. Initially, $\beta_{0}=\emptyset$ (which is
satisfied by no words) and $k=0$.

The main loop processes the positive examples $z_{i}$ for $i=1,2,\ldots,\ell$.
If $z_{i}$ is accepted by $(\mathcal{M},\beta_{k})$, then the algorithm goes
on to the next positive example. Otherwise, we say that the example $z_{i}$
_causes the update of_ $\beta_{k}$. Let $G=\textit{inf}_{\mathcal{M}}(z_{i})$
and $B=Q\setminus G$ and let $S_{k}$ be the set of pairs $(q,B)$ such that
$q\in G$ and there is no negative example $(w,0)$ in $T$ such that $w$
satisfies $(q,B)$. Then $\beta_{k+1}$ is set to $\beta_{k}\cup S_{k}$ and $k$
is set to $k+1$.

When the positive examples $z_{1},z_{2},\ldots,z_{\ell}$ have been processed,
let $\beta=\beta_{k}$ for the final value of $k$. If the Rabin acceptor
$(\mathcal{M},\beta)$ is consistent with $T$, then it is returned. If not, the
learning algorithm returns the default acceptor of type DRA for $T$.

###### Proposition 8.2.

Let $\mathcal{R}$ be an IRA in singleton normal form with acceptance condition
$\alpha$ and assume that the input $\mathcal{M}$ is an automaton isomorphic to
the automaton of $\mathcal{R}$. Assume the sample $T$ is consistent with
$\mathcal{R}$. For each $k$, if $z_{i}$ is the example that causes the update
of $\beta_{k}$, then $(\mathcal{M},\beta_{k})$ accepts $z_{j}$ for all $j<i$.
Moreover, $(\mathcal{M},\beta)$ is consistent with $T$.

###### Proof.

No pair $(q,B)$ is added to the acceptance condition if there is a negative
example in $T$ that satisfies it, so $(\mathcal{M},\beta)$ is consistent with
all the negative examples in $T$.

Consider any positive example $(w,1)$ from $T$. There exists $i$ with
$\textit{inf}_{\mathcal{M}}(w)=\textit{inf}_{\mathcal{M}}(z_{i})$. When
$z_{i}$ is processed by the algorithm, if it is already accepted by the
current $(\mathcal{M},\beta_{k})$, then it (and the word $w$) is also accepted
by every subsequent hypothesis, including $(\mathcal{M},\beta)$, because pairs
are not removed from $\beta_{k}$.

Otherwise, $z_{i}$ causes the update to $\beta_{k}$, and among the pairs in
$S_{k}$ that are added to $\beta_{k}$ is at least one that $z_{i}$ satisfies.
To see this, note that $z_{i}$ must satisfy some pair in $\alpha$, say
$(q,B_{j})$. Thus, $q\in{\textsl{inf}}(z_{i})$ and
$B_{j}\cap{\textsl{inf}}(z_{i})=\emptyset$. The pair $(q,B)$ where
$B=Q\setminus{\textsl{inf}}(z_{i})$ has $B_{j}\subseteq B$. Thus any
$\omega$-word that satisfies $(q,B)$ will also satisfy $(q,B_{j})$. Because
$T$ is consistent with $\mathcal{R}$, there can be no negative example in $T$
satisfying $(q,B)$, so pair $(q,B)$ is part of $S_{k}$ and is added to
$\beta_{k}$. The word $z_{i}$ (and the word $w$) satisfies $(q,B)$ and is
therefore accepted by $(\mathcal{M},\beta_{k+1})$ and every subsequent
hypothesis, including $(\mathcal{M},\beta)$. ∎

###  8.4. Constructing $T_{Acc}^{\mbox{\scriptsize{IRA}}}$

In this section we describe the construction of the sample
$T_{Acc}^{\mbox{\scriptsize{IRA}}}$, which conveys the acceptance condition of
an IRA. Let $\mathcal{R}=\langle\Sigma,Q,q_{\iota},\delta,\alpha\rangle$ be a
deterministic complete IRA of $n$ states in singleton normal form, and let
$\mathcal{M}$ be its automaton. The construction of the sample
$T_{Acc}^{\mbox{\scriptsize{IRA}}}$ proceeds in stages, simulating the
learning algorithm $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$ on the portion
of the sample constructed so far to determine what examples still need to be
added.

Initially, $\gamma_{0}=\emptyset$ and $k=0$. The acceptance condition
$\gamma_{k}$ tracks the learning algorithm’s $\beta_{k}$. The set of words
accepted by $(\mathcal{M},\gamma_{k})$ is always a subset of the set of words
accepted by $(\mathcal{M},\alpha)$.

The main loop is as follows. If $(\mathcal{M},\gamma_{k})$ is equivalent to
$(\mathcal{M},\alpha)$ then the construction of
$T_{Acc}^{\mbox{\scriptsize{IRA}}}$ is complete.

Otherwise, let $D_{k}$ be the set of $\omega$-words that satisfy $\alpha$ but
not $\gamma_{k}$. Let $C$ be the $\preceq$-largest set in
$\\{{\textsl{inf}}(w)\mid w\in D_{k}\\}$, and let
$w_{k+1}=\mathbf{Witness}(C,\mathcal{M})$, an ultimately periodic word of
length $O(n^{2})$. Then $w_{k+1}$ is added as a positive example to
$T_{Acc}^{\mbox{\scriptsize{IRA}}}$.

Let $B=Q\setminus{\textsl{inf}}(w_{k+1})$. Define $P_{k}$ to be the set of all
$(q,B)$ such that $q\in{\textsl{inf}}(w_{k+1})$ and there is no $\omega$-word
$w^{\prime}$ that satisfies $(q,B)$ but not $\alpha$. Set
$\gamma_{k+1}=\gamma_{k}\cup P_{k}$.

For each $q\in{\textsl{inf}}(w_{k+1})$ such that there is some $\omega$-word
$w^{\prime}$ that satisfies $(q,B)$ but not $\alpha$, let
$u(v)^{\omega}=\mathbf{Witness}({\textsl{inf}}(w^{\prime}),\mathcal{M})$ for
some such $w^{\prime}$ and include $(u(v)^{\omega},0)$ as a negative example
in $T_{Acc}$. The example $u(v)^{\omega}$ is of length $O(n^{2})$. Then set
$k$ to $k+1$ and continue with the main loop.

We prove a polynomial bound on the number of examples added to the sample
$T_{Acc}^{\mbox{\scriptsize{IRA}}}$, thus showing that its length is bounded
by a polynomial in the size of $\mathcal{R}$.

###### Proposition 8.3.

If the acceptance condition $\alpha$ is in singleton normal form and has $m$
pairs, then at most $m$ positive examples and at most $m|Q|$ negative examples
are added to $T_{Acc}$.

###### Proof.

We say an acceptance condition $\gamma$ _covers_ a pair $(q,B)$ iff every
$\omega$-word $w$ that satisfies $(q,B)$ also satisfies $\gamma$. We will show
that after each positive example $w_{k+1}$ is added to $T_{Acc}$, the
condition $\gamma_{k+1}$ covers at least one pair in $\alpha$ that was not
covered by $\gamma_{k}$.

Suppose not, and let $k+1$ be the least index for which $\gamma_{k+1}$ does
not cover a pair of $\alpha$ that was not covered by $\gamma_{k}$.

Because $w_{k+1}$ is an example that satisfies $\alpha$ but not $\gamma_{k}$,
there must be a pair $(q,B_{j})$ of $\alpha$ that is satisfied by $w_{k+1}$.
Note that $\gamma_{k}$ does not cover the pair $(q,B_{j})$.

Then $q\in{\textsl{inf}}(w_{k+1})$ and letting
$B=Q\setminus{\textsl{inf}}(w_{k+1})$, $B_{j}\subseteq B$. The pair $(q,B)$
will be added to $\gamma_{k}$ in constructing $\gamma_{k+1}$ because every
word that satisfies $(q,B)$ also satisfies $(q,B_{j})$.

If $\gamma_{k+1}$ does not cover $(q,B_{j})$, there must be a word
$w^{\prime}$ that satisfies $(q,B_{j})$ but not $(q,B)$. So
$q\in{\textsl{inf}}(w^{\prime})$ and
$B_{j}\cap{\textsl{inf}}(w^{\prime})=\emptyset$ but
$B\cap{\textsl{inf}}(w^{\prime})\neq\emptyset$. Let
$B^{\prime}=Q\setminus{\textsl{inf}}(w^{\prime})$, so $B_{j}\subseteq
B^{\prime}$. We have $B\cap B^{\prime}\subsetneq B$.

Because ${\textsl{inf}}(w_{k+1})$ and ${\textsl{inf}}(w^{\prime})$ are SCCs
that overlap in $q$, their union is an SCC as well. Let $w^{\prime\prime}$ be
an $\omega$-word such that ${\textsl{inf}}(w^{\prime\prime})$ is the union of
${\textsl{inf}}(w_{k+1})$ and ${\textsl{inf}}(w^{\prime})$. Then
$Q\setminus{\textsl{inf}}(w^{\prime\prime})=B\cap B^{\prime}$. Note that
$w^{\prime\prime}$ satisfies $(q,B_{j})$ because $B_{j}\subseteq B\cap
B^{\prime}$ and thus is a positive example of $\alpha$.

Because $B\cap B^{\prime}$ is a proper subset of $B$,
${\textsl{inf}}(w^{\prime\prime})$ is a proper superset of
${\textsl{inf}}(w_{k+1})$ and the positive example $w^{\prime\prime}$ would
have been considered before $w_{k+1}$ in the construction of $T_{Acc}$. (We
can imagine all the positive examples of $\alpha$ being considered in order to
find a maximum positive counterexample at each stage.) At that time, it was
either passed over because (1) the current $\gamma_{r}$ already covered it, or
(2) it contributed a new pair to the current $\gamma_{r}$ to yield
$\gamma_{r+1}$.

In case (1), there is some pair $(q^{\prime\prime},B^{\prime\prime})$ in
$\gamma_{r}$ that is satisfied by $w^{\prime\prime}$. Then
$q^{\prime\prime}\in{\textsl{inf}}(w^{\prime\prime})$ and
$B^{\prime\prime}\cap{\textsl{inf}}(w^{\prime\prime})=\emptyset$. Recall
${\textsl{inf}}(w^{\prime\prime})$ is the union of ${\textsl{inf}}(w_{k+1})$
and ${\textsl{inf}}(w^{\prime})$. Thus,
$B^{\prime\prime}\cap{\textsl{inf}}(w_{k+1})=\emptyset$ and
$B^{\prime\prime}\cap{\textsl{inf}}(w^{\prime})=\emptyset$. Note that
$q^{\prime\prime}\in{\textsl{inf}}(w_{k+1})$ or
$q^{\prime\prime}\in{\textsl{inf}}(w^{\prime})$. If
$q^{\prime\prime}\in{\textsl{inf}}(w_{k+1})$, $w_{k+1}$ satisfies the pair
$(q^{\prime\prime},B^{\prime\prime})$ in $\gamma_{j}$, a contradiction,
because $w_{k+1}$ is not accepted by $\gamma_{k}$ and $r\leq k$. And if
$q^{\prime\prime}\in{\textsl{inf}}(w^{\prime})$ then $w^{\prime}$ satisfies
the pair $(q^{\prime\prime},B^{\prime\prime})$ in $\gamma_{r}$, a
contradiction, because $w^{\prime}$ is not accepted by $\gamma_{k+1}$ and
$r\leq k$.

In case (2), the positive example $w^{\prime\prime}$ contributes at least one
term $(q^{\prime\prime},B^{\prime\prime})$ to $\gamma_{r+1}$. In this case
$B^{\prime\prime}=B\cap B^{\prime}$ and
$q^{\prime\prime}\in{\textsl{inf}}(w^{\prime\prime})$. Thus,
$q^{\prime\prime}\in{\textsl{inf}}(w_{k+1})$ or
$q^{\prime\prime}\in{\textsl{inf}}(w^{\prime})$, so $w_{k+1}$ or $w^{\prime}$
satisfies the term $(q^{\prime\prime},B^{\prime\prime})$ of $\gamma_{r+1}$, a
contradiction because $r+1\leq k$ and neither $w_{k+1}$ nor $w^{\prime}$ is
covered by $\gamma_{k}$.

Thus, each positive example added to $T_{Acc}$ covers a new pair of $\alpha$,
and at most $m$ positive examples can be added. Each positive example added
requires at most $|Q|$ negative examples to avoid adding incorrect pairs, so
at most $m|Q|$ negative examples are added. ∎

###  8.5. Correctness of $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$

We prove the correctness of the learning algorithm
$\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$ and show that the classes
$\mathbb{IR}$ and $\mathbb{IS}$ are identifiable in the limit using polynomial
time and data.

###### Theorem 8.4.

Algorithm $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$ runs in time polynomial
in the sizes of the inputs $\mathcal{M}$ and $T$. Let $\mathcal{R}$ be an IRA.
If the input automaton $\mathcal{M}$ is isomorphic to the automaton of
$\mathcal{R}$, and the sample $T$ is consistent with $\mathcal{R}$ and
subsumes $T_{Acc}^{\mbox{\scriptsize{IRA}}}$, then algorithm
$\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$ returns an IRA
$(\mathcal{M},\beta)$ equivalent to $\mathcal{R}$.

###### Proof.

By Prop. 4.3, $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$ can construct the
sequence $z_{1},z_{2},\ldots,z_{\ell}$ and the successive acceptance
conditions $\beta_{k}$ in time polynomial in the size of $\mathcal{M}$ and the
length of $T$.

Assume $\mathcal{R}$ is an IRA, that $\mathcal{M}$ is isomorphic to the
automaton of $\mathcal{R}$, and that the sample $T$ is consistent with
$\mathcal{R}$ and subsumes $T_{Acc}^{\mbox{\scriptsize{IRA}}}$. For ease of
notation, we assume that the isomorphism is the identity.

We show by induction that for each $k$, the acceptance condition $\beta_{k}$
in the learning algorithm $\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$ is the
same as the acceptance condition $\gamma_{k}$ in the construction of
$T_{Acc}^{\mbox{\scriptsize{IRA}}}$. This is true for $k=0$ because
$\beta_{0}=\gamma_{0}=\emptyset$.

Assume that $\beta_{k}=\gamma_{k}$ for some $k\geq 0$. If
$(\mathcal{M},\gamma_{k})$ is equivalent to
$\mathcal{R}=(\mathcal{M},\alpha)$, then also $(\mathcal{M},\beta_{k})$ is
equivalent to $\mathcal{R}$, and none of the remaining positive examples cause
any additions to $\beta_{k}$. Thus this is the final value of $k$, so
$\beta=\beta_{k}$ and $(\mathcal{M},\beta)$ is equivalent to $\mathcal{R}$.

If $(\mathcal{M},\gamma_{k})$ accepts a proper subset of the language accepted
by $(\mathcal{M},\alpha)$, then in the construction of sample
$T_{Acc}^{\mbox{\scriptsize{IRA}}}$, $D_{k}$ is equal to the $\omega$-words
accepted by $(\mathcal{M},\alpha)$ but not by $(\mathcal{M},\gamma_{k})$. This
causes the positive example $(w_{k+1},1)$ to be added to
$T_{Acc}^{\mbox{\scriptsize{IRA}}}$, where
$\textit{inf}_{\mathcal{M}}(w_{k+1})$ is $\preceq$-largest in the set
$\\{\textit{inf}_{\mathcal{M}}(w)\mid w\in D_{k}\\}$.

In the learning algorithm, because $(\mathcal{M},\beta_{k})$ does not accept
$w_{k+1}$, Prop. 8.2 implies that there must be an example $z_{i}$ that causes
the update to $\beta_{k}$, and all of the examples $z_{1},\ldots,z_{i-1}$ are
accepted by $(\mathcal{M},\beta_{k})$. Because for every positive example
$(w,1)$ in $T$ there exists $j$ such that
$\textit{inf}_{\mathcal{M}}(w)=\textit{inf}_{\mathcal{M}}(z_{j})$, there must
be some $r$ such that
$\textit{inf}_{\mathcal{M}}(w_{k+1})=\textit{inf}_{\mathcal{M}}(z_{r})$.
Moreover, $i\leq r$.

If $i<r$, then $\textit{inf}_{\mathcal{M}}(w_{i})$ is strictly
$\preceq$-larger than $\textit{inf}_{\mathcal{M}}(w_{r})$, which contradicts
the choice of $w_{k+1}$ by the sample construction procedure, because $z_{i}$
is accepted by $(\mathcal{M},\alpha)$ but not $(\mathcal{M},\gamma_{k})$. Thus
$i=r$ and the example $z_{i}=w_{k+1}$ is the element that causes the update to
$\beta_{k}$. The negative examples included in
$T_{Acc}^{\mbox{\scriptsize{IRA}}}$ for the positive example $w_{k+1}$ ensure
that the update to $\beta_{k}$ is the same as the update to $\gamma_{k}$, and
$\beta_{k+1}=\gamma_{k+1}$.

Because $\beta_{k}$ and $\gamma_{k}$ are equal for all $k$, for the final
value of $k$, $\beta=\beta_{k}=\gamma_{k}$, and therefore
$(\mathcal{M},\beta)$ is equivalent to $\mathcal{R}$. Because the IRA
$(\mathcal{M},\beta)$ is consistent with $T$, it is the acceptor returned by
$\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$. ∎

###### Theorem 8.5.

The classes $\mathbb{IR}$ and $\mathbb{IS}$ are identifiable in the limit
using polynomial time and data.

###### Proof.

By Prop. 4.1 it suffices to prove this for $\mathbb{IR}$. Let $\mathcal{R}$ be
an IRA in singleton normal form accepting the language $L$. The characteristic
sample $T_{L}=T_{Aut}\cup T_{Acc}^{\mbox{\scriptsize{IRA}}}$ is of size
polynomial in the size of $\mathcal{R}$.

The combined learning algorithm $\mathbf{L}^{\mbox{\scriptsize{IRA}}}$ with a
sample $T$ as input first runs $\mathbf{L}_{Aut}$ on $T$ to get a
deterministic complete automaton $\mathcal{M}$ and then runs
$\mathbf{L}_{Acc}^{\mbox{\scriptsize{IRA}}}$ on inputs $\mathcal{M}$ and $T$
and returns the resulting acceptor. $\mathbf{L}^{\mbox{\scriptsize{IRA}}}$
runs in time polynomial in the length of $T$ and returns a DRA consistent with
$T$.

Now assume that the sample $T$ is consistent with $\mathcal{R}$ and subsumes
$T_{L}$. Then by Theorem 5.2, the automaton $\mathcal{M}$ is isomorphic to the
automaton of $\mathcal{R}$. By Theorem 8.4, the acceptor returned by
$\mathbf{T}^{\mbox{\scriptsize{IRA}}}$ is an IRA $(\mathcal{M},\beta)$ is
equivalent to $\mathcal{R}$, and this is the acceptor also returned by
$\mathbf{L}^{\mbox{\scriptsize{IRA}}}$. ∎

##  9\. Characteristic samples in polynomial time

The definition of identification in the limit using polynomial time and data
requires that a characteristic sample exist and be of polynomial size, but
says nothing about the cost of computing it. An additional desirable property
is that a characteristic sample be computable in polynomial time given an
acceptor $\mathcal{A}$ as input. We now address the question of polynomial
time algorithms to compute the characteristic samples we have defined.

###  9.1. Computing $T_{Aut}$

For $T_{Aut}$, we need to be able to decide for two states $q_{1}$ and $q_{2}$
of an acceptor $\mathcal{A}$ whether there exists an $\omega$-word that
distinguishes them, and if so, to return one such word. We are thus led to
consider the problems of inclusion and equivalence.

###  9.2. The problems of inclusion and equivalence

The _inclusion problem_ is the following. Given as input two
$\omega$-acceptors $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ over the same
alphabet, determine whether the language accepted by $\mathcal{A}_{1}$ is a
subset of the language accepted by $\mathcal{A}_{2}$, that is, whether
${\llbracket}\mathcal{A}_{1}{\rrbracket}\subseteq{\llbracket}\mathcal{A}_{2}{\rrbracket}$.
If so, the answer should be “yes”; if not, the answer should be “no” and a
_witness_ , that is, an ultimately periodic $\omega$-word $u(v)^{\omega}$
accepted by $\mathcal{A}_{1}$ but rejected by $\mathcal{A}_{2}$.

The _equivalence problem_ is similar: the input is two $\omega$-acceptors
$\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ over the same alphabet, and the
problem is to determine whether they are equivalent, that is, whether
${\llbracket}\mathcal{A}_{1}{\rrbracket}={\llbracket}\mathcal{A}_{2}{\rrbracket}$.
If so, the answer should be “yes”; if not, the answer should be “no” and a
witness, that is, an ultimately periodic $\omega$-word $u(v)^{\omega}$ that is
accepted by exactly one of $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$.

If we have a procedure to solve the inclusion problem, at most two calls to it
will solve the equivalence problem. We describe polynomial time algorithms to
solve the inclusion problem for DBAs, DCAs, and DPAs in Section 10 and 11, for
DRAs and DSAs in Section 12, and for DMAs in Section 13. Referring to those
sections, we obtain polynomial time algorithms to solve the equivalence
problem for DBAs, DCAs, and DPAs from Theorem 10.1 and Theorem 11.2, for DRAs
and DSAs from Theorem 12.2, and for DMAs from Theorem 13.6. Thus, we have the
following.

###### Theorem 9.1.

Given an acceptor $\mathcal{A}$ of type IBA, ICA, IPA, IRA, ISA, or IMA, the
sample $T_{Aut}$ for the automaton portion of $\mathcal{A}$ may be computed in
polynomial time.

###### Proof.

Given an acceptor $\mathcal{A}$ and two states $q_{1}$ and $q_{2}$, to
determine whether there is an $\omega$-word that distinguishes them, we call
the relevant polynomial time equivalence algorithm on the acceptors
$\mathcal{A}^{q_{1}}$ and $\mathcal{A}^{q_{2}}$, which returns a
distinguishing word $u(v)^{\omega}$ if they are not equivalent. ∎

###  9.3. Computing $T_{Acc}$

For $T_{Acc}$, the requirements depend on the type of acceptor.

###### Proposition 9.2.

Given an IBA $\mathcal{B}$, the sample $T_{Acc}^{\mbox{\scriptsize{IBA}}}$ can
be computed in time polynomial in the size of $\mathcal{B}$.

###### Proof.

Given an IBA $\mathcal{B}=\langle\Sigma,Q,q_{\iota},\delta,F\rangle$ with
automaton $\mathcal{M}$, the sample $T_{Acc}^{\mbox{\scriptsize{IBA}}}$
described in Section 6.2 is computed as follows. For each SCC
$C\in\textit{maxSCCs}(Q\setminus F)$, let
$u(v)^{\omega}=\mathbf{Witness}(C,\mathcal{M})$ and include the negative
example $(u(v)^{\omega},0)$ in $T_{Acc}^{\mbox{\scriptsize{IBA}}}$.

To see that these examples are sufficient, suppose that $q\in Q$ and
$w\in\Sigma^{\omega}$ are such that $\mathcal{B}$ rejects $w$ and
$q\in{\textsl{inf}}(w)$. Then $D={\textsl{inf}}(w)$ is an SCC of $\mathcal{B}$
contained in $Q\setminus F$, so it is contained in some
$C\in\textit{maxSCCs}(Q\setminus F)$, and there is a negative example
$(u(v)^{\omega},0)$ in $T_{Acc}^{\mbox{\scriptsize{IBA}}}$ such that
${\textsl{inf}}(u(v)^{\omega})=C$. Because $D\subseteq C$, we have $q\in C$. ∎

###### Proposition 9.3.

Given an IPA $\mathcal{P}$, the sample $T_{Acc}^{\mbox{\scriptsize{IPA}}}$ can
be computed in time polynomial in the size of $\mathcal{P}$.

###### Proof.

Given an IPA $\mathcal{P}$ with automaton $\mathcal{M}$, the computation of
$T_{Acc}^{\mbox{\scriptsize{IPA}}}$ proceeds as described in Section 7.2. That
is, the canonical forest $\mathcal{F}^{*}(\mathcal{P})$ is computed in
polynomial time, and for each node $C$ in the forest,
$u(v)^{\omega}=\mathbf{Witness}(C,\mathcal{M})$ is computed and
$(u(v)^{\omega},l)$ is added to $T_{Acc}^{\mbox{\scriptsize{IPA}}}$, where $l$
is the label of node $C$ in the canonical forest. ∎

###### Proposition 9.4.

Given an IRA $\mathcal{R}$, the sample $T_{Acc}^{\mbox{\scriptsize{IRA}}}$ can
be computed in time polynomial in the size of $\mathcal{R}$.

###### Proof.

Given an IRA $\mathcal{R}=(\mathcal{M},\alpha)$, the computation of $T_{Acc}$
proceeds as described in Section 8.4. At each stage of the computation, it is
necessary to find an $\omega$-word $u(v)^{\omega}$ with the $\preceq$-largest
$\textit{inf}_{\mathcal{M}}(u(v)^{\omega}$) that is accepted by
$(\mathcal{M},\alpha)$ and rejected by $(\mathcal{M},\gamma_{k})$. Theorem
12.2 gives a polynomial time algorithm that not only tests the inclusion of
two DRAs, but returns a witness $u(v)^{\omega}$ with the $\preceq$-largest
$\textit{inf}_{\mathcal{M}}(u(v)^{\omega})$ in the case of non-inclusion,
because $\mathcal{M}$ is isomorphic to $\mathcal{M}\times\mathcal{M}$. ∎

###### Proposition 9.5.

Given an IMA $\mathcal{A}$, the sample $T_{Acc}^{\mbox{\scriptsize{IMA}}}$ can
be computed in time polynomial in the size of $\mathcal{A}$.

###### Proof.

Given an IMA $\mathcal{A}=(\mathcal{M},{\mathcal{F}})$, the sample
$T_{Acc}^{\mbox{\scriptsize{IMA}}}$ described in Section 6.1 is computed as
follows. For each $F\in{\mathcal{F}}$ determine whether $F$ is a reachable SCC
of $\mathcal{M}$, and if so, compute
$u(v)^{\omega}=\mathbf{Witness}(F,\mathcal{M})$ and add $(u(v)^{\omega},1)$ to
the sample $T_{Acc}^{\mbox{\scriptsize{IMA}}}$. ∎

###### Theorem 9.6.

Let $\mathcal{A}$ be an IBA, IPA, IRA, or IMA accepting the $\omega$-language
$L$. Then the characteristic sample $T_{L}$ for $\mathcal{A}$ may be computed
in polynomial time in the size of $\mathcal{A}$.

###### Proof.

By Theorem 9.1, the sample $T_{Aut}$ can be computed in polynomial time in the
size of $\mathcal{A}$, and by Prop. 9.2, 9.3, 9.4, or 9.5 the sample
$T_{Acc}^{\mbox{\scriptsize{IBA}}}$, $T_{Acc}^{\mbox{\scriptsize{IPA}}}$,
$T_{Acc}^{\mbox{\scriptsize{IRA}}}$, or $T_{Acc}^{\mbox{\scriptsize{IMA}}}$
can also be computed in polynomial time in the size of $\mathcal{A}$. ∎

##  10\. Inclusion algorithms

We show that there are polynomial time algorithms for the inclusion problem
for DBAs, DCAs, DPAs, DRAs, DSAs, and DMAs. Recall that two calls to an
inclusion algorithm suffice to solve the equivalence problem. By Claim 2.5,
the inclusion and equivalence problems for DCAs are efficiently reducible to
those for DBAs, and vice versa. Also, by Claim 2.2, the inclusion and
equivalence problems for DBAs are efficiently reducible to those for DPAs.
Thus it suffices to consider the inclusion problem for DPAs, DRAs, and DMAs.

##### Remark.

In the case of DFAs, a polynomial algorithm for the inclusion problem can be
obtained using polynomial algorithms for complementation, intersection and
emptiness (since for any two languages $L_{1}\subseteq L_{2}$ if and only if
$L_{1}\cap\overline{L_{2}}=\emptyset$). However, a similar approach does not
work in the case of DPAs; although complementation and emptiness for DPAs can
be computed in polynomial time, intersection cannot (Boker, 2018, Theorem 9).

For the inclusion problem for DBAs, DCAs, and DPAs, Schewe (Schewe, 2010)
gives the following result.

###### Theorem 10.1 ((Schewe, 2010)).

The inclusion problems for DBAs, DCAs, and DPAs are in NL.

Because NL (nondeterministic logarithmic space) is contained in polynomial
time, this implies the existence of polynomial time inclusion and equivalence
algorithms for DBAs, DCAs, and DPAs. Because Schewe does not give a proof or
reference for Theorem 10.1, and does not address the problem of returning a
witness, for completeness we include a proof sketch.

###### Proof sketch.

For $i=1,2$, let
$\mathcal{P}_{i}=\langle\Sigma,Q_{i},(q_{\iota})_{i},\delta_{i},\kappa_{i}\rangle$
be a DPA. It suffices to guess two states $q_{1}\in Q_{1}$ and $q_{2}\in
Q_{2}$, and two words $u\in\Sigma^{*}$ and $v\in\Sigma^{+}$, and to check that
for $i=1,2$, $\delta_{i}((q_{\iota})_{i},u)=q_{i}$ and
$\delta_{i}(q_{i},v)=q_{i}$, and also, that the smallest value of
$\kappa_{1}(q)$ in the loop in $\mathcal{P}_{1}$ from $q_{1}$ to $q_{1}$ on
input $v$ is odd, while the smallest value of $\kappa_{2}(q)$ in the loop in
$\mathcal{P}_{2}$ from $q_{2}$ to $q_{2}$ on input $v$ is even. If these
checks succeed, then ${\llbracket}\mathcal{P}_{1}{\rrbracket}$ is not a subset
of ${\llbracket}\mathcal{P}_{2}{\rrbracket}$, and the ultimately periodic word
$u(v)^{\omega}$ is a witness.

Logarithmic space is enough to record the two guessed states $q_{1}$ and
$q_{2}$ as well as the current minimum values of $\kappa_{1}$ and $\kappa_{2}$
as the loops on $v$ are traversed in the two automata. The words $u$ and $v$
need only be guessed symbol-by-symbol, using a pointer in each automaton to
keep track of its current state. ∎

This approach does not seem to work in the case of testing DRA or DMA
inclusion, because the acceptance conditions would seem to require keeping
track of more information than would fit in logarithmic space. To supplement
the proof sketch for Schewe’s theorem, in the next section we give an explicit
polynomial time algorithm for testing DPA inclusion. In the following
sections, we give polynomial time algorithms for testing inclusion for DRAs
and DMAs, which are novel results.

##  11\. Inclusion and equivalence for DPAs, DBAs, DCAs

In this section we describe an explicit polynomial time algorithm for the
inclusion problem for two DPAs, which yields algorithms for DBAs and DCAs. If
$\mathcal{P}=\langle\Sigma,Q,q_{\iota},\delta,\kappa\rangle$ is a complete DPA
and $w\in\Sigma^{\omega}$, we let $\mathcal{P}(w)$ denote the minimum color
visited by $\mathcal{P}$ infinitely often on input $w$, that is,
$\mathcal{P}(w)=\kappa({\textsl{inf}}(w))$.

###  11.1. Searching for $w$ with given minimum colors in two acceptors

We first describe an algorithm that searches for an $\omega$-word that yields
specified minimum colors in two different DPAs over the same alphabet.

For $i=1,2$, let
${\mathcal{P}}_{i}=\langle\Sigma,Q_{i},(q_{\iota})_{i},\delta_{i},\kappa_{i}\rangle$
be a DPA, and let $\mathcal{M}_{i}$ be the automaton of $\mathcal{P}_{i}$.
Given inputs of $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ and two nonnegative
integers $k_{1}$ and $k_{2}$, the $\mathbf{Colors}$ algorithm constructs the
product automaton ${\mathcal{M}}={{\mathcal{M}}}_{1}\times{{\mathcal{M}}}_{2}$
and the set $Q^{\prime}=\\{(q_{1},q_{2})\in Q_{1}\times
Q_{2}\mid\kappa_{1}(q_{1})\geq k_{1}\wedge\kappa_{2}(q_{2})\geq k_{2}\\}$.

The algorithm then computes $S=\textit{maxSCCs}(Q^{\prime})$ for the automaton
$\mathcal{M}$, and loops through the SCCs $C\in S$ checking whether $C$ is
reachable in $\mathcal{M}$, $\min(\kappa_{1}(\pi_{1}(C)))=k_{1}$, and
$\min(\kappa_{2}(\pi_{2}(C)))=k_{2}$. If so, it returns the ultimately
periodic word $u(v)^{\omega}=\mathbf{Witness}(C,\mathcal{M})$. If none of the
elements $C\in S$ satisfies this condition, then the answer “no” is returned.

###### Theorem 11.1.

The algorithm $\mathbf{Colors}$ takes as input two DPAs $\mathcal{P}_{1}$ and
$\mathcal{P}_{2}$ over the same alphabet and two nonnegative integers $k_{1}$
and $k_{2}$, runs in polynomial time, and determines whether there exists an
$\omega$-word $w$ such that $\mathcal{P}_{1}(w)=k_{1}$ and
$\mathcal{P}_{2}(w)=k_{2}$. If not, it returns the answer “no”. If so, it
returns an ultimately periodic $\omega$-word $u(v)^{\omega}$ such that
$\mathcal{P}_{1}(u(v)^{\omega})=k_{1}$ and
$\mathcal{P}_{2}(u(v)^{\omega})=k_{2}$.

###### Proof.

The polynomial running time of the algorithm follows from Props. 4.4 and 4.7.
To see the correctness of the algorithm, suppose first that it returns an
ultimately periodic word $u(v)^{\omega}$. This occurs only if it finds an SCC
$C$ of $\mathcal{M}$ such that $C$ is reachable in $\mathcal{M}$,
$\kappa_{1}(\pi_{1}(C))=k_{1}$, and $\kappa_{2}(\pi_{2}(C))=k_{2}$. Then for
$i=1,2$, $\pi_{i}(C)$ is the set of states visited infinitely often by
$\mathcal{M}_{i}$ on the input $u(v)^{\omega}$, which has minimum color
$k_{i}$.

To see that the algorithm does not incorrectly answer “no”, suppose $w$ is an
$\omega$-word such that for $i=1,2$, $\mathcal{P}_{i}(w)=k_{i}$. Let
$D_{i}=\textit{inf}_{\mathcal{M}_{i}}(w)$, an SCC of $\mathcal{M}_{i}$. No
state in $D_{i}$ has a color less than $k_{i}$, so if
$D=\textit{inf}_{\mathcal{M}}(w)$, then $D\subseteq Q^{\prime}$. Also, $D$ is
a reachable SCC in $\mathcal{M}$.

Then $D$ is contained in some element $C$ of $\textit{maxSCCs}(Q^{\prime})$.
Because there are no states $(q_{1},q_{2})$ in $C$ with
$\kappa_{1}(q_{1})<k_{1}$ or $\kappa_{2}(q_{2})<k_{2}$, we must have
$\kappa_{i}(\pi_{i}(C))=k_{i}$ for $i=1,2$. Also, $C$ is reachable in
$\mathcal{M}$ because $D$ is. Thus, the algorithm will find at least one such
$C$ and return $u(v)^{\omega}$ such that
$\textit{inf}_{\mathcal{M}}(u(v)^{\omega})=C$. ∎

###  11.2. An inclusion algorithm for DPAs

The inclusion problem for DPAs $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ over
the same alphabet can be solved by looping over all odd $k_{1}$ in the range
of $\kappa_{1}$ and all even $k_{2}$ in the range of $\kappa_{2}$, calling the
$\mathbf{Colors}$ algorithm with inputs $\mathcal{P}_{1}$, $\mathcal{P}_{2}$,
$k_{1}$, and $k_{2}$. If the $\mathbf{Colors}$ algorithm returns any witness
$u(v)^{\omega}$, then
$u(v)^{\omega}\in{\llbracket}\mathcal{P}_{1}{\rrbracket}\setminus{\llbracket}\mathcal{P}_{2}{\rrbracket}$,
and $u(v)^{\omega}$ is returned as a witness of non-inclusion. Otherwise, by
Theorem 11.1, there is no $\omega$-word $w$ accepted by $\mathcal{P}_{1}$ and
not accepted by $\mathcal{P}_{2}$, and the answer “yes” is returned for the
inclusion problem. Note that for $i=1,2$, the range of $\kappa_{i}$ has at
most $|Q_{i}|$ distinct elements. Thus we have the following.

###### Theorem 11.2.

There are polynomial time algorithms for the inclusion and equivalence
problems for two DPAs over the same alphabet.

From Claims 2.2 and 2.5, we have the following.

###### Theorem 11.3.

There are polynomial time algorithms for the inclusion and equivalence
problems for two DBAs (or DCAs) over the same alphabet.

##  12\. An inclusion algorithm for DRAs

In this section we describe a polynomial time algorithm to solve the inclusion
problem for two DRAs. The algorithm returns a $\preceq$-largest witness in the
case of non-inclusion.

Algorithm 1 $\mathbf{SubInc}^{DRA}$

Two DRAs $\mathcal{R}_{1}=(\mathcal{M}_{1},\alpha_{1})$ and
$\mathcal{R}_{2}=(\mathcal{M}_{2},\alpha_{2})$ in singleton normal form, where
$\alpha_{1}=\\{(q^{\prime},B^{\prime})\\}$ and
$\alpha_{2}=\\{(q_{1}^{\prime\prime},B_{1}^{\prime\prime}),\ldots,(q_{k}^{\prime\prime},B_{k}^{\prime\prime})\\}$,
and a set $S$ of states of $\mathcal{M}=\mathcal{M}_{1}\times\mathcal{M}_{2}$

$u(v)^{\omega}\in{\llbracket}\mathcal{R}_{1}{\rrbracket}\setminus{\llbracket}\mathcal{R}_{2}{\rrbracket}$
with $\textit{inf}_{\mathcal{M}}(u(v)^{\omega})\subseteq S$ if such exists,
else “none”.

$\mathcal{M}=\mathcal{M}_{1}\times\mathcal{M}_{2}$

$W\leftarrow\emptyset$

$S^{\prime}\leftarrow S\setminus\\{(q_{1},q_{2})\in S\mid q_{1}\in
B^{\prime}\\}$

$\mathcal{C}\leftarrow\textit{maxSCCs}(S^{\prime})$

for each reachable $C\in\mathcal{C}$ such that $q^{\prime}\in\pi_{1}(C)$ do

if for no $j\in[1..k]$ is $q_{j}^{\prime\prime}\in\pi_{2}(C)$ and
$B_{j}^{\prime\prime}\cap\pi_{2}(C)=\emptyset$ then

$W\leftarrow W\cup\\{\mathbf{Witness}(C,\mathcal{M})\\}$ $\triangleright$ A
new candidate witness

else

$J=\\{q_{j}^{\prime\prime}\mid
j\in[1..k],B_{j}^{\prime\prime}\cap\pi_{2}(C)=\emptyset\\}$

$S^{\prime\prime}\leftarrow C\setminus\\{(q_{1},q_{2})\in C\mid q_{2}\in J\\}$

Call $\mathbf{SubInc}^{DRA}$ recursively with $\mathcal{R}_{1}$,
$\mathcal{R}_{2}$, and $S^{\prime\prime}$

if the returned value is $u(v)^{\omega}$ then

$W\leftarrow W\cup\\{u(v)^{\omega}\\}$

if $W$ is $\emptyset$ then

return “none”

else

Let $u(v)^{\omega}\in W$ have the $\preceq$-largest value of
$\textit{inf}_{\mathcal{M}}(u(v)^{\omega})$

return $u(v)^{\omega}$

The algorithm $\mathbf{SubInc}^{DRA}$ takes as input two DRAs
$\mathcal{R}_{1}=(\mathcal{M}_{1},\alpha_{1})$ and
$\mathcal{R}_{2}=(\mathcal{M}_{2},\alpha_{2})$ in singleton normal form, where
$\alpha_{1}$ consists of a single pair $(q^{\prime},B^{\prime})$. It also
takes as input a subset $S$ of the state set of the product automaton
$\mathcal{M}=\mathcal{M}_{1}\times\mathcal{M}_{2}$. The problem it solves is
to determine whether there exists an $\omega$-word $u(v)^{\omega}$ with
$\textit{inf}_{\mathcal{M}}(u(v)^{\omega})\subseteq S$ such that
$u(v)^{\omega}\in{\llbracket}\mathcal{R}_{1}{\rrbracket}\setminus{\llbracket}\mathcal{R}_{2}{\rrbracket}$.
If there is such a word, the algorithm returns one with the $\preceq$-largest
value of $\textit{inf}_{\mathcal{M}}(u(v)^{\omega})$, and otherwise, it
returns “none”.

###### Proposition 12.1.

For $i=1,2$ let $\mathcal{R}_{i}=(\mathcal{M}_{i},\alpha_{i})$ be a DRA in
singleton normal form. Assume $\alpha_{1}=\\{(q^{\prime},B^{\prime})\\}$ and
$\alpha_{2}=\\{(q_{1}^{\prime\prime},B_{1}^{\prime\prime}),\ldots,(q_{k}^{\prime\prime},B_{k}^{\prime\prime})\\}$.
Let $\mathcal{M}=\mathcal{M}_{1}\times\mathcal{M}_{2}$, and let $S$ be a
subset of the states of $\mathcal{M}$. Then with inputs $\mathcal{R}_{1}$,
$\mathcal{R}_{2}$, and $S$, the algorithm $\mathbf{SubInc}^{DRA}$ runs in
polynomial time and returns
$u(v)^{\omega}\in{\llbracket}\mathcal{R}_{1}{\rrbracket}\setminus{\llbracket}\mathcal{R}_{2}{\rrbracket}$
with the $\preceq$-largest value of
$\textit{inf}_{\mathcal{M}}(u(v)^{\omega})$ contained in $S$, if such exists,
else it returns “none”.

###### Proof.

When the element $u(v)^{\omega}=\mathbf{Witness}(\mathcal{M},C)$ is added to
$W$, we have that $C$ is a reachable SCC of $\mathcal{M}$ contained in $S$,
$q^{\prime}\in\pi_{1}(C)$, and $B^{\prime}\cap\pi_{1}(C)=\emptyset$ (because
$S^{\prime}$ contains no elements $(q_{1},q_{2})$ with $q_{1}\in B^{\prime}$),
so $(\mathcal{M}_{1},\\{(q^{\prime},B^{\prime})\\})$ accepts $u(v)^{\omega}$.
Also, we have that for no $j\in[1..k]$ do we have
$q_{j}^{\prime\prime}\in\pi_{2}(C)$ and
$B_{j}^{\prime\prime}\cap\pi_{2}(C)=\emptyset$, so $\mathcal{R}_{2}$ rejects
$u(v)^{\omega}$. Thus, any returned $u(v)^{\omega}$ is a witness to the non-
inclusion of
${\llbracket}(\mathcal{M}_{1},\\{(q^{\prime},B^{\prime})\\}){\rrbracket}$ in
${\llbracket}\mathcal{R}_{2}{\rrbracket}$ with
$\textit{inf}_{\mathcal{M}}(u(v)^{\omega})\subseteq S$.

We now show by induction on the recursive calls that if $w$ is any
$\omega$-word such that $\textit{inf}_{\mathcal{M}}(w)\subseteq S$,
$(\mathcal{M}_{1},\\{(q^{\prime},B^{\prime})\\})$ accepts $w$, and
$\mathcal{R}_{2}$ rejects $w$, then $\mathbf{SubInc}^{DRA}$ returns a witness
$u(v)^{\omega}$ such that $\textit{inf}_{\mathcal{M}}(u(v)^{\omega})$ is at
least as large as $\textit{inf}_{\mathcal{M}}(w)$ in the $\preceq$-ordering.
Let $D=\textit{inf}_{\mathcal{M}}(w)$. Then $D$ is a reachable SCC of
$\mathcal{M}$ such that $q^{\prime}\in\pi_{1}(D)$,
$B^{\prime}\cap\pi_{1}(D)=\emptyset$, and for no $j\in[1..k]$ do we have
$q_{j}^{\prime\prime}\in\pi_{2}(D)$ and
$B_{j}^{\prime\prime}\cap\pi_{2}(D)=\emptyset$. Then $D\subseteq S^{\prime}$
because $B^{\prime}\cap\pi_{1}(D)=\emptyset$. Thus, $D$ must be a subset of
exactly one of the elements $C$ of $\textit{maxSCCs}(S^{\prime})$. Then $C$ is
reachable, $q^{\prime}\in\pi_{1}(C)$, and $B^{\prime}\cap\pi_{1}(C)=\emptyset$
(because $C$ is a subset of $S^{\prime}$).

If $C$ is such that for no $j\in[1..k]$ do we have
$q_{j}^{\prime\prime}\in\pi_{2}(C)$ and
$B_{j}^{\prime\prime}\cap\pi_{2}(C)=\emptyset$, then a witness
$u(v)^{\omega}=\mathbf{Witness}(C,\mathcal{M})$ is added to $W$, and we have
that $C=\textit{inf}_{\mathcal{M}}(u(v)^{\omega})$ is at least as large in the