*[inlineenum]mode=unboxed,label=(0)

# Learning Broadcast Protocols

Dana Fisman1 Noa Izsak1 Swen Jacobs2

###### Abstract

The problem of learning a computational model from examples has been receiving
growing attention. For the particularly challenging problem of learning models
of distributed systems, existing results are restricted to models with a
_fixed_ number of interacting processes. In this work we look for the first
time (to the best of our knowledge) at the problem of learning a distributed
system with an arbitrary number of processes, assuming only that there
_exists_ a cutoff, i.e., a number of processes that is sufficient to produce
all observable behaviors. Specifically, we consider _fine broadcast protocols_
, these are broadcast protocols (BPs) with a finite cutoff and no hidden
states. We provide a learning algorithm that can infer a correct BP from a
sample that is consistent with a fine BP, and a minimal equivalent BP if the
sample is sufficiently complete. On the negative side we show that (a)
characteristic sets of exponential size are unavoidable, (b) the consistency
problem for fine BPs is NP hard, and (c) that fine BPs are not polynomially
predictable.

##  1 Introduction

Learning computational models has a long history starting with the seminal
works of Gold (1967; 1978) and Angluin (1987). Questions regarding learning
computational models have raised a lot of interest both in the artificial
intelligence community and the verification community. (Peled et al. (2002),
Vaandrager (2017)). Many results regarding the learnability of various
computational models used in verification have already been obtained (Beimel
et al. 2000), (Bollig et al. 2013), (Decker et al. 2014), Angluin et al.
(2015), Balle et al. (2015), Drews et al. (2017), Roy et al. (2020),
Vaandrager et al. (2021), Saadon et al. (2022), Nitay et al. (2023), Frenkel
et al. (2023).

Particularly challenging is learning of concurrent computational models.
Compared to most sequential models, they offer another level of succinctness,
and they usually have no unique minimal model. Both of these aspects can make
learning significantly more difficult. Various results regarding learning
concurrent models have already been obtained (Bollig et al. 2010),(Aarts et
al. 2015), Esparza et al. (2011), Muscholl et al. (2022). However, these
results are limited to models with a fixed number of processes, and therefore
cannot reliably learn models for (distributed) protocols that are expected to
run correctly for _any_ number of processes.

_Broadcast protocols_ (BPs) are a powerful concurrent computational model,
allowing the synchronous communication of the sender of an action with an
arbitrary number of receivers (Emerson and Namjoshi 1998). In its basic form,
this model assumes that communication and processes are reliable, i.e., it
does not consider communication failures or faulty processes. BPs have mainly
been studied in the context of parameterized verification, i.e., proving
functional correctness according to a formal specification, for all systems
where an arbitrary number of processes execute a given protocol.

The challenge in reasoning about parameterized systems such as BPs is that a
parameterized system concisely represents an infinite family of systems: for
each natural number $n$ it includes the system where $n$ indistinguishable
processes interact. The system is correct only if it satisfies the
specification for any number $n$ of processes interacting. In the context of
verification, a variety of approaches has been investigated to overcome this
challenge.

Some of these approaches are based on the notion of _cutoff_ , i.e., a number
$c$ of processes such that a given property holds for any instance of the
system with $n\\!\geq\\!c$ processes if and only if it holds for the cutoff
system, where the _cutoff system_ is a system with exactly $c$ processes
interacting. In the literature, many results exist that provide cutoffs for
certain classes of properties in a given computational model (Emerson and
Namjoshi 2003; Emerson and Kahlon 2000), Außerlechner et al. (2016). Moreover,
cutoffs also enable the _synthesis_ of implementations for parameterized
systems from formal specifications (Jacobs and Bloem 2014), a problem closely
related to learning.

In this paper, we develop a learning approach for BPs. Given the
expressiveness of BPs and the complexity of the general problem, we make some
assumptions to keep the problem manageable. In particular, we assume (1) that
the BP under consideration has no hidden states, i.e., every state has at
least one broadcast sending action by which it can be recognized; and (2) that
there _exists_ a cutoff, i.e., a number $c$ such that the language (of finite
words over actions) derived by $c$ processes is the same as the language
derived by any number greater than $c$. We call such BPs _fine_ , and note
that many BPs studied in the literature are fine.

Moreover, the restriction to fine BPs does not overly simplify the problem, as
even under this assumption we obtain negative results for some basic learning
problems. We note that not all BPs have a cutoff (whether or not they have
hidden states), and that when a cutoff exists the derived language is regular.
The fact that the derived language is regular also holds in previous works on
learning concurrent models (communicating automata (Bollig et al. 2010),
workflow Petri nets (Esparza et al. (2011)), and negotiation protocols
(Muscholl et al. (2022))) merely since a finite number of essentially finite
state machines is in consideration.111The language of a BP in general need not
be regular (Finkel and Schnoebelen 2001; Geeraerts, Raskin, and Begin 2007)
and this is true also with the restriction to no hidden states. We emphasize
that this does not reduce the problem to learning a regular language, since
the aim is to obtain the concurrent representation, which we show to be much
more succinct than a DFA for the language. Moreover, the problem we consider
goes way beyond what has been considered in previous works in the sense that
our approach works if _there exists_ a cutoff, but it does not require that
the cutoff is known a priori, which is equivalent to the assumption of a
(given) fixed number of processes in existing approaches.

We focus mainly on passive learning paradigms (de la Higuera 2010).
Specifically, we consider the following problems:  1. _Inference_ — given a
sample consistent with a BP, return a BP that is consistent with the sample,
2. _Consistency_ — whether there exists a BP with at most $k$ states that
agrees with a given sample,  3. _Polynomial data_ — whether characteristic
sets are of polynomial size, and  4. _Polynomial Predictability_ — whether a
learner can correctly classify an unknown word with high probability after
asking polynomially many membership and draw queries.

We prove a few properties of fine BPs relevant to learning in §3. In §4, we
provide an inference algorithm that, given a sample of words that are
consistent with a fine BP, infers a correct BP. In §5, we show that the
inference algorithm produces a minimal equivalent BP when the sample subsumes
a characteristic set, and that characteristic sets of exponential size are
unavoidable. In §6, we show that consistency is NP-hard for the class of fine
BPs. Finally, in §7 we show that fine BPs are not polynomially predictable.
Full proofs are available in the appendix.

##  2 Preliminaries

### Broadcast Protocols

In the following we define broadcast protocols as introduced by Emerson and
Namjoshi (1998) and studied in the seminal paper by Esparza et al. (1999).
Broadcast protocols are one of the most powerful computational models for
which some parameterized verification problems are still decidable, and are
strictly more powerful than other standard communication primitives such as
pairwise rendezvous or disjunctive guards (Emerson and Kahlon 2003).

#### Broadcast Protocols (BPs)

A _broadcast protocol_ $B=(S,s_{0},L,R)$ consists of a finite set of states
$S$ with an initial state $s_{0}\in S$, a set of labels $L$ and a transition
relation $R\subseteq S\times L\times S$, where $L=\\{a!!,a??\mid a\in A\\}$
for some set of actions $A$. A transition labeled with $a!!$ is a broadcast
_sending transition_ , and a transition labeled with $a??$ is a broadcast
_receiving transition_ , also called a _response_.222Some models of BPs also
consider rendezvous transitions, usually labeled with $a!$ and $a?$, but these
can be simulated by broadcast transitions with a quadratic blowup in the
number of states. For each action $a\in A$, there must be exactly one outgoing
response from every state.

Given a BP $B=(S,s_{0},L,R)$ we consider systems $B^{n}$, composed of $n$
identical processes that execute $B$. Let $[n]$ denote the set
$\\{0,1,\ldots,n\\}$. A _configuration_ of $B^{n}$ is a function
$\textbf{q}:S\rightarrow[n]$, assigning to each state a number of processes.
The _initial configuration_ $\textbf{q}_{0}$ is the configuration with
$\textbf{q}_{0}(s_{0})=n$ and $\textbf{q}_{0}(s)=0$ for all $s\neq s_{0}$. In
a _global transition_ , all processes make a move: One process takes a sending
transition (labeled $a!!$), modeling that it broadcasts the value $a$ to all
the others processes in the system. Simultaneously, all of the other processes
take the receiving transition (labeled $a??$) from their current state.333We
give a formal semantics of $B^{n}$ below.

$s_{0}$$s_{1}$ $\textbf{M}_{a}=\begin{bmatrix}1&1\\\ 0&0\end{bmatrix}$
$\textbf{v}_{a}=\begin{bmatrix}1\\\ 0\end{bmatrix}$
$\textbf{v}_{a}^{\prime}=\begin{bmatrix}0\\\ 1\end{bmatrix}$
$\textbf{M}_{b}=\begin{bmatrix}0&0\\\ 1&1\end{bmatrix}$
$\textbf{v}_{b}=\begin{bmatrix}0\\\ 1\end{bmatrix}$
$\textbf{v}_{b}^{\prime}=\begin{bmatrix}0\\\ 1\end{bmatrix}$
$a!!,b??$$a??$$b!!,b??$$a??$

Figure 1: Left: a simple BP. Right: its algebraic representation.

######  Example 2.1 (A simple BP).

Fig.1 (left) depicts a simple BP $B$. In the initial configuration of the
system $B^{9}$ we have $9$ processes in $s_{0}$. If a process broadcasts $a$,
it moves to $s_{1}$ via the transition label $a!!$. The other processes
respond following the $a??$ transition from their current state, hence they
remain in $s_{0}$. Now we are in a configuration $\textbf{q}^{\prime}$ with
one process in $s_{1}$ and $8$ in $s_{0}$. If from $\textbf{q}^{\prime}$
another process broadcasts $a$, it moves from $s_{0}$ to $s_{1}$. The
processes in $s_{0}$ stay there (following $a??$ from $s_{0}$), and the
process in $s_{1}$ moves back to $s_{0}$ (following $a??$ from $s_{1}$). Thus,
we return to $\textbf{q}^{\prime}$. If from $\textbf{q}^{\prime}$ the process
in $s_{1}$ broadcasts $b$ then it remains in $s_{1}$ (following $b!!$), while
all other processes move to $s_{1}$ via $b??$ i.e., all processes will be in
$s_{1}$.

Following Esparza et al. (1999), we make the standard assumption that for each
action $a$, there is a unique state $s_{a}$ with an outgoing sending
transition on $a!!$. A state $s$ in a broadcast protocol is said to be
_hidden_ if it has no outgoing sending transition. In this paper we consider
broadcast protocols with no hidden states. Note that the additional assumption
of no hidden states is modest, since many examples from the literature satisfy
it (e.g., the MESI protocol in Esparza et al. (1999) or the last-in first-
served protocol in Delzanno et al. (1999)), and every protocol that does not
satisfy this restriction can easily be modified to satisfy it without changing
its functionality.

#### Semantics of $B^{n}$

We can represent transitions of a system $B^{n}$ algebraically. Assuming some
ordering $s_{0},s_{1},...s_{|S|-1}$ on the set of states $S$, we can identify
configurations of $B^{n}$ with vectors from $[n]^{|S|}$, also called _state-
vectors_. We use $\textbf{q}[i]$ to denote the entry in position $i$ of a
state-vector q. For example, let $\textbf{u}_{j}$ be the unit vector with
$\textbf{u}_{j}[j]{=}1$ and $\textbf{u}_{j}[i]{=}0$ for all $i\neq j$. Then
the configuration where all $n$ processes are in $s_{0}$ is the vector
$n\cdot\textbf{u}_{0}$. If q is a state-vector with $\textbf{q}[i]\geq 1$ we
say that $i$ is _lit_ in q. If state $s_{i}$ has an outgoing sending
transition on action $a$ we say that $a$ is _enabled_ in $s_{i}$; if $i$ is
lit in q we also say that $a$ is _enabled_ in q.

With each action $a$ we can associate  1 two unit-vectors
$\textbf{v}_{a}=\textbf{u}_{i}$ for the origin and
$\textbf{v}_{a}^{\prime}=\textbf{u}_{j}$ for the destination, following its
sending transition $(s_{i},a!!,s_{j})$, and  2 a _broadcast matrix_
$\textbf{M}_{a}$, which is an $|S|\times|S|$ matrix with
$\textbf{M}_{a}(m,k)=1$ if there is a response $(s_{k},a??,s_{m})\in R$, and
$\textbf{M}_{a}(m,k)=0$ otherwise. Every column of such a matrix is a unit
vector.

Then the transitions $T$ of $B^{n}$ are defined as follows: there is a
transition between configurations q and q’ on action $a$ in $B^{n}$, denoted
$(\textbf{q},a,\textbf{q}^{\prime})\in T$, iff there exists
$(s_{i},a!!,s_{j})\in R$ with $\textbf{q}[i]\geq 1$ and:
$\textbf{q}^{\prime}=\textbf{M}_{a}\cdot(\textbf{q}-\textbf{v}_{a})+\textbf{v}_{a}^{\prime}.$

To see this, note that the state-vector $\textbf{q}-\textbf{v}_{a}$
corresponds to the sending process leaving the state $s_{i}$. The state-vector
$\textbf{M}_{a}\cdot(\textbf{q}-\textbf{v}_{a})$ describes the situation after
the other processes take the responses on $a$. Finally, $\textbf{q}^{\prime}$
is the resulting state-vector after the sending process arrives at its target
location.

######  Example 2.2.

Consider again the BP in Fig.1, depicted with the broadcast matrices for the
two actions $\textbf{M}_{a}$ and $\textbf{M}_{b}$, and the associated origin
and destination vectors $\textbf{v}_{a}$, $\textbf{v}^{\prime}_{a}$,
$\textbf{v}_{b}$, $\textbf{v}^{\prime}_{b}$. In configuration
$\textbf{q}=\left[\begin{smallmatrix}2\\\ 2\end{smallmatrix}\right]$, $a$ is
enabled ($s_{0}$ is lit). Computing the effect of $a$, we first get
$\textbf{q}-\textbf{v}_{a}=\left[\begin{smallmatrix}1\\\
2\end{smallmatrix}\right]$, then
$\textbf{M}_{a}\cdot\left[\begin{smallmatrix}1\\\
2\end{smallmatrix}\right]=\left[\begin{smallmatrix}3\\\
0\end{smallmatrix}\right]$, and finally,
$\textbf{q}^{\prime}=\left[\begin{smallmatrix}3\\\
0\end{smallmatrix}\right]+\textbf{v}^{\prime}_{a}=\left[\begin{smallmatrix}3\\\
1\end{smallmatrix}\right]$.

An _execution_ of $B^{n}$ is a finite sequence
$e=\\!\textbf{q}_{0},a_{1},\allowbreak\textbf{q}_{1},a_{2},\ldots\\!,\allowbreak
a_{m},\textbf{q}_{m}$ such that
$(\textbf{q}_{i},a_{i+1},\textbf{q}_{i+1})\\!\in\\!T$ for every
$i\in[m\\!-\\!1]$. We say that $e$ is _based on_ the sequence of actions
$a_{1},\ldots,a_{m}$ and that $B^{n}(a_{1}\ldots a_{m})=\textbf{q}_{m}$. We
say that a word $w\in A^{*}$ is _feasible_ in $B^{n}$ if there is an execution
of $B^{n}$ based on $w$. The _language_ of $B^{n}$, denoted $L(B^{n})$, is the
set of all words that are feasible in $B^{n}$, and the language of $B$,
denoted $L(B)$, is the union of $L(B^{n})$ over all $n\in\mathbb{N}$.

Let $B_{1}$ and $B_{2}$ be two BPs. We say that $B_{1}$ and $B_{2}$ are
_equivalent_ iff $L(B_{1}){=}L(B_{2})$. A BP $B$ is said to have a _cutoff_
$k\in\mathbb{N}$ if for any $k^{\prime}>k$ it holds that
$L(B^{k})=L(B^{k^{\prime}})$. A BP with no hidden states is termed _fine_ if
it has a cutoff. We measure the size of a BP by its number of states. Thus, a
BP is termed _minimal_ if there is no equivalent BP with fewer states. Note
that unlike the case of DFAs, there is no unique minimal fine BP, as shown by
the following example.

######  Example 2.3.

Fig.2 shows two BPs $B_{1}$ and $B_{2}$. Note that $L(B_{1}^{1})=a^{*}$, since
with a single process, $a$ is the only possible action from $\textbf{q}_{0}$,
and we arrive in $\textbf{q}_{0}$ after executing it. With $2$ processes,
after executing $a$ we arrive in state-vector $\left[\begin{smallmatrix}1\\\
1\end{smallmatrix}\right]$, and we can execute either $a$ or $b$, and each of
them brings us to $\left[\begin{smallmatrix}1\\\ 1\end{smallmatrix}\right]$
again. Therefore, $L(B_{1}^{2})=a(a\cup b)^{*}$. Moreover, adding more
processes does not change the language, i.e., $L(B_{1}^{n})=L(B_{1}^{2})$ for
all $n$. Hence $L(B_{1})=L(B_{1}^{2})$ and the cutoff of $B_{1}$ is $2$.
Similarly, we can show that $L(B_{2})=a(a\cup b)^{*}$ and the cutoff of
$B_{2}$ is $2$. Note that $B_{1}$ and $B_{2}$ are not isomorphic, but they are
equivalent.

01$B_{1}:$01$B_{2}:$$a??,b??$$b!!$$a!!$$a??,b??$$a??$$a!!,b??$$b!!,a??,b??$

Figure 2: Two non-isomorphic fine BPs:
$L\\!(\\!B_{1}\\!)\\!=\\!L\\!(\\!B_{2}\\!)\\!=\\!a(\\!a\cup b\\!)^{*}$.

We note that the aforementioned examples from the literature (Esparza et al.
(1999) and Delzanno et al. (1999)) also have a cutoff, and thus are fine BPs.

### Learning problems

A _sample_ for a BP $B$ is a set $\mathcal{S}$ of triples in
$A^{*}\times\mathbb{N}\times\mathbb{B}$ where
$\mathbb{B}=\\{\textsc{t},\textsc{f}\\}$. A triple $(w,n,\textsc{t})$ (resp.
$(w,n,\textsc{f})$) is consistent with $B$ if $w$ is feasible (resp.
infeasible) in $B^{n}$. A sample is _consistent_ with $B$ if all triples in it
are consistent with $B$. The size of $\mathcal{S}$ is defined as the sum of
length of words in it.

We consider the following problems related to learning a class $\mathcal{C}$
of computational models, phrased for BPs.

######  Problem 2.1 (Inference).

Devise an algorithm that given a sample $\mathcal{S}$ that is consistent with
some BP in $\mathcal{C}$ returns a BP $B\in\mathcal{C}$ that is consistent
with $\mathcal{S}$. We refer to such an algorithm as an _inference algorithm_.

Obviously one would prefer the returned BP to be minimal or sufficiently
small. Phrased as a decision problem this is the consistency problem.

######  Problem 2.2 (Consistency).

Given a sample $\mathcal{S}$ and $k\in\mathbb{N}$ determine whether there
exists a BP $B\in\mathcal{C}$ consistent with $\mathcal{S}$ with at most $k$
states.

The consistency problem is NP-hard even for DFAs (Gold 1978). Thus, inference
algorithms are often based on SAT or SMT solvers In §4 we provide such an
inference algorithm for fine BPs. Note that in many cases it is possible to
devise a trivial inference algorithm (e.g., for DFAs the prefix-tree
automaton) that is correct on the sample but makes no generalization and does
not attempt to minimize the returned result. We show in §5 that if the sample
is sufficiently complete (subsumes a _characteristic set_), the inference
algorithm we provide in fact returns the minimal BP that agrees with the
sample. One may thus ask how large should a characteristic set be. We show
that, unfortunately, it can be of size exponential in the number of states of
the BP.

######  Problem 2.3 (Polynomial data).

Does there exist an inference algorithm $\mathfrak{A}$ such that one can
associate with every BP $B\in\mathcal{C}$ a sample $\mathcal{S}_{B}$ of size
polynomial in $B$ so that $\mathfrak{A}$ correctly infers $L(B)$ from
$\mathcal{S}_{B}$ or any sample subsuming it.

The last problem we consider is in the active learning paradigm. Its
definition is quite long and deferred to §7.

######  Problem 2.4 (Polynomial Predictability).

Can a learner correctly classify an unknown word with high probability after
asking polynomially many membership and draw queries.

##  3 Properties of Broadcast Protocols

Below we establish some properties regarding broadcast protocols that will be
useful in devising the learning algorithm. The proofs are given in Appendix A.

It is not hard to see that the set of feasible words $L(B)$ of a given BP is
prefix-closed. That is, if $uv$ is feasible for $u,v\in A^{*}$ then $u$ is
feasible as well. Additionally, if $w\in A^{*}$ is feasible in $B^{k}$ then
$w$ is feasible in $B^{\ell}$ for all $\ell>k$.

######  Lemma 3.1 (Prefix-closedness and monotonicity).

If $B$ is a BP then $L(B)$ is prefix-closed. Moreover, $L(B^{k})\subseteq
L(B^{\ell})$ for all $\ell>k$.

The following lemma asserts that if $wa$ is feasible with $n$ processes but
not with $m<n$, while $w$ is feasible with $m$ processes (for $w\in A^{*}$ and
$a\in A$) then $wa$ must be feasible with $m+1$ processes. Intuitively this is
since $m$ processes are enough to execute all actions in $w$, and therefore
any additional processes will take only receiving transitions along $w$, and
will all arrive in the same local state. Thus, if $a$ is not enabled after $w$
with $m+1$ processes, then the additional process did not lit the state
$s_{a}$ enabling $a$, and the same is true if we add any bigger number of
processes.

######  Lemma 3.2 (Step by step progress).

Let $w\in A^{*}$, $a\in A$, and $m<n$. If $w\in L(B^{m})$ and $wa\notin
L(B^{m})$ yet $wa\in L(B^{n})$, then $wa\in L(B^{m+1})$.

Recall that fine BPs have no canonical minimal representation, in the sense
that, as shown in Ex.2.3, there could be two non-isomorphic BPs for the same
language. The lack of a canonical minimal representation often makes it
difficult to achieve a learning algorithm. The following important lemma
asserts, that while two minimal fine BPs may be non-isomorphic there is a
tight correlation between them.

Since every action is enabled by a unique state, and every state enables at
least one action, in a minimal fine BP the set $A$ is partitioned between
states, and if there is a state $s_{1}$ in $B_{1}$ whose set of enabled
actions is $A^{\prime}=\\{a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}\\}$ then there
should be a state $s_{2}$ in $B_{2}$ for which the set of enabled actions is
exactly $A^{\prime}$. So we can define such a mapping between the states of
two minimal fine BPs, and it must be that on every word $w$ if
$\textbf{p}_{w}$ and $\textbf{q}_{w}$ are the state-vectors $B_{1}$ and
$B_{2}$ reach after reading $w$, resp., then if state $s_{1}$ is lit in
$\textbf{p}_{w}$ then the corresponding state $s_{2}$ (that agrees on the set
of enabled actions) is lit in $\textbf{q}_{w}$. Moreover, the fact that
$L(B_{1})=L(B_{2})$ guarantees that $L(B_{1}^{m})=L(B_{2}^{m})$ for any
$m\in\mathbb{N}$. This bundle of claims can be proven together by induction
first on the number of processes $m$, and second the length of the word $w$.
In the following we use $f^{\textsf{act}}(s)=A^{\prime}$ if $A^{\prime}$ is
the set of actions enabled in $s$.

######  Lemma 3.3 (Relation between minimal fine equivalent BPs).

Let $B_{1}$ and $B_{2}$ be minimal fine BPs with states $S_{1}$ and $S_{2}$
such that $L(B_{1}){=}L(B_{2})$. Then for every $m\in\mathbb{N}$ it holds that
$L(B_{1}^{m}){=}L(B_{2}^{m})$ and there exists a bijection $h:S_{1}\to S_{2}$
satisfying that $f^{\textsf{act}}(s){=}f^{\textsf{act}}(h(s))$ for any
$s{\in}S_{1}$; and for any $w\in A^{*}$ if $B_{1}^{m}(w)=\textbf{p}_{w}$ and
$B_{2}^{m}(w)=\textbf{q}_{w}$ then $\textbf{p}_{w}[i]$ is lit if and only if
$\textbf{q}_{w}[h(i)]$ is lit, for every state $i$.

##  4 Inferring a BP from a Sample

Let $\mathcal{S}$ be a sample. The inference algorithm $\mathfrak{I}$ we
devise constructs a BP $B_{\mathcal{S}}$ that agrees with $\mathcal{S}$.

Let $A_{\mathcal{S}}$ be the set of actions that appear in $\mathcal{S}$ in at
least one feasible word. In order to return a BP $B_{\mathcal{S}}$ with no
hidden states, we allow $B_{\mathcal{S}}$ to have a set of actions $A\supseteq
A_{\mathcal{S}}$.444Note that in §5 we show that it is enough to consider
$A=A_{\mathcal{S}}$ if $\mathcal{S}$ is sufficiently complete. We use $S$ for
the set of states of $B_{\mathcal{S}}$, and $s_{0}$ for its initial state.

We construct a set of constraints that define the BP $B_{\mathcal{S}}$. More
precisely, we construct a set of constraints $\Psi_{\mathcal{S}}$ regarding
the behavior of three partial functions
$f^{\textsf{st}}:\\!A\\!\rightarrow\\!S$,
$f^{\textsf{!!}}:\\!A\rightarrow\\!S$, and
$f^{\textsf{??}}_{a}:\\!S\\!\rightarrow\\!S$ for every $a\\!\in\\!A$ so that
any valuation of these functions that satisfies $\Psi_{\mathcal{S}}$ implement
a BP consistent with the sample. Formally, we say that functions
$f^{\textsf{st}},f^{\textsf{!!}},\\{f^{\textsf{??}}_{a}\mid a\in A\\}$
_implement_ a BP $B=(S,s_{0},L,R)$ if for every $(s_{i},a!!,s_{j})\in R$ we
have $f^{\textsf{st}}(a)=s_{i}$, $f^{\textsf{!!}}(a)=s_{j}$ and for every
$(s_{i},a??,s_{j})\in R$ we have $f^{\textsf{??}}_{a}(s_{i})=s_{j}$. We also
use $f^{\textsf{act}}(s)=A^{\prime}$ if $A^{\prime}=\\{a\in
A~{}|~{}f^{\textsf{st}}(a)=s\\}$.

We turn to introduce some terminology regarding the sample. Let
$\mathcal{P}_{i}$ be the set of words
$\\{w\colon\\!(w,i,\textsc{t})\\!\in\\!\mathcal{S}\\}$, and let
$\mathcal{N}_{i}$ be $\\{w\colon\\!(w,i,\textsc{f})\\!\in\\!\mathcal{S}\\}$.
Note that by Lem.3.1 it follows that if $w\\!\in\\!\mathcal{P}_{i}$ then $w$
is feasible in $B^{j}$ for every $j\\!\geq\\!i$. Similarly, if
$w\\!\in\\!\mathcal{N}_{i}$, then $w$ is infeasible in $B^{j}$ for every
$j\\!\leq\\!i$. We define $\mathcal{N}$ (resp. $\mathcal{P}$) as the union of
all $\mathcal{N}_{i}$’s (resp. $\mathcal{P}_{i}$’s).

We define a relation between actions $a,b\in A_{\mathcal{S}}$ as follows. We
say that $a\,\\#_{\mathcal{S}}\,b$ if there exist a word $w\in
A_{\mathcal{S}}^{*}$ and naturals $n^{\prime}\geq n$ such that
$(wa,n,\textsc{t})\in\mathcal{S}$ and
$(wb,n^{\prime},\textsc{f})\in\mathcal{S}$ or vice versa (switching the roles
of $a$ and $b$). Following Lem.3.3, $a\,\\#_{\mathcal{S}}\,b$ means that the
sample $\mathcal{S}$ has information contradicting that $a$ and $b$ are
enabled in the same state.

  1. 1.

Our first constraints are therefore that for every $a,b\in A$ such that
$a\,\\#_{\mathcal{S}}\,b$ it holds that $f^{\textsf{st}}(a)\neq
f^{\textsf{st}}(b)$.

  2. 2.

Since we identify states by the set of actions they enable and we assume there
are no hidden states, we define the set of states
$S=\\{f^{\textsf{st}}(a)\colon a\in A\\}$ as the set of terms
$f^{\textsf{st}}(a)$. This definition guarantees that no states are hidden.
Moreover, we designate one of the states, that we term $s_{0}$, as the initial
state: $\exists s\in S\colon s=s_{0}$.

  3. 3.

The rest of the constraints are gathered by scanning the words first by
length. For every word of length one, i.e. action $a$, if
$au\in\mathcal{P}_{i}$ for some $i$ and some $u\in A^{*}$ then we add
$f^{\textsf{st}}(a)=s_{0}$, and if $a\in\mathcal{N}_{i}$ then we add
$f^{\textsf{st}}(a)\neq s_{0}$.

  4. 4.

Next, we scan inductively for every word $w\in\mathcal{P}$ for the minimal
$i\geq 1$ such that $w\in\mathcal{P}_{i}$ and for every $w\in\mathcal{N}$ for
the maximal $i\geq 1$ such that $w\in\mathcal{N}_{i}$.

In the base case $i{=}1$ we have $w\in\mathcal{P}_{1}\cup\mathcal{N}_{1}$. Let
$w=\allowbreak{a_{1}a_{2}{\ldots}a_{m}}$. We define $m{+}1$ variables
$p_{0},p_{1},\ldots p_{m}$. The variable $p_{k}$ indicates the state the
process reaches after the system reads $a_{1}\ldots a_{k}$, and $p_{0}$ should
be $s_{0}$.

If $w\in\mathcal{P}_{1}$, we add the constraint $\psi_{w,1}$ defined as

$\begin{array}[]{l}\left(p_{0}=s_{0}\right)\wedge\bigwedge_{1\leq\ell\leq
m}\left(p_{\ell-1}=f^{\textsf{st}}(a_{\ell})\wedge
p_{\ell}=f^{\textsf{!!}}(a_{\ell})\right)\end{array}$

This requires that the next letter $a_{\ell}$ is enabled in the state the
process reached after $a_{1}a_{2}\ldots a_{\ell-1}$ was executed.

If ${w\in\mathcal{N}_{1}}$ we add the following constraint

$\begin{array}[]{l}\displaystyle\bigvee_{0\leq\ell<m}\left(\psi_{w[..\ell],1}\wedge
p_{\ell}\neq f^{\textsf{st}}(a_{\ell+1})\right)\end{array}$

where $w[..\ell]$ denotes the $\ell$’th prefix of $w$, namely
$a_{1}a_{2}\ldots a_{\ell}$, and we let $\psi_{\epsilon,1}=\textsc{t}$. This
requires that at least one of the letters in the word is not enabled in the
state the process reached, implying the entire word is infeasible with one
process.

  5. 5.

For the induction step $i>1$, let $w\in\mathcal{P}_{i}\cup\mathcal{N}_{i}$ and
assume $w=a_{1}a_{2}\ldots a_{m}$. We define $i(m+1)$ variables
$p_{1,0},p_{2,0},\ldots p_{i,m}$. The variable $p_{j,k}$ indicates the state
the $j$-th process reaches after the system reads $a_{1}\ldots a_{k}$.
Accordingly, we set $p_{j,0}=s_{0}$ for every $1\leq j\leq i$. The state of
the processes after reading the next letter, $a_{l+1}$, depends on their state
after reading $a_{l}$.

Let ${w{\in}\mathcal{P}_{i}}$, we add the constraint $\psi_{w,i}$ defined as
follows.

$\psi_{w,i}=\begin{array}[]{l}\displaystyle\bigwedge_{1\leq\ell\leq
m}\left(\bigvee_{1\leq j\leq
i}\left(\left(p_{j,\ell-1}=f^{\textsf{st}}(a_{\ell})\right)\wedge\varphi_{j,\ell}\right)\right)\end{array}$

where

$\displaystyle\varphi_{j,\ell}=\left(\begin{array}[]{c}p_{j,\ell}=f^{\textsf{!!}}(a_{\ell})\quad\wedge\\\
\displaystyle\bigwedge_{{\begin{array}[]{c}1\leq j^{\prime}\leq i\\\
j^{\prime}\neq
j\end{array}}}p_{j^{\prime},\ell}=f^{\textsf{??}}_{a_{\ell}}(p_{j^{\prime},\ell-1})\end{array}\right)$

Intuitively, $\psi_{w,i}$ requires that for every letter $a_{\ell}$ of $w$ one
of the processes, call it $j$, reached a state in which $a_{\ell}$ is enabled.
The formula $\varphi_{j,\ell}$ states that the $j$-th process took the sending
transition on $a_{\ell}$ and the rest of the processes took the respective
receiving transition.

Let $w\in\mathcal{N}_{i}$. We then add the following requirement

$\begin{array}[]{l}\displaystyle\bigvee_{0\leq\ell<m}\left(\psi_{w[..\ell],i}\wedge\bigwedge_{1\leq
j\leq i}\left(p_{j,\ell}\neq
f^{\textsf{st}}(a_{\ell+1})\right)\right)\end{array}$

where we let $\psi_{\epsilon,i}=\textsc{t}$ for every $i$.

Intuitively, if $w$ is infeasible with $i$ processes, then there exists a
(possibly empty) prefix $w[..\ell]$ which is feasible with $i$ processes,
therefore $\psi_{w[..\ell],i}$ holds, while $w[..\ell\\!+\\!1]$ is infeasible,
meaning none of the $i$ processes is in a state where $a_{\ell+1}$ is enabled.

######  Theorem 4.1.

Let $\mathcal{S}$ be a sample that is consistent with some fine BP. Let
$B_{\mathcal{S}}$ be a BP that satisfies the prescribed constraints
$\Psi_{\mathcal{S}}$. Then $B_{\mathcal{S}}$ is a BP consistent with
$\mathcal{S}$.

###### Proof.

We prove that if $w{\in}\mathcal{P}_{i}$ (resp. $w{\in}\mathcal{N}_{i}$) then
$w$ is feasible (resp. infeasible) in $B_{\mathcal{S}}^{i}$, by induction
first on the length of $w$ and then on $i$. For $w$ of length $1$, this holds
by the constraints in item (3). Let
$w\\!=\\!a_{1}a_{2}\\!\ldots\\!a_{n}{\in}\mathcal{P}_{i}$. If $i{=}1$ then
this holds by induction on $w$ thanks to constraint (4). Next we consider
words of the form $w$ that are in $\mathcal{P}_{i}\cup\mathcal{N}_{i}$. If
$w\in\mathcal{P}_{i}$ is already in $\mathcal{P}_{j}$ for $j<i$ then by the
induction hypothesis it is already feasible for $j$ processes in the
constructed BP, and by Lem.3.1, it is also feasible with $i$ processes.
Otherwise, $w\in\mathcal{P}_{i}\setminus\bigcup_{j{<}i}\,\mathcal{P}_{j}$. In
this case, constraint (5) makes sure that every prefix of $w$ is feasible with
$i$ processes, and requiring that for the next letter $a_{\ell}$ one of the
$i$ processes reached the state enabling $a_{\ell}$ after reading the prefix
up to $a_{\ell\\!-\\!1}$.

If $w{\in}\mathcal{N}_{i}$ then $w$ is infeasible with $i$ processes. In this
case, there exists a letter $a_{\ell}$ for $1\\!\leq\\!\ell\\!\leq\\!m$ such
that while $w[..\ell{-}1]$ is feasible, $a_{\ell}$ is not enabled in any of
the states that the $i$ processes reach after reading (the possibly empty)
prefix $w[..\ell{-}1]$. This is exactly what constraint (5) stipulates, which
is added for $i$ or some $j>i$. In the latter case, Lem.3.1 implies that $w$
is infeasible in $B_{\mathcal{S}}^{i}$. ∎

Finally, note that our constraints are in the theory of equality with
uninterpreted functions (EUF), and are therefore decidable.555While constraint
(2) depends on the unknown set $A$, we can bound the size of $A$, e.g., by the
size of the prefix tree of $\mathcal{S}$. Thus, an algorithm for inferring
fine BPs can be implemented using an SMT solver.

######  Corollary 4.2.

$\mathfrak{I}$ is an inference algorithm for fine BPs.

##  5 Returning a Minimal BP

In this section we show that when the sample is sufficiently complete we can
guarantee that we return a minimal equivalent BP, and not just a BP that
agrees with the sample. We thus first show that every fine BP $B$ can be
associated with a sample $\mathcal{S}_{B}$ so that there exists an inference
algorithm $\mathfrak{A}$ that when applied to any sample $\mathcal{S}$ that
subsumes $\mathcal{S}_{B}$ and is consistent with $B$, returns a minimal fine
BP that is equivalent to $B$. We refer to such a sample as a _characteristic
set_ (CS).

In the following, we first describe a procedure $\mathfrak{G}$ that generates
a sample $\mathcal{S}_{B}$ from a fine BP $B$, and then we prove that an
inference algorithm $\mathfrak{A}$ can correctly infer a minimal BP
$B^{\prime}$ equivalent to $B$ from any sample subsuming $\mathcal{S}_{B}$.

### Generating a Characteristic Set

The CS generation algorithm $\mathfrak{G}$ builds a sequence of trees
$\mathcal{T}_{i}$ starting with $i=0$ and incrementing $i$ by one until
$\mathcal{T}_{i+1}=\mathcal{T}_{i}$. The edges of the tree are actions. The
name of a node is taken to be the unique sequence of actions $w$ that leads to
it. Thus, the root is named $\varepsilon$ and a child of a node $w\in A^{*}$
is named $wa$ for some $a\in A$. A node $w\in A^{*}$ in tree $\mathcal{T}_{i}$
is annotated with $B^{i}(w)=\textbf{p}_{w,i}$, i.e. the state-vector $B^{i}$
reaches when reading $w$, if $w$ is feasible in $B^{i}$, and with the special
symbol $\bot$ otherwise. We call a node in the tree _positive_ if it is
annotated with a state-vector, and _negative_ otherwise. All nodes are either
leaves or have exactly $|A|$ children. Negative nodes are always leaves.

The tree $\mathcal{T}_{0}$ consists of only a root $\varepsilon$ and is
annotated with the state-vector of all zeros. The tree $\mathcal{T}_{i+1}$ is
constructed from the tree $\mathcal{T}_{i}$ by first re-annotating all its
nodes: The annotation of a positive $\textbf{p}_{w,i}$ is replaced by
$\textbf{p}_{w,i+1}$, a negative node $w$ in $\mathcal{T}_{i}$ may become
positive in $\mathcal{T}_{i+1}$ (if $w$ is feasible with $i+1$ processes) and
will be annotated accordingly with $\textbf{p}_{w,i+1}$. Then we check, from
every positive node, whether further exploration is needed. A positive node
will be declared a leaf if it is of the form $va$ and it has an ancestor $u$,
a prefix of $v$, for which $\textbf{p}_{u,i+1}=\textbf{p}_{v,i+1}$. Otherwise
its $|A|$ children are constructed. That is, once we reach a node whose state-
vector is the same as one of its ancestors, we develop its children, but the
children are not developed further.

The entire process terminates when $\mathcal{T}_{i+1}=\mathcal{T}_{i}$.666We
say $\mathcal{T}_{i+1}=\mathcal{T}_{i}$ if they agree on the tree structure
and the edge labels (regardless of the nodes’ annotations). Note that given
that the BP has a cutoff, such an $i$ must exist. We use $\mathcal{T}$ for the
last tree constructed, namely $\mathcal{T}_{i+1}$. The sample is then produced
as follows. For $n\in[i+1]$, let $\mathcal{P}_{n}=\\{(u,n,\textsc{t})~{}|~{}n$
is the minimal for which $u$ is positive in $\mathcal{T}_{n}\\}$,
$\mathcal{N}_{n}=\\{(u,n,\textsc{f})~{}|$ $n$ is the maximal for which $u$ is
negative in $\mathcal{T}_{n}\\}$. Then the sample is
$\mathcal{S}_{B}=\bigcup_{n=1}^{i+1}\left(\mathcal{P}_{n}\cup\mathcal{N}_{n}\right)$.

### Proving that $\mathfrak{G}$ generates characteristic sets

We first note that for any reachable state $s$ of the original BP, there
exists at least one node $v$ in the tree where $s$ is lit (i.e. the entry for
$s$ in the state-vector annotating the node is lit). The following lemma
strengthens this statement further.

######  Lemma 5.1.

Let p be a state-vector that is reachable in $B^{n}$. Then for every shortest
word $w$ that reaches p in $B^{n}$ there exists a node $w$ in
$\mathcal{T}_{n}$ such that $\textbf{p}_{w}=\textbf{p}$.

When the sample $\mathcal{S}$ subsumes the set $\mathcal{S}_{B}$ then
$\,\\#_{\mathcal{S}}\,$ induces an equivalence relation between the actions:

######  Lemma 5.2.

For two actions $a$ and $b$ define $a\sim_{\mathcal{S}}b$ iff it is not the
case that $a\,\\#_{\mathcal{S}}\,b$. If $\mathcal{S}$ subsumes
$\mathcal{S}_{B}$ then $\sim_{\mathcal{S}}$ is an equivalence relation.

######  Theorem 5.3.

Let $B$ be a fine minimal BP, and let $\mathcal{S}_{B}$ be the sample
generated for it as above. There is an inference algorithm $\mathfrak{A}$ such
that if $B^{\prime}$ is the result of $\mathfrak{A}$ when applied to any set
subsuming $\mathcal{S}_{B}$ and consistent with $B$ then $B^{\prime}$ is
minimal and $L(B^{\prime})=L(B)$.

###### Proof.

The inference algorithm $\mathfrak{A}$ we use to prove this claim runs in two
steps. First it runs a variation $\mathfrak{I^{\prime}}$ of the inference
algorithm $\mathfrak{I}$ presented in §4 that turns the constraint (1) into an
iff constraint. I.e. adding that $f^{\textsf{st}}(a)=f^{\textsf{st}}(b)$
unless $a\,\\#_{\mathcal{S}}\,b$. If running $\mathfrak{I^{\prime}}$ returns
that there is no satisfying assignment then it runs $\mathfrak{I}$. In both
cases Thm. 4.1 guarantees that the returned BP is consistent with the given
sample. Therefore $\mathfrak{A}$ is an inference algorithm.

Next we claim that if the given sample subsumes $\mathcal{S}_{B}$ then
$B^{\prime}$, the resulting BP, is minimal. This holds since Lem.5.2 ensures
that $\,\\#_{\mathcal{S}}\,$ defines the desired equivalence
$\sim_{\mathcal{S}}$ between actions, and the revised constraint (1)
guarantees that actions are not enabled from the same state if and only if the
sample separates them. (Note that any word consistent with the BP cannot
separate actions $a$ and $b$ if they are enabled from the same state.) Hence
$\mathfrak{I^{\prime}}$ will not return that there is no satisfying
assignment.

Next we note that by Lem.5.1 for every state-vector p that is reachable in
$B^{m}$ and for every shortest word $w$ that reaches p in $B^{m}$ there exists
a node $w$ in $\mathcal{T}_{m}$ such that $\textbf{p}_{w}=\textbf{p}$. If
$w=a_{1}a_{2}\ldots a_{n}$ then for each $1\leq i\leq n$ one process took the
sending transition $a_{i}!!$ and the rest of the processes responded with
$a_{i}??$. Constraint (5) makes sure the assignment to $f^{\textsf{st}}$,
$f^{\textsf{!!}}$ and $f^{\textsf{??}}$ respect all the possible options that
enabled this, making sure that for every two options for enabling $w$ that
result in state-vectors $\textbf{p}_{1}$ and $\textbf{p}_{2}$, resp., the same
states are lit in both $\textbf{p}_{1}$ and $\textbf{p}_{2}$.

Hence, for any BP $B^{\prime}$ that adheres to the constraints there exists a
mapping $h$ between the states of $B$ and $B^{\prime}$ satisfying the
requirements of Lem.3.3. Thus, $L(B)\\!=\\!L(B^{\prime})$. ∎

Regarding the problem of _polynomial data_ we show that there exist fine BPs
for which there is no CS of polynomial size. The proof constructs a family of
BPs of size quadratic in $n$ for which there exists an action $a_{\top}$ such
that the length of the shortest word containing $a_{\top}$ is exponential in
$n$. Thus, any CS has to include at least one such long word.

######  Theorem 5.4.

There exists a family of fine BPs with no characteristic set of polynomial
size.

The same family used in the proof of Thm.5.4 also shows that fine BPs can be
exponentially smaller than the minimal DFA accepting the same language. This
is since in a DFA for every state $q$ the length of the shortest word reaching
$q$ is bounded by the number of states in the DFA.

######  Corollary 5.5.

There exists a family of fine BPs for which the corresponding minimal DFA is
of exponential size.

##  6 Consistency is NP-Hard for fine BPs

We show below that consistency is NP-hard even for fine BPs. We note that
hardness is expected since DFA consistency is NP-hard (Gold 1978), but it does
not directly follow from hardness of DFA consistency. This is since a DFA is
not a special case of a fine BP. However, a fine BP can simulate a DFA, in a
manner prescribed in Lem.6.1.

Fig.3 provides a schematic illustration of the simulation. The states in the
rectangle are the original states of the DFA, and $\iota$ is the initial state
of the DFA. All responses that are not shown in the figure are self-loops, we
omit them to avoid clutter. In addition, to make the BP fine, we need to allow
each state $q$ to enable some action, call it $q$. The simulation would like
to ignore these actions, i.e. consider the projection of the words to words
without these actions. Formally, let $\Gamma,\Gamma^{\prime}$ be alphabets
such that $\Gamma^{\prime}\supseteq\Gamma$. Let $w^{\prime}$ be a word over
$\Gamma^{\prime}$. We use $\pi_{\Gamma}(w^{\prime})$ for the word obtained
from $w^{\prime}$ by removing letters in $\Gamma^{\prime}\setminus\Gamma$. If
$B$ is a BP over $A^{\prime}$, such that $A^{\prime}\supseteq A$, we refer to
the words in $\\{\pi_{A}(w)~{}|~{}w\in L(B)\\}$, abbreviated $\pi_{A}(L(B))$,
as the $A$-feasible words of $B$. Lem.6.1 states in which manner the BP
simulates the DFA.

i$\iota$$D$$q^{\prime}$$q^{\prime\prime}$$\top$$\bot$cx$i!!$$i??$$\$??$$\$??$$\Sigma!!$$\$!!,\$??$$x!!$$\bot!!$$\top!!$$\top??$$\bot??$$\$??$

Figure 3: Reduction from DFA-consistency to BP-consistency.

######  Lemma 6.1.

Let $L$ be a non-trivial regular language over $\Sigma$, and assume $n$ is the
number of states in the minimal DFA for $L$.777A language is non-trivial if it
is not the empty set or $\Sigma^{*}$. Let
$A=\Sigma\cup\\{i,\$,\top,\bot,x\\}$.

  1. 1.

There exists a fine BP $B$ over actions $A^{\prime}$ such that
$A^{\prime}\supseteq A$ satisfying that $\pi_{A}(L(B^{1}))=\\{i\\}$ and
$\pi_{A}(L(B^{n}))\subseteq i(\Sigma)^{*}\$x^{*}(\top^{*}\cup\bot^{*})$ for
every $n\geq 2$.

  2. 2.

In addition, for every $w\in\Sigma^{*}$:

     * •

$w\in L\Leftrightarrow(iw\$\top,2)$ is feasible in $B$.

     * •

$w\notin L\Leftrightarrow(iw\$\bot,2)$ is feasible in $B$.

  3. 3.

Moreover, for every $B$ satisfying the above it holds that $B$ has at least
$n+5$ states.

###### Proof sketch.

In order to keep the number of processes in the DFA part exactly one, the $i$
action from the initial state of the BP (state i) sends one process to $\iota$
and the rest to state c. To allow every letter $\sigma\in\Sigma$ to be taken
from every state of the DFA, the state c of the BP enables all letters in
$\Sigma$, and the original $(q,\sigma,q^{\prime})$ transitions of the DFA are
transformed into responses $(q,\sigma??,q^{\prime})$. Next, to deal with the
fact that the language of a DFA is defined by the set of words that reach an
accepting state whereas the language of a BP is the set feasible words, we
introduce the letters $\$$, $\top$ and $\bot$. Upon $\$$ the single process in
one of the DFA states moves into either state $\bot$ or state $\top$ depending
on whether it was in an accepting state or a rejecting state; and all
processes in states c move to state x where they wait to follow the respective
$\bot$ or $\top$. Now only $\\{x,\top\\}$ or $\\{x,\bot\\}$ are enabled. An
$x!!$ transition would not change this situation whereas a $\top$ (resp.
$\bot$) transition will ensure only $\top$ (resp. $\bot$) can be taken
henceforth. The complete proof, given in App. C shows the three requirements
of the lemma are satisfied. ∎

######  Theorem 6.2.

BP consistency is NP-hard.

###### Proof Sketch.

The proof is by reduction from DFA consistency which was shown to be NP-hard
in (Gold 1978). Given an input to DFA-consistency, namely a sample
$\mathcal{S}$ and a number $k$, we produce a sample $\mathcal{S}^{\prime}$ and
$k^{\prime}=k+5$ as an input to BP-consistency so that the relation between
the minimal BP consistent with $\mathcal{S^{\prime}}$ and the minimal DFA
consistent with $\mathcal{S}$ is as described in Lem.6.1.

The sample $\mathcal{S}^{\prime}$ consists of various triples ensuring a BP
consistent with $\mathcal{S}^{\prime}$ has the structure given in Fig.3. For
instance, $(i,1,\textsc{t})$ and $(ii,2,\textsc{f})$ enforce that $i$ is
enabled in the initial state but is not a self-loop. A pair $(w,\textsc{t})$
(resp. $(w,\textsc{f})$) in $\mathcal{S}$ is altered to triple
$(iw\$\top\top,2,\textsc{t})$ (resp. $(iw\$\bot\bot,2,\textsc{t})$ in
$\mathcal{S}^{\prime}$, making sure that words accepted (resp. rejected) by
the DFA create respective feasible words ending with $\top$’s (resp.
$\bot$’s). Each such pair carries some additional triples added to
$\mathcal{S}^{\prime}$ to continue enforcing the structure of Fig.3. ∎

An alternative proof, inspired by (Lingg et al.2024) via a direct reduction
from all-eq-sat is available in App. C.

Note that given a BP $B$ and a pair $(w,n)\in A^{*}\times\mathbb{N}$ it is
possible to check in polynomial time whether $w$ is feasible in $B^{n}$ by
developing the state-vector $n\cdot\textbf{u}_{0}$ along the word $w$ in $B$.
Consequently, and since a BP with $m$ states over set of actions $A$ can be
described in size polynomial in $m$ and $|A|$, if $m$ is given in unary then
BP-consistency is NP-complete.

##  7 BPs are not polynomially predictable

Here we show that fine BPs are not polynomially predictable with membership
queries. The learning paradigm of polynomial predictability of a class
$\mathcal{C}$ can be explained as follows. The learner has access to an oracle
answering _membership queries_ (mq) with regard to the target language
$C\in\mathcal{C}$ or _draw queries_ (dr) that can be implemented using mq. A
membership query receives a word $w$ as input and answers whether $w$ is or is
not in $C$. A draw query receives no inputs and returns a pair $(w,b)$ where
$w$ is a word that is randomly chosen according to some probability
distribution $D$ and $b$ is $\textsc{mq}(w)$. We assume some bound $\ell$ on
the length of the relevant examples, so that $D$ is a probability distribution
on the set of relevant words. We assume the learner knows $\ell$ but $D$ is
unknown to her. At some point, the learner is expected to ask for a word whose
membership it needs to predict, in which case it is handed a word $w$ (drawn
randomly according to the same distribution $D$) and it should then answer
whether $w$ is or is not in $C$. We say that the class $\mathcal{C}$ is
_polynomially predictable_ with membership queries, if given a bound $s$ on
the size of the target language, the mentioned bound $\ell$ on the length of
relevant examples, and an accuracy parameter $\varepsilon$ between $0$ and
$1$, there exists a learner that will classify the word to predict correctly
with probability at least $(1-\varepsilon)$, after asking a number of queries
that is polynomial in the size of the minimal BP of the target language. We
show that under plausible cryptography assumptions fine BPs (thus BPs in
general) are not polynomially predictable.

$\textsc{h}_{1}$$\textsc{g}_{1}$$\textsc{h}_{2}$$\textsc{g}_{2}$$\circ\circ\circ$$\textsc{h}_{k}$$\textsc{g}_{k}$$\iota_{1}$$\iota_{2}$$\iota_{k}$$D_{1}$$D_{2}$$D_{k}$$q^{\prime}_{1}$$q^{\prime}_{2}$$q^{\prime\prime}_{2}$$q^{\prime}_{k}$$q^{\prime\prime}_{k}$$\bot$scx$h_{1}!!$$s??$$h_{1}??$$h_{2}!!$$s??$$h_{2}??$$h_{k-1}??$$h_{k}!!$$s??$$h_{k}??$$\$??$$\$??$$\$??$$\$??$$\bot!!\bot??$$s!!,s??$$\Sigma!!$$\$!!,\$??$$x!!$$\$??$$\$??$$\$??$$\$??$

Figure 4: A BP simulating intersection of $k$ DFAs.

######  Theorem 7.1.

Assuming the intractability of any of the following three problems: testing
quadratic residues modulo a composite, inverting RSA encryption, or factoring
Blum integers, fine BPs are not polynomially predictable with mq.

###### Proof Sketch.

The proof is via a reduction from the class $\mathcal{D}$ of intersection of
DFAs, for which Angluin and Kharitonov have shown that $\mathcal{D}$ is not
polynomially predictable under the same assumptions (Angluin and Kharitonov
1995). We show that given a predictor $\mathfrak{B}$ for fine BPs we can
construct a predictor $\mathfrak{D}$ for the intersection of DFAs as follows.
Given a set $D_{1},D_{2},\ldots,D_{k}$ of DFAs, we can construct a BP $B$ as
shown in Fig.4 such that $B$ simulates the run of the $k$ DFAs together. As in
the proof of Lem.6.1 we can send one process to simulate any of the DFAs. Here
we need $k$ processes to send a process to the initial state of each of the
DFAs, and an additional process to enable all letters in $\Sigma$. Thus, the
cutoff is $k+1$. The BP detects whether a given word $w$ is accepted by all
the DFAs by checking whether $uw\$\bot$ is infeasible in $B$ where $u$ is some
initialization sequence that is required to send the processes to the initial
states of the DFAs. ∎

##  8 Conclusion

We investigated the learnability of the class of fine broadcast protocols. To
the best of our knowledge, this is the first work on learning concurrent
models that does not assume a fixed number of processes interact. On the
positive, we showed a passive learning algorithm that can infer a BP
consistent with a given sample, and even return a minimal equivalent BP if the
sample is sufficiently complete. On the negative, we showed that the
consistency problem for fine BPs is NP-hard; characteristic sets may be
inevitably of exponential size; and the class is not polynomially predictable.

## References

  * Aarts et al. (2015) Aarts, F.; Fiterau-Brostean, P.; Kuppens, H.; and Vaandrager, F. W. 2015.  Learning Register Automata with Fresh Value Generation.  In _Theoretical Aspects of Computing - ICTAC 2015 - 12th International Colloquium Cali, Colombia, October 29-31, 2015, Proceedings_ , 165–183.
  * Angluin (1987) Angluin, D. 1987.  Learning Regular Sets from Queries and Counterexamples.  _Inf. Comput._ , 75(2): 87–106.
  * Angluin, Eisenstat, and Fisman (2015) Angluin, D.; Eisenstat, S.; and Fisman, D. 2015.  Learning Regular Languages via Alternating Automata.  In _Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015_ , 3308–3314.
  * Angluin and Kharitonov (1995) Angluin, D.; and Kharitonov, M. 1995.  When Won’t Membership Queries Help?  _J. Comput. Syst. Sci._ , 50(2): 336–355.
  * Außerlechner, Jacobs, and Khalimov (2016) Außerlechner, S.; Jacobs, S.; and Khalimov, A. 2016.  Tight Cutoffs for Guarded Protocols with Fairness.  In _VMCAI_ , volume 9583 of _Lecture Notes in Computer Science_ , 476–494. Springer.
  * Balle and Mohri (2015) Balle, B.; and Mohri, M. 2015.  Learning Weighted Automata.  In _Algebraic Informatics - 6th International Conference, CAI 2015, Stuttgart, Germany, September 1-4, 2015. Proceedings_ , 1–21.
  * Beimel et al. (2000) Beimel, A.; Bergadano, F.; Bshouty, N. H.; Kushilevitz, E.; and Varricchio, S. 2000\.  Learning functions represented as multiplicity automata.  _J. ACM_ , 47(3): 506–530.
  * Bollig et al. (2013) Bollig, B.; Habermehl, P.; Leucker, M.; and Monmege, B. 2013.  A Fresh Approach to Learning Register Automata.  In _Developments in Language Theory - 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings_ , 118–130.
  * Bollig et al. (2010) Bollig, B.; Katoen, J.; Kern, C.; and Leucker, M. 2010.  Learning Communicating Automata from MSCs.  _IEEE Trans. Software Eng._ , 36(3): 390–408.
  * de la Higuera (2010) de la Higuera, C. 2010.  _Grammatical Inference: Learning Automata and Grammars_.  Cambridge University Press.
  * Decker et al. (2014) Decker, N.; Habermehl, P.; Leucker, M.; and Thoma, D. 2014.  Learning Transparent Data Automata.  In _Application and Theory of Petri Nets and Concurrency - 35th International Conference, PETRI NETS 2014, Tunis, Tunisia, June 23-27, 2014\. Proceedings_ , 130–149.
  * Delzanno, Esparza, and Podelski (1999) Delzanno, G.; Esparza, J.; and Podelski, A. 1999.  Constraint-Based Analysis of Broadcast Protocols.  In _CSL_ , volume 1683 of _Lecture Notes in Computer Science_ , 50–66. Springer.
  * Drews and D’Antoni (2017) Drews, S.; and D’Antoni, L. 2017.  Learning Symbolic Automata.  In _Tools and Algorithms for the Construction and Analysis of Systems - 23rd International Conference, TACAS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings, Part I_ , 173–189.
  * Emerson and Kahlon (2000) Emerson, E. A.; and Kahlon, V. 2000.  Reducing Model Checking of the Many to the Few.  In _CADE_ , volume 1831 of _Lecture Notes in Computer Science_ , 236–254. Springer.
  * Emerson and Kahlon (2003) Emerson, E. A.; and Kahlon, V. 2003.  Model Checking Guarded Protocols.  In _LICS_ , 361–370. IEEE Computer Society.
  * Emerson and Namjoshi (1998) Emerson, E. A.; and Namjoshi, K. S. 1998.  On Model Checking for Non-Deterministic Infinite-State Systems.  In _LICS_ , 70–80. IEEE Computer Society.
  * Emerson and Namjoshi (2003) Emerson, E. A.; and Namjoshi, K. S. 2003.  On Reasoning About Rings.  _Int. J. Found. Comput. Sci._ , 14(4): 527–550.
  * Esparza, Finkel, and Mayr (1999) Esparza, J.; Finkel, A.; and Mayr, R. 1999.  On the Verification of Broadcast Protocols.  In _LICS_ , 352–359.
  * Esparza, Leucker, and Schlund (2011) Esparza, J.; Leucker, M.; and Schlund, M. 2011.  Learning Workflow Petri Nets.  _Fundam. Informaticae_ , 113(3-4): 205–228.
  * Finkel and Schnoebelen (2001) Finkel, A.; and Schnoebelen, P. 2001.  Well-structured transition systems everywhere!  _Theor. Comput. Sci._ , 256(1-2): 63–92.
  * Fisman, Frenkel, and Zilles (2023) Fisman, D.; Frenkel, H.; and Zilles, S. 2023.  Inferring Symbolic Automata.  _Log. Methods Comput. Sci._ , 19(2).
  * Fisman, Nitay, and Ziv-Ukelson (2023) Fisman, D.; Nitay, D.; and Ziv-Ukelson, M. 2023.  Learning of Structurally Unambiguous Probabilistic Grammars.  _Log. Methods Comput. Sci._ , 19(1).
  * Fisman and Saadon (2022) Fisman, D.; and Saadon, S. 2022.  Learning and Characterizing Fully-Ordered Lattice Automata.  In _Automated Technology for Verification and Analysis - 20th International Symposium, ATVA 2022, Virtual Event, October 25-28, 2022, Proceedings_ , 266–282.
  * Geeraerts, Raskin, and Begin (2007) Geeraerts, G.; Raskin, J.; and Begin, L. V. 2007.  Well-structured languages.  _Acta Informatica_ , 44(3-4): 249–288.
  * Gold (1967) Gold, E. M. 1967.  Language Identification in the Limit.  _Inf. Control._ , 10(5): 447–474.
  * Gold (1978) Gold, E. M. 1978.  Complexity of Automaton Identification from Given Data.  _Inf. Control._ , 37(3): 302–320.
  * Jaber et al. (2020) Jaber, N.; Jacobs, S.; Wagner, C.; Kulkarni, M.; and Samanta, R. 2020.  Parameterized Verification of Systems with Global Synchronization and Guards.  In _Computer Aided Verification - 32nd International Conference, CAV 2020, Los Angeles, CA, USA, July 21-24, 2020, Proceedings, Part I_ , 299–323.
  * Jacobs and Bloem (2014) Jacobs, S.; and Bloem, R. 2014.  Parameterized Synthesis.  _Log. Methods Comput. Sci._ , 10(1).
  * Lingg, de Oliveira Oliveira, and Wolf (2024) Lingg, J.; de Oliveira Oliveira, M.; and Wolf, P. 2024.  Learning from positive and negative examples: New proof for binary alphabets.  _Information Processing Letters_ , 183: 106427.
  * Muscholl and Walukiewicz (2022) Muscholl, A.; and Walukiewicz, I. 2022.  Active learning for sound negotiations.  In _LICS ’22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022_ , 21:1–21:12.
  * Peled, Vardi, and Yannakakis (2002) Peled, D. A.; Vardi, M. Y.; and Yannakakis, M. 2002.  Black Box Checking.  _J. Autom. Lang. Comb._ , 7(2): 225–246.
  * Roy, Fisman, and Neider (2020) Roy, R.; Fisman, D.; and Neider, D. 2020.  Learning Interpretable Models in the Property Specification Language.  In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020_ , 2213–2219.
  * Vaandrager (2017) Vaandrager, F. W. 2017.  Model learning.  _Commun. ACM_ , 60(2): 86–95.
  * Vaandrager, Bloem, and Ebrahimi (2021) Vaandrager, F. W.; Bloem, R.; and Ebrahimi, M. 2021.  Learning Mealy Machines with One Timer.  In _Language and Automata Theory and Applications - 15th International Conference, LATA 2021, Milan, Italy, March 1-5, 2021, Proceedings_ , 157–170.

Proofs Appendix

##  Appendix A Complete Proofs for Section 3

See 3.1

###### Proof of Lem.3.1.

Prefix-closedness holds since if $a_{1}a_{2}\ldots a_{n}$ is feasible, then
for every $1\leq i\leq n$ the action $a_{i}$ is feasible after reading the
prefix $a_{1}a_{2}\ldots a_{i-1}$.

For monotonicity, for two state vectors p and q we say that
$\textbf{q}\geq\textbf{p}$ if for every $i\in[|S|]$ we have that
$\textbf{q}[i]\geq\textbf{p}[i]$. Note that if $a\in A$ is enabled in p then
it is also enabled in q. Let $w=a_{1}a_{2}\ldots a_{m}$ and let
$\textbf{p}_{0},a_{1},\textbf{p}_{1},a_{2},\ldots,a_{m},\textbf{p}_{m}$ be the
execution of $B^{k}$ on $w$. We can construct an execution
$\textbf{q}_{0},a_{1},\textbf{q}_{1},a_{2},\ldots,a_{m},\textbf{q}_{m}$ of
$B^{\ell}$ by induction on the length of $w$ such that for every $i$ we have
that $\textbf{q}_{i}>\textbf{p}_{i}$ entailing $w$ is feasible in $B^{\ell}$
as well. ∎

See 3.2

###### Proof of Lem.3.2.

Suppose ${w\in L(B^{m})}$ and ${{wa}\notin L(B^{m})}$ yet ${wa}\notin
L(B^{m+1})$. I.e., neither one of the processes that take some sending
transitions when executing $w$ in $B^{m+1}$, nor one of the processes only
taking receiving transitions (including the additional process compared to
$B^{m}$) is in the state that has the sending transition on $a$. Since any
further additional process will behave in the same way as the additional
process in $B^{m+1}$, ${wa}$ can never become feasible. Contradicting that it
is feasible in $B^{n}$. ∎

See 3.3

###### Proof of Lem.3.3.

The proof is by induction on the number $m$ of interacting processes and the
length of $w$. For $m=1$ and $w=\epsilon$, we have
$\textbf{p}_{\epsilon}=\textbf{u}_{i}$ and
$\textbf{q}_{\epsilon}=\textbf{u}_{j}$ for some
$i,j{\in}\\{0,\ldots,|S|\\!-\\!1\\}$ where $n{=}|B_{1}|=|B_{2}|$. It follows
that $s_{i}$ and $s_{j}$ are the initial states of $B_{1}$ and $B_{2}$, resp.
Thus, $f^{\textsf{act}}(s_{i})=f^{\textsf{act}}(s_{j})$, as otherwise there is
an action $a$ that is enabled in $B_{1}^{1}$ and not in $B_{2}^{1}$ or vice
versa (and therefore also in any $B_{1}^{m}$ and $B_{2}^{m}$ with $m{\geq}1$),
contradicting that $L(B_{1})=L(B_{2})$. Hence we can set $h(i)=j$ and the
claim holds.

For $m=1$ and $w=ua$ for $u\in A^{*}$ and $a\in A$, by the induction
hypothesis we know that for every state $i$, $\textbf{p}_{w}[i]$ is lit if and
only if $\textbf{q}_{w}[h(i)]$ is lit. Since we have only one process all
global states are unit vectors. Thus, it must be that
$\textbf{p}_{u}=\textbf{u}_{i}$ and $\textbf{q}_{u}=\textbf{u}_{j}$ for some
$i,j\in\\{0,\ldots,|S|\\!-\\!1\\}$. That is, $i$ and $j$ are the indices of
the states in $B_{1},B_{2}$ from which $a$ is enabled, resp. Let
$i^{\prime},j^{\prime}\in\\{0,\ldots,|S|\\!-\\!1\\}$ be the indices of the
states that $B_{1},B_{2}$ reach after reading $ua$. Then
$\textbf{p}_{ua}=\textbf{u}_{i^{\prime}}$ and
$\textbf{q}_{ua}=\textbf{u}_{j^{\prime}}$. Since this is true for any action
$b$ that is feasible in $B_{1}$ or $B_{2}$ after $u$,
$h(i^{\prime})=j^{\prime}$ satisfies the claim. Note that this also shows that
any word $w$ that is feasible in $B_{1}^{1}$ is also feasible in $B_{2}^{1}$
and vice versa.

Assume the claim holds for $m$ we show it holds for $m+1$. Consider a word
$w$. Let $\textbf{p}_{w}$ and $\textbf{q}_{w}$ be the state vectors
$B_{1}^{m}$ and $B_{2}^{m}$ reach after reading $w$. Then by the induction
hypothesis, $L(B_{1}^{m})=L(B_{2}^{m})$ and for every state $i$ we have that
$\textbf{p}_{w}[i]$ is lit if and only if $\textbf{q}_{w}[h(i)]$ is lit. Let
$\textbf{p}^{\prime}_{w}$ and $\textbf{q}^{\prime}_{w}$ be the state vectors
$B_{1}^{m+1}$ and $B_{2}^{m+1}$ reach after reading $w$. Then $\textbf{p}_{w}$
and $\textbf{p}^{\prime}_{w}$ are the same for every
$i\in\\{0,\ldots,|S|\\!-\\!1\\}$ but one (and similarly for the q’s). For all
of these indices the claim holds by the induction hypothesis. Let $j$ be the
index with $\textbf{p}_{w}[j]\neq\textbf{p}^{\prime}_{w}[j]$, i.e.,
$\textbf{p}^{\prime}_{w}[j]=\textbf{p}_{w}[j]+1$. If $\textbf{p}_{w}[j]\geq
1$, then by the induction hypothesis for every state $i$ we have that
$\textbf{p}_{w}[i]$ is lit if and only if $\textbf{q}_{w}[h(i)]$ is lit. In
particular, this holds for $j$.

Otherwise, $\textbf{p}^{\prime}_{w}[j]=1$, which implies that there is at
least one action $a$ enabled from $\textbf{p}^{\prime}_{w}$ that is not
enabled from $\textbf{p}_{w}$. By induction hypothesis,
$L(B_{1}^{m})=L(B_{2}^{m})$, and therefore we know that $a$ is also not
enabled from $\textbf{q}_{w}$. Moreover, by Lemma 3.2, if $w\in L(B_{2}^{m})$,
$wa\in L(B_{2})$ and $wa\notin L(B_{2}^{m})$, then $wa\in L(B_{2}^{m+1})$.
Thus, there must be a local state $k$ enabling $a$ such that
$\textbf{q}_{w}[k]=0$ and $\textbf{q}^{\prime}_{w}[k]=1$. Hence, letting
$h(j)=k$ satisfies the claim. ∎

##  Appendix B Complete Proofs for Section 5

See 5.1

###### Proof of Lem.5.1.

The proof is by induction, first on $n$ then on the length of $w$. For $n=1$,
the construction of the tree clearly guarantees that all states reachable with
one process have a respective node in the tree.

Suppose p is reachable with $w$ in $B^{n}$ for $n>1$. By Lemma 3.2, there
exists a prefix $u$ of $w$, such that $u$ is feasible in $B^{n-1}$. By the
induction hypothesis, $u$ is a node of $\mathcal{T}_{n-1}$. Suppose
$w=ua_{1}a_{2}\ldots a_{m}$. We can show by induction on $1\leq n$ that
$ua_{1}a_{2}\ldots a_{i}$ is a node of $\mathcal{T}_{n}$ for every $i\leq m$
by simply following the tree construction. ∎

See 5.2

###### Proof of Lem.5.2.

Clearly $\sim_{\mathcal{S}}$ is symmetric and reflexive. To see that it is
transitive, we first refer to Lem. 5.1 to deduce that there exists a node $v$
in $\mathcal{T}$ in which $s$ is lit. Let $n$ be the minimal for which $v$ is
in $\mathcal{T}_{n}$. It follows that for every action $a$ that is feasible
after $v$ with $n$ processes we have $(va,n,\textsc{t})\in\mathcal{S}$ and for
every action $a$ that is infeasible after $v$ with $n$ processes we have
$(va,n,\textsc{f})\in\mathcal{S}$. Therefore, for any two actions we have
$a\,\\#_{\mathcal{S}}\,b$ iff $a$ and $b$ are not enabled from the same state,
and $a\sim_{\mathcal{S}}b$ otherwise. Assume now that $a\sim_{\mathcal{S}}b$,
$b\sim_{\mathcal{S}}c$. Then $a$ and $b$ are enabled from the same state, and
$b$ and $c$ are enabled from the same state, implying $a$ and $c$ are enabled
from the same state, i.e., $a\sim_{\mathcal{S}}c$ as required. ∎

$\textsc{i}_{1}$$\textsc{i}_{2}$1’$\textsc{h}_{1}$$\begin{array}[]{c}\circ\\\\[-5.69054pt]
\circ\\\\[-5.69054pt]
\circ\end{array}$$\textsc{h}_{\ell}$$\bot$2’$\begin{array}[]{c}\circ\\\\[-5.69054pt]
\circ\\\\[-5.69054pt]
\circ\end{array}$n-1’n’12$\begin{array}[]{c}\circ\\\\[-5.69054pt]
\circ\\\\[-5.69054pt]
\circ\end{array}$m$\top$$i_{1}!!$$i_{1}??$$i_{2}!!$$i_{2}??$$h_{1}!!$$h_{\ell-1}!!$$h_{\ell}!!$$H??$$A??,H??$$A??,H??$$A??,H??$$A??,H??$$a_{1}??$$a_{1}!!$$a_{2}??$$a_{2}!!$$a_{n^{\prime}-2}??$$a_{n^{\prime}-1}!!$$a_{n^{\prime}-1}??$$c!!$$c??$$b_{1}!!$$b_{2}!!$$b_{m}!!$$a_{\top}!!$

Figure 5:  The BP $B_{m,n,\ell}$ from a family of fine BP’s with quadratic
cutoffs.

$i_{0}$$i_{1}$$i_{2}$$i_{3}$$1^{\prime\prime}$$\begin{array}[]{c}\circ\\\\[-5.69054pt]
\circ\\\\[-5.69054pt]
\circ\end{array}$$5^{\prime\prime}$$1^{\prime}$$2^{\prime}$$3^{\prime}$$1$
$2$$d$$\top$$h_{1}^{\prime}$$h_{2}^{\prime}$$h_{1}$$h_{2}$$h_{3}$$\bot$$i_{0}??$$i_{0}!!$$i_{1}??$$i_{1}!!$$h_{1}!!$$h_{2}!!$$h_{3}!!$$H^{\prime}??$$h^{\prime}_{2}!!$$h^{\prime}_{1}!!$$i_{2}??$$i_{2}!!$$i_{3}??$$i_{3}!!$$a_{1}??$$a_{1}!!$$a_{4}??$$a_{4}!!$$\begin{array}[]{l}\\!H?\\!?\\!\\\
\\!H^{\prime}?\\!?\\!\end{array}$$\begin{array}[]{l}\\!H?\\!?\\!\\\
\\!H^{\prime}?\\!?\\!\\\
\\!A?\\!?\end{array}$$\begin{array}[]{l}\\!H?\\!?\\!\\\
\\!H^{\prime}?\\!?\\!\\\
\\!A?\\!?\end{array}$$\begin{array}[]{l}\\!H?\\!?\\!\\\
\\!H^{\prime}?\\!?\\!\\\
\\!A?\\!?\end{array}$$\begin{array}[]{l}\\!H?\\!?\\!\\\
\\!H^{\prime}?\\!?\\!\\\
\\!A?\\!?\end{array}$$\begin{array}[]{l}\\!H?\\!?\\!\\\
\\!H^{\prime}?\\!?\\!\\\
\\!A?\\!?\end{array}$$c!!$$c??$$c??$$d!!$$d??$$a_{\top}!!$

Figure 6:  The BP $P_{5}$ used to show a family of fine BPs with an
exponential cutoff.

Next we show that there exist fine BPs for which there is no characteristic
set of polynomial size. For the sake of gradual presentation before proving
Thm.5.4 we show that there exist fine BPs with cutoff of size quadratic in the
size of the BP.

######  Proposition B.1.

There exists a family of fine BPs which requires characteristic sets of
quadratic size.

###### Proof.

We adapt a family of BPs used in (Jaber et al. 2020) for showing a quadratic
cutoff for BPs without the restriction of no-hidden states, and for a slightly
different definition of cutoff (reaching a particular state). The adaptation
for no-hidden states is seamless. To work with our definition of cutoff we
needed to introduce some auxiliary states. The family is given in Fig.5.

The family is parameterized by three natural numbers $m$, $n$, and $\ell$. The
BP $B_{m,n,\ell}$ has $n$ states in the left loop (colored blue), $m$ states
in the right loop (colored blue as well), and $\ell$ helper states (colored
red), and 4 additional states; overall $n+m+\ell+4$ states. The states
$\textsc{i}_{1}$ and $\textsc{i}_{2}$ send one process to the right loop, one
process to state $\textsc{h}_{1}$, and the rest of the processes to state 1’.
The state $\top$ is used for identifying that at the same moment both states m
and n’ are lit together.

We use $H??$ and $A??$ as a shortcuts for $\\{h_{i}??~{}|~{}i\in[1..\ell]\\}$
and $\\{a_{i}??~{}|~{}i\in[1..n^{\prime}\\!-\\!1]\\}$, respectively. From all
of the states except for m we assume $c??$ takes to the $\bot$ state, and
$a_{\top}??$ takes all of the states to the $\top$ state (we didn’t add these
transitions to avoid clutter). Actions in $\\{b_{j}\colon j\in[1..m]\\}$ are
added to satisfy the no hidden states assumption, where $b_{j}!!$ is a self-
loop on state j (colored gray), and $b_{j}??$ is a self loop for any state
(not shown). One can see that traversing the left blue loop requires at least
$n$ processes: one process for each of the $a_{i}$ transitions, for $1\leq
i\leq n-1$, and one process for the $H$ transition. Each $H$ transition
requires one of the $h_{i}$ transitions to be taken. The structure of the
$h_{i}$ sending transitions thus restrict the number of times n’ can be
reached to $\ell+1$ (since it can be reached once without executing an
$h_{i}$). In order to enable $a_{\top}$ there must be one process in state n’
that sends $c!!$ and one process in state m responding to it. Therefore if $n$
and $m$ are co-prime, this can occur only once the left loop is traversed $m$
times (which requires $m$ helper states). Thus an overall of $n\cdot m$
processes are required to make a word using action $a_{\top}$ feasible.
Accordingly, the shortest word using the $a_{\top}$ action is of length at
least $n\cdot m$. This shows that there exist no characteristic sets for this
family of size less than quadratic in the size of the given BP. ∎

To obtain an exponential size lower bound, instead of having two such loops,
we have $k$ such loops of sizes $p_{1},p_{2},\ldots,p_{k}$, where $p_{i}$ is
the $i$-th prime number, as explained in the proof of Thm.5.4.

See 5.4

###### Proof of Thm.5.4.

With every $n\in\mathbb{N}$ we associate a BP $P_{n}$ that has a loop for
every prime smaller or equal to $n$. Denote these primes
$p_{1}\\!<\\!p_{2}\\!<\\!\ldots\\!<\\!p_{k}\\!\leq\\!n$. Let
$m\\!=\\!p_{1}\\!\cdot\\!p_{2}\cdots p_{k}$ be the multiplication of all these
primes. There is a special action $a_{\top}$ detecting synchronization among
these loops, that is enabled from a state $\top$ that can be reached only once
there is a process at the end of each of these $k$ loops.

Roughly speaking, the synchronization of the traversal around the different
loops is controlled by the biggest loop (which sends $a_{i}!!$ actions), and
the rest of the loops responding (following $a_{i}??$). To enforce a cutoff
exists, there are additional helper states that limit the number of times
biggest loop the ($p_{k}$) can be traversed to $m/p_{k}$ times, which is the
minimum we need to reach $\top$. This is done by requiring an helper
transition to traverse the transition closing the $p_{k}$ loop.

In order to avoid adding $m/p_{k}$ such helper states, we suffice with
$p_{1},p_{2},\ldots,p_{k-1}$ helper states that also synchronize to count to
$m/p_{k}$. The BP for $n=5$ is given in Fig. 6. As before, $A??$, $H??$ and
$H^{\prime}??$ are abbreviations for all $a_{i}$, $h_{i}$ and $h^{\prime}_{i}$
actions. You can see the loops corresponding to $p_{1}=2$, $p_{2}=3$,
$p_{3}=5$ painted in blue. The helper states are painted red. There are
additional auxiliary states $i_{0},i_{1},\ldots,i_{2(k-1)-1}$ (up to $i_{3}$
for $n=5$ for which $k=3$) enabling an initialization sequence
$u_{0}=i_{0}i_{1}\cdots i_{2(k-1)-1}$ that is used to send one process to each
of the $k-1$ smaller blue loops i.e. the loops of $p_{1},\ldots,p_{k-1}$ and
one to each of the red loops/sequences. All additional processes reach the
beginning of the biggest loop $p_{k}$ (for the example in Fig.6, it is state
$\textsc{1}^{\prime\prime}$). Auxiliary actions added to meet the no hidden
states assumption are not shown.

The sequence enabling $a_{\top}$ will take the following form. Let
$u=a_{1}a_{2}\cdots a_{p_{k}-1}$ and $v=uh_{1}uh_{2}u\cdots uh_{p_{k-1}-1}u$.
Then the desired sequence is $w=vh^{\prime}_{1}vh^{\prime}_{2}v\cdots
h^{\prime}_{p_{1}}vh_{p_{2}}u$. After this sequence, all final states of the
loops will be lit at the same time. Then, we can create a termination sequence
$u_{t}$ ensuring there is a moment in which there is a process in the end of
each of the $k$ loops. In the example of $P_{5}$ if the states 2,
$\textsc{3}^{\prime}$, $\textsc{5}^{\prime\prime}$ are all lit at the same
time, then the sequence $cd$ will enable $a_{\top}$. In the general case if we
have $k$ primes, the termination sequence would be of length $k-1$. Hence the
sequence $u_{0}wu_{t}a_{\top}$ is feasible.

Note that the size of BP $P_{n}$ is quadratic in $n$. Since all primes are of
size $2$ at least, and since the number of primes of size $n$ or less is
$\Theta(n/\log n)$ the number of processes required to enable $a_{\top}$ is at
least $2^{\Theta(n/\log n)}$, and so is the size of a shortest word
($u_{0}wu_{t}a_{\top}$) that includes the $a_{\top}$ action. Hence, a word of
length exponential in the size of the BP is required to be in the sample,
entailing this family has no characteristic set of polynomial size. ∎

##  Appendix C Complete Proofs for Section 6

See 6.1

###### Proof of Lem.6.1.

We start with the first item. Let $D=(\Sigma,Q,\iota,\delta,F)$ be a minimal
DFA for $L$. We build the BP $B=(A,S,s,R)$ as follows, see Fig. 3. The states
are $S=Q\cup\\{\textsc{i},\textsc{c},\textsc{x},\top,\bot\\}$, the initial
state is $s\\!=\\!\textsc{i}$. The actions $A\\!=\Sigma\cup
Q\cup\\{i,\$,\bot,\top,x\\}$. The transitions are as follows:
$(\textsc{i},i!!,{\iota})$, and $(\textsc{i},i??,\textsc{c})$. For every
$\sigma\in\Sigma$: $(\textsc{c},\sigma!!,\textsc{c})$ and
$(\textsc{c},\$!!,\textsc{x}),(\textsc{c},\$??,\textsc{x})$. For every
$(q,\sigma,q^{\prime})\in\delta$ : $(q,\sigma??,{q^{\prime}})$. For every
$q\in Q\setminus F$: $(q,\$??,\bot)$ and for every $q\in F$: $(q,\$??,\top)$.
Finally, $(\textsc{x},x!!,\textsc{x}),(\textsc{x},x??,\textsc{x})$,
$(\textsc{x},\top??,\top),(\textsc{x},\bot??,\bot)$, $(\top,\top!!,\top)$ and
$(\bot,\bot!!,\bot)$. To adhere to the no-hidden states requirement we can add
$(q,q!!,q)$ for all $q\in Q$ and every response that isn’t defined is a self
loop.

First we note that with one process the set of $A$-feasible words is $i$. With
two processes, after executing $i$ we have one process in $\iota$ and one in
c. The process in state c can execute any word over $\Sigma$ and the other
process would have to simulate the DFA on this word. After $\$$ is fired a
sequence of $x$’s is feasible followed by either a sequence of $\top$’s or a
sequence of $\bot$’s, depending whether the DFA has reached an accepting state
or not. Note that with three or more processes the same set of words is
feasible, therefore the cutoff is $2$ and $B$ is fine. It follows that $w\in
L$ if and only if $(iw\$\top,2)$ is feasible in $B$ and similarly $w\notin L$
if and only if $(iw\$\bot,2)$ is feasible in $B$. This proves the first two
items.

For the third item, we first claim that the requirement of the $A$-feasible
words require at least $5$ states. Indeed, since with one process only $i$ is
$A$-feasible, the only action feasible from the initial state, call it i is
$i$. Since $ii$ is infeasible, $i!!$ from the initial state must reach a new
state, and since no other $A$-feasible words are feasible with one process,
this state has no $A$-feasible actions. With two processes, after $i$ we can
also fire all actions in $\Sigma\cup\\{\$\\}$, and so $i??$ from the initial
state must reach a state that enables all of them, call it c. Afterwards, once
a $\$$ has been fired neither $i$ nor $\Sigma$ or $\$$ are feasible, but only
$x$ and either $\top$ or $\bot$. So $\$!!$ as well as $\$??$, must have
reached new states that enables these. Due to the fact that after $x$ nothing
but $\top$ or $\bot$ is feasible, we get that $x$ is fired from a different
state. Finally, since after $\top$ only $\top$’s are feasible, and similarly
after $\bot$, these actions have to be enabled from different states as well,
call them $\top$ and $\bot$. So there are at least $5$ states, and they
possess transitions as shown in Fig. 3.

Now, assume towards contradiction that the minimal DFA for $L$ has $n$ states,
and there is a BP $B$ satisfying these requirements with less than $n+5$
states. We claim that if $B$ has less than $n+5$ states then we can build a
DFA for $L$ with less than $n$ states. First note that as argued earlier,
after firing $i$ there exists a process in a state, call it $\iota$, from
which none of the actions in $A$ can be fired. Moreover, if there is more than
one process, then the rest of processes after executing $i$ are in a different
state, the one we called c. Assuming first, the responses on actions in
$\Sigma$ do not reach one of the identified 5 states, it is clear that they
must simulate the transitions of the DFA, as otherwise we would get a
contradiction to the minimality of the DFA. Removing this assumption, we note
that out of the five states, responses on $\Sigma$ actions can only get to c
as otherwise the set of $A$-feasible words will not be a prefix of
$i(\Sigma)^{*}\$x^{*}(\top^{*}\cup\bot^{*})$ as required. Assuming that this
happens for some $\sigma\in\Sigma$, then at that point all the processes will
be in c, which means that after taking $\$$ neither $\bot$ nor $\top$ is
feasible, contradicting requirement (2). This concludes that the responses on
actions in $\Sigma$ do behave the same as in the minimal DFA. Regarding the
actions in $A^{\prime}\setminus A$, we can assume that sending and receiving
transitions on every $a\in A^{\prime}\setminus A$ behave such that, when
starting from a configuration where only states c and $f^{\textsf{st}}(a)$ are
lit, then also after $a$ the same states are lit.888This means that either the
transitions on $a$ are all self-loops, or the response from c goes to
$f^{\textsf{st}}(a)$, and at least one of the sending and receiving
transitions on $a$ from $f^{\textsf{st}}(a)$ goes to c (and is a self-loop
otherwise). Otherwise we would get a contradiction either to requirement (2)
or to minimality of the DFA:

  * •

First, note that if c is not lit after $a$, then requirement (2) cannot be
satisfied.

  * •

If a transition on $a$ from $f^{\textsf{st}}(a)$ or c goes to an auxiliary
state other than c, then we also get a contradiction to requirement (2).

  * •

If a transition on $a$ from $f^{\textsf{st}}(a)$ goes to a non-auxiliary state
other than $f^{\textsf{st}}(a)$, then we get a contradiction to minimality of
the DFA, since then from this state exactly the same words in $\Sigma^{*}$
would be accepted as from $f^{\textsf{st}}(a)$.

This concludes the proof. ∎

See 6.2

###### Proof of 6.2.

The proof is by reduction from DFA-consistency which was shown to be NP-hard
in (Gold 1978), using the idea in Lem.6.1. Given an input to DFA-consistency,
namely a sample $\mathcal{S}$ and a number $k$, we produce a sample
$\mathcal{S}^{\prime}$ and $k^{\prime}=k+5$ as an input to BP-consistency as
follows.

We start by putting the triples $(i,1,\textsc{t})$, $(ii,2,\textsc{f})$,
$(ix,2,\textsc{f})$, $(i\top,2,\textsc{f})$, $(i\bot,2,\textsc{f})$. Then for
all ${\sigma\in\Sigma}$ we add $(i\sigma i,2,\textsc{f}),$ $(i\sigma
x,2,\textsc{f}),$ $(i\sigma\$xi,2,\textsc{f})$ to $\mathcal{S}^{\prime}$.
Then, for each $(w,\textsc{t})\in\mathcal{S}$ we add $(iw\$\top\top,2)$ and
$(iw\$xx\top\top,2)$ with positive label to $\mathcal{S^{\prime}}$, and the
following words with negative label to $\mathcal{S^{\prime}}$:
$(iw\$\top\bot,2)$, $(iw\$\bot\top,2)$, $(iw\top,2)$, $(iw\$\bot,2)$,
$(iw\$\top i,2)$, $(iw\$\top x,2)$, and $(iw\$\top\sigma,2)$, $(iw\$\sigma,2)$
for any $\sigma\in\Sigma$.

For each $(w,\textsc{f})\in\mathcal{S}$ we add $(iw\$\bot\bot,2,)$ and
$(iw\$xx\bot\bot,2)$ with positive label to $\mathcal{S^{\prime}}$, and the
following words with negative label to $\mathcal{S^{\prime}}$:
$(iw\$\top\bot,2)$, $(iw\$\bot\top,2)$, $(iw\bot,2)$, $(iw\$\top,2)$,
$(iw\$\bot x,2)$, and $(iw\$\bot\sigma,2)$, $(iw\$\sigma,2)$ for any
$\sigma\in\Sigma$.

From similar arguments as the proof for the third item in Thm. 6.1 we can show
that the reduction is valid, namely there is a DFA for the given sample
$\mathcal{S}$ with less than $k$ sates if and only if there is a BP for the
constructed sample $\mathcal{S}^{\prime}$ with less than $k+5$ states. ∎

### Alternative proof that BP consistency is NP hard

Below we provide a direct proof by reduction from the problem of _all-eq-3SAT_
that is inspired by a recent proof on the hardness of DFA consistency (Lingg,
de Oliveira Oliveira, and Wolf 2024).

$q_{1}$$q_{c}$$q_{2}$$\circ\circ\circ$$q_{m}$$p_{1}$$p_{2}$$p_{3}$$\circ\circ\circ$$p_{n}$$q_{a}$$q_{T}$$q_{F}$$a_{1}!!$$a_{2}!!$$a_{m-1}!!$$a_{m}!!$$a_{m+1}!!$$a_{m+2}!!$$a_{m+3}!!$$a_{m+n-1}!!$$a_{m+n}!!$$b!!$$d!!$$e!!$$c!!$$a!!$$b??$$b??$$c??$$c??$$c??$$c??$

Figure 7: A BP consistent with $\varphi=C_{1}\wedge C_{2}\wedge\ldots\wedge
C_{m}$ where $C_{1}=(x_{1}\vee x_{2}\vee x_{5})$,
$C_{2}=(\overline{x_{2}}\vee\overline{x_{3}}\vee\overline{x_{7}})$ and the
satisfying assignment
$x_{1}=\textsc{t},x_{2}=\textsc{f},x_{3}=\textsc{f},\ldots,x_{n}=\textsc{t}$.
Responses that are not shown are self-loops.

See 6.2

###### Proof.

The problem of _all-eq-3SAT_ asks given an all-eq-3CNF formula $\varphi$
whether it has a satisfying assignment. Where an all-eq-3CNF formula is a 3CNF
formula where in each clause either all literals are positive or all literals
are negative. This problem is known to be NP-complete.

Let $\varphi=C_{1}\wedge C_{2}\wedge\ldots\wedge C_{m}$ be an all-eq-3CNF
formula over a set of variables $V=\\{x_{1},x_{2},\ldots,x_{n}\\}$. We take
the number $k$ to be $n+m+4$. For the alphabet of the sample we take
$A=\\{a_{i}~{}|~{}1\leq i\leq m+n\\}\cup\\{a,b,c,t,\\!f\\}$. We devise a
sample $\mathcal{S}$ using four disjoint sets of words: $P_{1}$, $P_{2}$,
$N_{1}$, $N_{2}$. The sample then consists of the triples
$\\{(w,1,\textsc{t})~{}|~{}w\in P_{1}\\}\cup\\{(w,2,\textsc{t})~{}|~{}w\in
P_{2}\\}\cup\\{(w,1,\textsc{f})~{}|~{}w\in
N_{1}\\}\cup\\{(w,2,\textsc{f})~{}|~{}w\in N_{2}\\}$. The sets are defined as
follows:

$\begin{array}[]{l@{\,}l}P_{1}\,=&\\{a_{1}a_{2}\ldots
a_{m+n}aa\\}\cup\\{bcc\\}\\\ P_{2}\,=&\\{a_{1}a_{2}\ldots
a_{i}bctt~{}|~{}1\leq i\leq m,\ \ C_{i}\text{ is positive}\\}\ \cup\\\
&\\{a_{1}a_{2}\ldots a_{i}bc\\!f\\!f~{}|~{}1\leq i\leq m,\ \ C_{i}\text{ is
negative}\\}\\\ N_{1}\,=&\\{a_{1}a_{2}\ldots a_{i}a_{j}~{}|~{}1\leq i<m+n,\
j\neq{i+1}\\}\ \cup\\\ &\\{a,ba,bb,c,t,\\!f,bca,bct,bc\\!f\\}\\\
N_{2}\,=&\\{a_{1}\ldots a_{i}ba_{j}a_{j+1}\ldots a_{m+n}~{}|~{}i\leq j\leq
m\\}\ \cup\\\ &\\{a_{1}\ldots a_{i}ba_{j+1}\ldots a_{m+n}~{}|~{}i\leq
m,j>m,x_{j}\notin C_{i}\\}\ \cup\\\ &\\{a_{1}a_{2}\ldots
a_{i}bct\\!f~{}|~{}1\leq i\leq m\\}\ \cup\\\ &\\{a_{1}a_{2}\ldots
a_{i}bc\\!ft~{}|~{}1\leq i\leq m\\}\ \cup\\\ &\\{a_{1}a_{2}\ldots
a_{i}x~{}|~{}0<i\leq m+n,\ x\in\\{c,t,\\!f\\}\\}\ \cup\\\ &\\{a_{1}a_{2}\ldots
a_{i}a~{}|~{}0<i<m+n\\}\ \cup\\\ &\\{a_{1}\ldots a_{i}ba_{j+1}\ldots
a_{k}a~{}|~{}i\leq m,\ j\geq m,\ k<m+n\\}\\\ \end{array}$

Suppose there is a satisfying assignment for $\varphi$. We can construct a BP
with $k$ states consistent with the sample as shown in Fig. 7. The states
$q_{1},q_{2},\ldots,q_{m}$ correspond to the clauses, the states
$p_{1},p_{2},\ldots,p_{n}$ correspond to the variables, the states $q_{T}$ and
$q_{F}$ correspond to truth assignments t and f, and there are two additional
states $q_{c}$ and $q_{a}$. The initial state $q_{1}$ has transition with
$b!!$ to $q_{c}$ which has a self transition on $c!!$. State $q_{a}$ has a
self-loop on $a!!$.

All states $p_{j}$ corresponding to variables $x_{j}$ with a t (resp. f)
assignment have a $c??$ response to state $q_{T}$ (resp. $q_{F}$). For $1\leq
i\leq m$, state $q_{i}$ corresponds to clause $C_{i}$ and to the word
$a_{1}\ldots a_{i-1}$ (for $i=1$ the corresponding word is the empty word).
From each state $q_{i}$ we add a $b??$ transition to a state $p_{j}$
corresponding to a satisfying literal in the clause of $C_{i}$. This makes the
words $a_{1}a_{2}\ldots a_{i}bctt$ (resp. $a_{1}a_{2}\ldots a_{i}bc\\!f\\!f$)
feasible in $B^{2}$ for every positive (resp. negative) clause $C_{i}$ for
which $x_{j}\in C_{i}$ and $x_{j}$’s assignment is t (resp. f) conditioned a
corresponding $b??$ transition from $C_{i}$ to $x_{j}$ exists. It can be
verified that this BP agrees with the sample.

Next, we show that if $\varphi$ has no satisfying assignment then any BP with
$k$ states or less, disagrees with the sample. We show that the sample implies
there are at least $k$ states, associated with actions as shown in Fig.7.
Then, similar arguments regarding satisfaction of the clauses, imply that if
no satisfying assignment exists, then any BP with these states would disagree
with the sample.

To see that such $k$ states are required, we note that for every BP consistent
with $P_{1}$, if for some $\sigma\in A$ there is a word in $P_{1}$ with
$\sigma\sigma$ as an infix, there must be a state with self-loop on $\sigma$,
since there is only one processes in the system. Another thing to note is that
if a word is feasible with $n$ processes then it is also feasible with any
$m\geq n$ processes. In the other direction, if a word is infeasible with $n$
processes then it is also infeasible with any $m\leq n$ processes (see
Lem.3.1). Moreover, if $w$ is feasible then any prefix of it is feasible.

The first set in $N_{1}$ prescribes that in any consistent BP, with a single
process, the action $a_{i}$ may only be followed by $a_{i+1}$. And due to
$N_{1}$, with respect to $P_{1}$ this guarantees that any BP consistent with
$\mathcal{S}$ has at least $m\\!+\\!n$ states, one for each of the $a_{i}$
actions. Since $bcc$ is feasible yet $a_{1}a_{2}\ldots a_{i}c$ is infeasible
for any $i\in[1,...,m\\!+\\!n]$ (see $N_{2}$, line 5), it follows that $b!!$
reaches a state where $c$ is enabled from and this state is different from any
of the states $a_{i}$’s are feasible from. Hence, another state for the $c$ is
needed. Similar arguments taking that $a_{1}a_{2}\ldots a_{m_{n}}a$ is in
$P_{1}$ yet $a_{1}a_{2}\ldots a_{i}a$ is in $N_{2}$ for
$i\in[1,...,m\\!+\\!n\\!-\\!1]$ (see line 6) show that another state for $a$
is required. Since $bcc$ is feasible (in $P_{1}$) while $bca$ is not (in
$N_{1}$) the $a$ and $c$ action must be from different states. Hence so far we
have identified $n\\!+\\!m\\!+\\!2$ states. Two more states are required for
actions $t$ and $\\!f$ since either $a_{1}a_{2}\ldots a_{i}bctt$ or
$a_{1}a_{2}\ldots a_{i}bc\\!f\\!f$ in $P_{2}$ depending whether the clause
$C_{i}$ is positive or negative, hence $tt$ or $\\!f\\!f$ is always feasible
after $a_{1}a_{2}\ldots a_{i}bc$, while $a_{1}a_{2}\ldots a_{i}bct\\!f$ and
$a_{1}a_{2}\ldots a_{i}bc\\!ft$ are in $N_{2}$ thus $t$ and $\\!f$ cannot be
from the same state. Similar arguments show that these actions cannot be from
the states the previous actions are. Thus $m\\!+\\!n\\!+\\!4$ states are
required. With this structure, from similar arguments to the first direction,
if the BP would agree with all the words in the sample, it would contradict
that $\varphi$ is not satisfiable. ∎

##  Appendix D Complete Proofs for Section 7

See 7.1

###### Proof of Thm.7.1.

The proof is via a reduction from the class $\mathcal{D}$ of intersection of
DFAs, for which Angluin and Kharitonov (1995) have shown that $\mathcal{D}$ is
not polynomially predictable under the same assumptions.

We show that given a predictor $\mathfrak{B}$ for fine BPs we can construct a
predictor $\mathfrak{D}$ for the intersection of DFAs as follows. First, we
show how to associate with any given set $D_{1},D_{2},\ldots,D_{k}$ of DFAs a
particular BP $B$. Let $D_{i}=(\Sigma,Q_{i},\iota_{i},\delta_{i},F_{i})$ and
assume without loss of generality that the states of the DFAs are disjoint and
the DFAs are complete (i.e. from every state there is an outgoing transition
on every letter in $\Sigma$). We construct a fine BP $B=(A,S,s,R)$ with cutoff
$k+1$ as follows. See illustration in Fig.4.

Let $Q=\cup_{i\in[1..k]}\,Q_{i}$. The set of states $S$ is
$Q\cup\\{\bot,\textsc{s},\textsc{c},\textsc{x}\\}\cup\\{\textsc{g}_{i},\textsc{h}_{i}~{}|~{}i\in[1..k]\\}$.
The initial state is $\textsc{h}_{1}$. Let
$\Sigma_{h}=\\{h_{j}~{}|~{}j\in[1..k]\\}$ and
$\Sigma_{g}=\\{g_{j}~{}|~{}j\in[1..k]\\}$ . The set of actions $A$ is $\Sigma\
\cup\ \Sigma_{h}\ \cup\Sigma_{g}\cup\ \\{\$,\bot,x,s\\}$.

The transitions are as follows: for every ${i\in[1..k]}$ we have
$(\textsc{h}_{i},h_{i}!!,\textsc{g}_{i})$. The receiving transitions on
$h_{i}$ are $(\textsc{h}_{i},h_{i}??,\textsc{h}_{i+1})$ for every
$i\in[1..k\\!-\\!1]$, and $(\textsc{h}_{k},h_{k}??,\textsc{s})$. For state s,
the transitions are as follows: $(\textsc{s},s!!,\textsc{c})$,
$(\textsc{s},s??,\textsc{c})$. For every $\sigma\in\Sigma$ we have
$(\textsc{c},\sigma!!,\textsc{c})$. The transitions from the
$\textsc{g}_{i}$’s states are $(\textsc{g}_{i},s??,\iota_{i})$ for every
$i\in[1..k]$. For every $(q,\sigma,q^{\prime})\in\delta_{i}$ for
$q,q^{\prime}\in Q_{i}$ we have $(q,\sigma??,q^{\prime})$. For the $\bot$
state we have $({\bot},\bot!!,{\textsc{x}})$, $({\bot},\bot??,{\textsc{x}})$
and $(\textsc{x},x!!,{\textsc{x}})$. Finally, for every $i\in[1..k]$ and $q\in
Q_{i}$ we have $(q,$$??$,\textsc{x})$ if $q\in F_{i}$ and $(q,$$??$,\bot)$
otherwise. Response transitions that are not specified are self-loops.

To satisfy the requirement of no-hidden states, we can assume that the
$\textsc{g}_{i}$ states have a self loop on $g_{i}!!$, and every state $q$ of
one of the DFAs has a self loop on $q!!$ (not shown in the figure to avoid
clutter). The set of actions used would be $A\cup Q$. Note that this structure
enforces the prefix to be of the form $h_{1}u_{1}h_{2}u_{2}\ldots h_{k}u_{k}$
where $u_{i}\in\\{g_{1},g_{2},\ldots,g_{i}\\}^{*}$ and $k$ processes are
required to enable $h_{k}$. In order to enable $s$ an additional process is
required. At this point any word $v$ from $\Sigma^{*}$ is feasible, and there
will be exactly one process in the initial state of each of the DFAs,
simulating its run on $v$. Upon the letter $\$$ only $\bot$ or $x$ are
feasible. Moreover, if there exists a DFA that rejects the word then $\bot$ is
feasible, otherwise, no $\bot$ is feasible, only $x$.

Next we show how the predictor $\mathfrak{D}$ for the intersection of DFAs
uses the predictor $\mathfrak{B}$ for BPs to satisfy his task. Note that
$\mathfrak{D}$ has an oracle for the intersection of the DFAs
$D_{1},\ldots,D_{k}$ at his disposal, whereas $\mathfrak{B}$ expects answers
regarding $B$. When $\mathfrak{B}$ asks a mq about $(w,n)$, i.e. whether $w$
is feasible in $B^{n}$ then $\mathfrak{D}$ behaves as follows.

Let $w^{\prime}$ be the word obtained from $w$ by removing letters that are
not in $A$. If $w^{\prime}$ is not a prefix of $h_{1}u_{1}h_{2}u_{2}\ldots
u_{k-1}h_{k}u_{k}s\Sigma^{*}\$\\{\bot,x\\}^{*}$ where
$u_{i}\in\\{g_{1},g_{2},\ldots,g_{i}\\}^{*}$, or the number of $\bot$ letters
exceeds one, then $\mathfrak{D}$ returns the answer “no” to $\mathfrak{B}$.
Else, if $w$ is such a prefix and $w$ does not contain $\bot$, $\$$ or $x$,
then $\mathfrak{D}$ returns to $\mathfrak{B}$ the answer “yes” iff $n>k$ or
$w^{\prime}$ is a prefix of $h_{1}u_{1}h_{2}u_{2}\ldots u_{n-1}h_{n}u_{n}$
where the $u_{i}$’s are as above. Otherwise, $w$ is such a prefix that
contains $\$$. If $n\leq k$ we return “no”. Otherwise, let $v$ be the maximal
infix of $w^{\prime}$ that is in $\Sigma^{*}$. The predictor $\mathfrak{D}$
asks a MQ about $v$. Assume it receives the answer $b$. If $w$ has $\bot$, it
answers “yes” iff $b$ is “no”. Otherwise it answers “yes”.

We claim that $\mathfrak{B}$ receives correct answers. Indeed, the first
couple of checks verify that $w$ is feasible according to the construction
that builds $B$ from the given DFAs. For the last check, first note that if
$w$ does not contain $\bot$ then $w$ is feasible. Otherwise, if $w$ does
contain $\bot$ then it is infeasible if $v$ is accepted by all the DFAs and is
feasible if at least one DFA rejects it.

The next ingredient is to show how draw queries of $\mathfrak{B}$ are
simulated by $\mathfrak{D}$. When $\mathfrak{B}$ makes a dr query, then
$\mathfrak{D}$ makes a dr query. Suppose it receives the answer $(v,b)$. Then
it passes $((h_{1}h_{2}\ldots h_{k}sv\$\bot,k+1),\neg b)$ to $\mathfrak{B}$.
Last, when $\mathfrak{B}$ asks for a word $w$ to predict, then $\mathfrak{D}$
asks for a word $v$ to predict and flips the answer of the prediction of
$\mathfrak{B}$ on $(h_{1}h_{2}\ldots h_{k}sv\$\bot,k+1)$. Note that if $v$ is
accepted by the intersection of the DFAs, and $w=h_{1}h_{2}\ldots
h_{k}sv\$\bot$ then $w$ is infeasible, and if $v$ is rejected then $w$ is
feasible. It follows that given $\mathfrak{B}$ classifies the predicted word
correctly then so does $\mathfrak{D}$. Therefore, if $\mathfrak{B}$ is a
polynomial predictor for fine BPs then $\mathfrak{D}$ is a polynomial
predictor for the intersection of DFAs. ∎