Daniel J. Fremont, Alexandre Donzé, Sanjit A. Seshia, and David Wessel

# Control Improvisation

Daniel J. Fremont  University of California, Berkeley  Alexandre Donzé
University of California, Berkeley  Sanjit A. Seshia  University of
California, Berkeley  David Wessel  University of California, Berkeley

###### Abstract.

We formalize and analyze a new automata-theoretic problem termed control
improvisation. Given an automaton, the problem is to produce an _improviser_ ,
a probabilistic algorithm that randomly generates words in its language,
subject to two additional constraints: the satisfaction of an _admissibility_
predicate, and the exhibition of a specified amount of randomness. Control
improvisation has multiple applications, including, for example, generating
musical improvisations that satisfy rhythmic and melodic constraints, where
admissibility is determined by some bounded divergence from a reference
melody. We analyze the complexity of the control improvisation problem, giving
cases where it is efficiently solvable and cases where it is
$\mathsf{\\#P}$-hard or undecidable. We also show how symbolic techniques
based on Boolean satisfiability (SAT) solvers can be used to approximately
solve some of the intractable cases.

###### Key words and phrases:

finite automata, random sampling, Boolean satisfiability, testing,
computational music, control theory

###### 1991 Mathematics Subject Classification:

F.4.3 Formal Languages, G.3 Probability and Statistics, F.2.2 Nonnumerical
Algorithms and Problems

##  1\. Introduction

We introduce and formally characterize a new automata-theoretic problem termed
control improvisation. Given an automaton, the problem is to produce an
_improviser_ , a probabilistic algorithm that randomly generates words in the
language of the automaton, subject to two additional constraints: each
generated word must satisfy an _admissibility_ predicate, and the improviser
must exhibit a specified amount of randomness.

The original motivation for this problem arose from a topic known as machine
improvisation of music [19]. Here, the goal is to create algorithms which can
generate variations of a reference melody like those commonly improvised by
human performers, for example in jazz. Such an algorithm should have three key
properties. First, the melodies it generates should conform to rhythmic and
melodic constraints typifying the music style (e.g. in jazz, the melodies
should follow the harmonic conventions of that genre). Second, the algorithm
should be sufficiently randomized that running it several times produces a
variety of different improvisations. Finally, the generated melodies should be
actual variations on the reference melody, neither reproducing it exactly nor
being so different as to be unrecognizable. In previous work [11], we
identified these properties in an initial definition of the control
improvisation problem, and applied it to the generation of monophonic (solo)
melodies over a given jazz song harmonization111Examples of improvised
melodies can be found at the following URL:
http://www.eecs.berkeley.edu/~donze/impro_page.html..

These three properties of a generation algorithm are not specific to music.
Consider _black-box fuzz testing_ [20], which produces many inputs to a
program hoping to trigger a bug. Often, constraints are imposed on the
generated inputs, e.g. in _generative_ fuzz testing approaches which enforce
an appropriate format so that the input is not rejected immediately by a
parser. Also common are _mutational_ approaches which guide the generation
process with a set of real-world seed inputs, generating only inputs which are
variations of those in the set. And of course, fuzzers use randomness to
ensure that a variety of inputs are tried. Thus we see that the inputs
generated in fuzz testing have the same general requirements as music
improvisations: satisfying a set of constraints, being appropriately
similar/dissimilar to a reference, and being sufficiently diverse.

We propose control improvisation as a precisely-defined theoretical problem
capturing these requirements, which are common not just to the two examples
above but to many other generation problems. Potential applications also
include home automation mimicking typical occupant behavior (e.g., randomized
lighting control obeying time-of-day constraints and limits on energy usage
[16]) and randomized variants of the supervisory control problem [5], where a
controller keeps the behavior of a system within a safe operating region (the
language of an automaton) while adding diversity to its behavior via
randomness. A typical example of the latter is surveillance: the path of a
patrolling robot should satisfy various constraints (e.g. not running into
obstacles) and be similar to a predefined route, but incorporate some
randomness so that its location is not too predictable [15].

Our focus, in this paper, is on the theoretical characterization of control
improvisation. Specifically, we give a precise theoretical definition and a
rigorous characterization of the complexity of the control improvisation
problem under various conditions on the inputs to the problem. While the
problem is distinct from any other we have encountered in the literature, our
methods are closely connected to prior work on random sampling from the
languages of automata and grammars [13, 10, 14], and sampling from the
satisfying assignments of a Boolean formula [7]. Probabilistic programming
techniques [12] could be used for sampling under constraints, but the present
methods cannot be used to construct improvisers meeting our definition.

In summary, this paper makes the following novel contributions:

  * •

Formal definitions of the notions of control improvisation (CI) and a
polynomial-time improvisation scheme (Sec. 2);

  * •

A theoretical characterization of the conditions under which improvisers exist
(Sec. 3);

  * •

A polynomial-time improvisation scheme for a practical class of CI instances,
involving finite-memory admissibility predicates (Sec. 4);

  * •

$\mathsf{\\#P}$-hardness and undecidability results for more general classes
of the problem (Sec. 5);

  * •

A symbolic approach based on Boolean satisfiability (SAT) solving that is
useful in the case when the automata are finite-state but too large to
represent explicitly (Sec. 6).

We conclude in Sec. 7 with a synopsis of results and directions for future
work. For lack of space, we include only selected proofs and proof sketches in
the main body of the paper; complete details may be found in the Appendix.

##  2\. Background and Problem Definition

In this section, we first provide some background on a previous automata-
theoretic method for music improvisation based on a data structure called the
factor oracle. We then provide a formal definition of the control
improvisation problem while explaining the choices made in this definition.

###  2.1. Factor Oracles

An effective and practical approach to machine improvisation of music (used
for example in the prominent OMax system [1]) is based on a data structure
called the factor oracle [2, 8]. Given a word $w_{\text{ref}}$ of length $N$
that is a symbolic encoding of a reference melody, a factor oracle $F$ is an
automaton constructed from $w_{\text{ref}}$ with the following key properties:
$F$ has $N+1$ states, all accepting, chained linearly with direct transitions
labelled with the letters in $w_{\text{ref}}$, and with potentially additional
forward and backward transitions. Figure 1 depicts $F$ for
$w_{\text{ref}}=bbac$. A word $w$ accepted by $F$ consists of concatenated
“factors” of $w_{\text{ref}}$, and its dissimilarity with $w_{\text{ref}}$ is
correlated with the number of non-direct transitions. By assigning a small
probability $\alpha$ to non-direct transitions, $F$ becomes a generative
Markov model with tunable “divergence” from $w_{\text{ref}}$. In order to
impose more musical structure on the generated words, our previous work [11]
additionally requires that improvisations satisfy rules encoded as
deterministic finite automata, by taking the product of the generative Markov
model and the DFAs. While this approach is heuristic and lacks any formal
guarantees, it has the basic elements common to machine improvisation schemes:
(i) it involves randomly generating strings from a formal language typically
encoded as an automaton, (ii) it enforces diversity in the generated strings,
and (iii) it includes a requirement on which strings are admissible based on
their divergence from a reference string. The definition we propose below
captures these elements in a rigorous theoretical manner, suitable for further
analysis. In Sec. 4, we revisit the factor oracle, sketching how the notion of
divergence from $w_{\text{ref}}$ that it represents can be encoded in our
formalism.

$s_{0}$$s_{1}$$s_{2}$$s_{3}$$s_{4}$$b$$b$$a$$c$$a$$c$$a$$\epsilon$$\epsilon$$\epsilon$$\epsilon$
Figure 1. Factor oracle constructed from the word $w_{\text{ref}}=bbac$.

###  2.2. Problem Definition

We abbreviate deterministic and nondeterministic finite automata as DFAs and
NFAs respectively. We use the standard definition of probabilistic finite
automata from [18], where a string is accepted iff it causes the automaton to
reach an accepting state with probability greater than a specified _cut-point_
$p\in[0,1)$. We call a probabilistic finite automaton, together with a choice
of cut-point so that its language is definite, a PFA. We write
$\Pr[f(X)\>|\>X\leftarrow D]$ for the probability of event $f(X)$ given that
the random variable $X$ is drawn from the distribution $D$.

######  Definition 2.1.

An _improvisation automaton_ is a finite automaton (DFA, NFA, or PFA)
$\mathcal{I}$ over a finite alphabet $\Sigma$. An _improvisation_ is any word
$w\in L(\mathcal{I})$, and $I=L(\mathcal{I})$ is the set of all
improvisations.

######  Definition 2.2.

An _admissibility predicate_ is a computable predicate
$\alpha:\Sigma^{*}\rightarrow\\{0,1\\}$. An improvisation $w\in I$ is
_admissible_ if $\alpha(w)=1$. We write $A$ for the set of all admissible
improvisations.

#### Running Example.

Our concepts will be illustrated with a simple example. Our aim is to produce
variations of the binary string $s=001$ of length 3, subject to the constraint
that there cannot be two consecutive 1s. So $\Sigma=\\{0,1\\}$, and
$\mathcal{I}$ is a DFA which accepts all length-3 strings that do not have two
1s in a row. To ensure that our variations are similar to $s$, we let our
admissibility predicate $\alpha(w)$ be 1 if the Hamming distance between $w$
and $s$ is at most 1, and 0 otherwise. Then the improvisations are the strings
$000$, $001$, $010$, $100$, and $101$, of which $000$, $001$, and $101$ are
admissible.

Intuitively, an improviser samples from the set of improvisations according to
some distribution. But what requirements must one impose on this distribution?
Since we want a variety of improvisations, we require that each one is
generated with probability at most some bound $\rho$. By choosing a small
value of $\rho$ we can thus ensure that many different improvisations can be
generated, and that no single one is output too frequently. Other constraints
are possible, e.g. requiring that every improvisation have nonzero
probability, but we view this as too restrictive: if there are a large number
of possible improvisations, it should be acceptable for an improviser to
generate many but not all of them. Another possibility would be to ensure
variety by imposing some minimum distance between the improvisations. This
could be reasonable in a setting (such as music) where there is a natural
metric on the space of improvisations, but we choose to keep our setting
general and not assume such a metric. Finally, we require our generated
improvisation to be admissible with probability at least $1-\epsilon$ for some
specified $\epsilon$. When the admissibility predicate encodes a notion of
similarity to a reference string, for example, this allows us to require that
our improvisations usually be similar to the reference. Combining these
requirements, we obtain our definitions of an acceptable distribution over
improvisations and thus of an improviser:

######  Definition 2.3.

Given $\mathcal{C}=(\mathcal{I},\alpha,\epsilon,\rho)$ with $\mathcal{I}$ and
$\alpha$ as in Definitions 2.1 and 2.2, $\epsilon\in[0,1]\cap\mathbb{Q}$ an
error probability, and $\rho\in(0,1]\cap\mathbb{Q}$ a probability bound, a
distribution $D:\Sigma^{*}\rightarrow[0,1]$ with support $S$ is an
_$(\epsilon,\rho)$ -improvising distribution_ if:

  * •

$S\subseteq I$

  * •

$\forall w\in S,D(w)\leq\rho$

  * •

$\Pr[w\in A\>|\>w\leftarrow D]\geq 1-\epsilon$

If there is an $(\epsilon,\rho)$-improvising distribution, we say that
$\mathcal{C}$ is $(\epsilon,\rho)$-_feasible_ (or simply feasible). An
_$(\epsilon,\rho)$ -improviser_ (or simply improviser) for a feasible
$\mathcal{C}$ is an expected finite-time probabilistic algorithm generating
strings in $\Sigma^{*}$ whose output distribution (on empty input) is an
$(\epsilon,\rho)$-improvising distribution.

To summarize, if $\mathcal{C}=(\mathcal{I},\alpha,\epsilon,\rho)$ is feasible,
there exists a distribution satisfying the requirements in Definition 2.3, and
an improviser is a probabilistic algorithm for sampling from one.

#### Running Example.

For our running example, $\mathcal{C}=(\mathcal{I},\alpha,0,1/4)$ is not
feasible since $\epsilon=0$ means we can only generate admissible
improvisations, and since there are only 3 of those we cannot possibly give
them all probability at most $1/4$. Increasing $\rho$ to $1/3$ would make
$\mathcal{C}$ feasible. Increasing $\epsilon$ to $1/4$ would also work,
allowing us to return an inadmissible improvisation $1/4$ of the time: an
algorithm uniformly sampling from $\\{000,001,101,100\\}$ would be an
improviser for $(\mathcal{I},\alpha,1/4,1/4)$.

######  Definition 2.4.

Given $\mathcal{C}=(\mathcal{I},\alpha,\epsilon,\rho)$, the _control
improvisation (CI)_ problem is to decide whether $\mathcal{C}$ is feasible,
and if so to generate an improviser for $\mathcal{C}$.

Ideally, we would like an efficient algorithm to solve the CI problem.
Furthermore, the improvisers our algorithm produces should themselves be
efficient, in the sense that their runtimes are polynomial in the size of the
original CI instance. This leads to our last definition:

######  Definition 2.5.

A _polynomial-time improvisation scheme_ for a class $\mathcal{P}$ of CI
instances is a polynomial-time algorithm $S$ with the following properties:

  * •

for any $\mathcal{C}\in\mathcal{P}$, if $\mathcal{C}$ is feasible then
$S(\mathcal{C})$ is an improviser for $\mathcal{C}$, and otherwise
$S(\mathcal{C})=\bot$

  * •

there is a polynomial $p:\mathbb{R}\rightarrow\mathbb{R}$ such that if
$G=S(\mathcal{C})\neq\bot$, then $G$ has expected runtime at most
$p(|\mathcal{C}|)$.

A polynomial-time improvisation scheme for a class of CI instances is an
efficient, uniform way to solve the control improvisation problem for that
class. In Sections 4 and 5 we will investigate which classes have such
improvisation schemes.

##  3\. Existence of Improvisers

It turns out that the feasibility of an improvisation problem is completely
determined by the sizes of $I$ and $A$:

######  Theorem 3.1.

For any $\mathcal{C}=(\mathcal{I},\alpha,\epsilon,\rho)$, the following are
equivalent:

  1. (a)

$\mathcal{C}$ is feasible.

  2. (b)

$|I|\geq 1/\rho$ and $|A|\geq(1-\epsilon)/\rho$.

  3. (c)

There is an improviser for $\mathcal{C}$.

######  Proof 3.2.

(a)$\Rightarrow$(b)::

Suppose $D$ is an $(\epsilon,\rho)$-improvising distribution with support $S$.
Then $\rho|S|=\sum_{w\in S}\rho\geq\sum_{w\in S}D(w)=1$, so $|I|\geq|S|\geq
1/\rho$. We also have $\rho|S\cap A|=\sum_{w\in S\cap A}\rho\geq\sum_{w\in
S\cap A}D(w)=\Pr[w\in A\>|\>w\leftarrow D]\geq 1-\epsilon$, so $|A|\geq|S\cap
A|\geq(1-\epsilon)/\rho$.

(b)$\Rightarrow$(c)::

Defining $N=\left\lceil(1-\epsilon)/\rho\right\rceil$, we have $|A|\geq N$. If
$N\geq 1/\rho$, then there is a subset $S\subseteq A$ with $|S|=\left\lceil
1/\rho\right\rceil$. Since $1/\left\lceil 1/\rho\right\rceil\leq\rho$, the
uniform distribution on $S$ is a $(0,\rho)$-improvising distribution. Since
this distribution has finite support and rational probabilities, there is an
expected finite-time probabilistic algorithm sampling from it, and this is a
$(0,\rho)$-improviser. If instead $N<1/\rho$, defining $M=\left\lceil
1/\rho\right\rceil-N$ we have $M\geq 1$. Since $|I|\geq\left\lceil
1/\rho\right\rceil=N+M$, there are disjoint subsets $S\subseteq A$ and
$T\subseteq I$ with $|S|=N$ and $|T|=M$. Let $D$ be the distribution on $S\cup
T$ where each element of $S$ has probability $\rho$ and each element of $T$
has probability $(1-\rho N)/M=(1-\rho
N)/\left\lceil(1/\rho)-N\right\rceil=(1-\rho N)/\left\lceil(1-\rho
N)/\rho\right\rceil\leq\rho$. Then $\Pr[w\in A|w\leftarrow D]\geq\rho N\geq
1-\epsilon$, so $D$ is a $(\epsilon,\rho)$-improvising distribution. As above
there is an expected finite-time probabilistic algorithm sampling from $D$,
and this is an $(\epsilon,\rho)$-improviser.

(c)$\Rightarrow$(a)::

Immediate.

######  Remark 3.3.

In fact, whenever $\mathcal{C}$ is feasible, the construction in the proof of
Theorem 3.1 gives an improviser which works in nearly the most trivial
possible way: it has two finite lists $S$ and $T$, flips a (biased) coin to
decide which list to use, and then returns an element of that list uniformly
at random.

A consequence of this characterization is that when there are infinitely-many
admissible improvisations, there is an improviser with zero error probability:

######  Corollary 3.4.

If $A$ is infinite, $(\mathcal{I},\alpha,0,\rho)$ is feasible for any
$\rho\in(0,1]\cap\mathbb{Q}$.

In addition to giving conditions for feasibility, Theorem 3.1 yields an
algorithm which is guaranteed to find an improviser for any feasible CI
problem.

######  Corollary 3.5.

If $\mathcal{C}$ is feasible, an improviser for $\mathcal{C}$ may be found by
an effective procedure.

######  Proof 3.6.

The sets $I$ and $A$ are clearly computably enumerable, since $\alpha$ is
computable. We enumerate $I$ and $A$ until enough elements are found to
perform the construction in Theorem 3.1. Since $\mathcal{C}$ is feasible, the
theorem ensures this search will terminate.

We cannot give an upper bound on the time needed by this algorithm without
knowing something about the admissibility predicate $\alpha$. Therefore
although as noted in the remark above whenever there are improvisers at all
there is one of a nearly-trivial form, actually finding such an improviser
could be difficult. In fact, it could be faster to generate an improviser
which is _not_ of this form, as seen for example in Sec. 4.

######  Corollary 3.7.

The set of feasible CI instances is computably enumerable but not computable.

######  Proof 3.8.

Enumerability follows immediately from the previous Corollary. If checking
whether $\mathcal{C}$ is feasible were decidable, then so would be checking if
$|A|\geq(1-\epsilon)/\rho$, but this is undecidable since $\alpha$ can be an
arbitrary computable predicate.

##  4\. Finite-Memory Admissibility Predicates

In order to bound the time needed to find an improviser, we must constrain the
admissibility predicate $\alpha$. Perhaps the simplest type of admissibility
predicate is one which can be computed by a DFA, i.e., one such that there is
some DFA $\mathcal{D}$ which accepts a word $w\in\Sigma^{*}$ iff
$\alpha(w)=1$. This captures the notion of a _finite-memory_ admissibility
predicate, where admissibility of a word can be determined by scanning the
word left-to-right, only being able to remember a finite number of already-
seen symbols. An example of a finite-memory predicate $\alpha$ is one such
that $\alpha(w)=1$ iff each subword of $w$ of a fixed constant length
satisfies some condition. By the pumping lemma, such predicates have the
property that continually repeating some section of a word can produce an
infinite family of improvisations, which could be a disadvantage if looking
for “creative”, non-repetitive improvisations. However, in applications such
as music we impose a maximum length on improvisations, so this is not an
issue.

######  Example 4.1 (Factor Oracles).

Recall that one way of measuring the divergence of an improvisation $w$
generated by the factor oracle $F$ built from a word $w_{\text{ref}}$ is by
counting the number of non-direct transitions that $w$ causes $F$ to take.
Since DFAs cannot count without bound, we can use a sliding window of some
finite size $k$. Then our admissibility predicate $\alpha$ can be that at any
point as $F$ processes $w$, the number of the previous $k$ transitions which
were non-direct lies in some interval $[\ell,h]$ with $0\leq\ell\leq h\leq k$.
This predicate can be encoded as a DFA of size $O(|F|\cdot 2^{k})$ (see the
Appendix for details). The size of the automaton grows exponentially in the
size of the window, but for small windows it can be reasonable.

When the admissibility predicate is finite-memory and the automaton
$\mathcal{I}$ is a DFA, there is an efficient procedure to test if an
improviser exists and synthesize one if so. The construction is similar to
that of Theorem 3.1, but avoids explicit enumeration of all improvisations to
be put in the range of the improviser. To avoid enumeration we use a classic
method of uniformly sampling from the language of a DFA $\mathcal{D}$ (see for
example [13, 10]). The next few lemmas summarize the results we need, proofs
being given in the Appendix for completeness. The first step is to determine
the size of the language.

lemma-indexed-by-theoremlemmaDFACounting If $\mathcal{D}$ is a DFA,
$|L(\mathcal{D})|$ can be computed in polynomial time.

Once we know the size of $L(\mathcal{D})$ we can efficiently sample from it,
handling infinite languages by sampling from a finite subset of a desired
size.

lemma-indexed-by-theoremlemmaDFAPumpSamp There is a polynomial $p(x,y)$ such
that for any $N\in\mathbb{N}$ and DFA $\mathcal{D}$ with infinite language,
there is a probabilistic algorithm $S$ which uniformly samples from a subset
of $L(\mathcal{D})$ of size $N$ in expected time at most $p(|\mathcal{D}|,\log
N)$, and which can be constructed in the same time.

lemma-indexed-by-theoremlemmaDFAUnifSamp There is a polynomial $q(x)$ such
that for any DFA $\mathcal{D}$ with finite language, there is a probabilistic
algorithm $S$ which uniformly samples from $L(\mathcal{D})$ in expected time
at most $q(|\mathcal{D}|)$, and which can be constructed in the same time.

Using these sampling techniques, we have the following:

######  Theorem 4.2.

The class of CI instances $\mathcal{C}$ where $\mathcal{I}$ is a DFA and
$\alpha$ is computable by a DFA has a polynomial-time improvisation scheme.

######  Proof 4.3.

The proof considers five cases. We first define some notation. Let
$\mathcal{D}$ denote the DFA giving $\alpha$. Letting $\mathcal{A}$ be the
product of $\mathcal{I}$ and $\mathcal{D}$, we have $A=L(\mathcal{A})$. This
product can be computed in polynomial time since the automata are both DFAs,
and $|\mathcal{A}|$ is polynomial in $|\mathcal{C}|$ and $|\mathcal{D}|$. In
some of the cases below we will also use a DFA $\mathcal{B}$ which is the
synchronous product of $\mathcal{I}$ and the complement of $\mathcal{A}$.
Clearly $L(\mathcal{B})=I\setminus A$, and the size of $\mathcal{B}$ and the
time needed to construct it are also polynomial in $|\mathcal{C}|$ and
$|\mathcal{D}|$.

Next we compute $|A|=|L(\mathcal{A})|$ and $|I|=|L(\mathcal{I})|$ in
polynomial time using Lemma 4.1. There are now several cases (illustrated in
Figure 2):

$\infty$$0$$\frac{1-\epsilon}{\rho}$$\frac{1}{\rho}$$|I|$$\infty$$\frac{1-\epsilon}{\rho}$$\frac{1}{\rho}$$|A|$(E)(A)(B)(C)(D)
Figure 2. Cases for Theorem 4.2. The dark gray region cannot occur.

  1. (A)

$|A|=\infty$: Applying Lemma 4.1 to $\mathcal{A}$ with $N=\left\lceil
1/\rho\right\rceil$, we obtain a probabilistic algorithm $S$ which uniformly
samples from a subset of $L(\mathcal{A})=A$ of size $\left\lceil
1/\rho\right\rceil$. Since $1/\left\lceil 1/\rho\right\rceil\leq\rho$, we have
that $S$ is a $(0,\rho)$-improviser and return it.

  2. (B)

$1/\rho\leq|A|<\infty$: Applying Lemma 4.1 to $\mathcal{A}$, we obtain a
probabilistic algorithm $S$ which uniformly samples from $L(\mathcal{A})=A$.
Since $1/|A|\leq\rho$, we have that $S$ is a $(0,\rho)$-improviser and return
it.

  3. (C)

$(1-\epsilon)/\rho\leq|A|<1/\rho$ and $|I|=\infty$: Applying Lemma 4.1 to
$\mathcal{A}$ we obtain $S$ as in the previous case. Defining $M=\left\lceil
1/\rho\right\rceil-|A|$, we have $\infty=|L(\mathcal{B})|>M\geq 1$. Applying
Lemma 4.1 to $\mathcal{B}$ with $N=M$ yields a probabilistic algorithm
$S^{\prime}$ which uniformly samples from a subset of
$L(\mathcal{B})=I\setminus A$ of size $M$. Let $G$ be a probabilistic
algorithm which with probability $\rho|A|$ executes $S$, and otherwise
executes $S^{\prime}$. Then since $L(\mathcal{A})=A$ and
$L(\mathcal{B})=I\setminus A$ are disjoint, every word generated by $G$ has
probability either $(\rho|A|)/|A|=\rho$ (if it is in $A$) or
$(1-\rho|A|)/M=(1-\rho|A|)/\left\lceil(1-\rho|A|)/\rho\right\rceil\leq\rho$
(if it is in $I\setminus A$). Also, $G$ outputs a member of $A$ with
probability $\rho|A|\geq 1-\epsilon$, so $G$ is an
$(\epsilon,\rho)$-improviser and we return it.

  4. (D)

$(1-\epsilon)/\rho\leq|A|<1/\rho\leq|I|<\infty$: As in the previous case,
except obtaining $S^{\prime}$ by applying Lemma 4.1 to $\mathcal{B}$. Since
$|I|\geq\left\lceil 1/\rho\right\rceil$, we have $|L(\mathcal{B})|=|I\setminus
A|\geq M$ and so $G$ as constructed above is an $(\epsilon,\rho)$-improviser.

  5. (E)

$|I|<1/\rho$ or $|A|<(1-\epsilon)/\rho$: By Theorem 3.1, $\mathcal{C}$ is not
feasible, so we return $\bot$.

This procedure takes time polynomial in $|\mathcal{I}|$, $|\mathcal{D}|$, and
$\log(1/\rho)$, so it is polynomial-time. Also, a fixed polynomial in these
quantities bounds the expected runtime of the generated improviser, so the
procedure is a polynomial-time improvisation scheme.

#### Running Example.

Recall that for our running example
$\mathcal{C}=(\mathcal{I},\alpha,1/4,1/4)$, we have
$I=\\{000,001,010,100,101\\}$ and $A=\\{000,001,101\\}$. Since $|A|=3$ and
$|I|=5$, we are in case (D) of Theorem 4.2. So our scheme uses Lemma 4.1 to
obtain $S$ and $S^{\prime}$ uniformly sampling from $A$ and $I\setminus
A=\\{010,100\\}$ respectively. It returns a probabilistic algorithm $G$ that
executes $S$ with probability $\rho|A|=3/4$ and otherwise executes
$S^{\prime}$. So $G$ returns $000$, $001$, and $101$ with probability $1/4$
each, and $010$ and $100$ with probability $1/8$ each. The output distribution
of $G$ satisfies our conditions, so it is an improviser for $\mathcal{C}$.

##  5\. More Complex Automata

While counting the language of a DFA is easy, in the case of an NFA it is much
more difficult, and so there are unlikely to be polynomial-time improvisation
schemes for more complex automata. Let $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$
be the classes of CI instances where $\mathcal{I}$ or $\alpha$ respectively
are given by an NFA, and the other is given by a DFA. Then denoting by
$\mathcal{N}$ either of these classes, we have (deferring full proofs from
this section to the Appendix):

theoremtheoremNFAHardness Determining whether $\mathcal{C}\in\mathcal{N}$ is
feasible is $\mathsf{\\#P}$-hard.

######  Proof 5.1 (Proof sketch).

The problem of counting the language of an NFA, which is $\mathsf{\\#P}$-hard
[14], is polynomially reducible to that of checking if
$\mathcal{C}\in\mathcal{N}$ is feasible.

######  Remark 5.2.

Determining feasibility of $\mathcal{N}$-instances is not a counting problem,
so it is not $\mathsf{\\#P}$-complete, but it is clearly in
$\mathsf{P}^{\mathsf{\\#P}}$: we construct the automata $\mathcal{I}$ and
$\mathcal{A}$ as in Theorem 4.2 (now they can be NFAs), count their languages
using $\mathsf{\\#P}$, and apply Theorem 3.1.

######  Corollary 5.3.

If there is a polynomial-time improvisation scheme for $\mathcal{N}$, then
$\mathsf{P}=\mathsf{P}^{\mathsf{\\#P}}$.

This result indicates that in general, the control improvisation problem is
probably intractable in the presence of NFAs. Some special cases could still
be handled in practice: for example, if the NFA is very small it could be
converted to a DFA. Another tractable case is where although one of
$\mathcal{I}$ or $\mathcal{A}$ (as in Theorem 4.2) is an NFA, it has infinite
language (this can clearly be detected in polynomial time). If $\mathcal{A}$
is an NFA with infinite language we can use case (A) of the proof of Theorem
4.2, since an NFA can be pumped in the same way as a DFA. If instead
$\mathcal{A}$ is a DFA with finite language but $\mathcal{I}$ is an NFA with
infinite language, one of the other cases (B), (C), or (E) applies, and in
case (C) we can sample $I\setminus A$ by pumping $\mathcal{I}$ enough to
ensure we get a string longer than any accepted by $\mathcal{A}$. Table 1 in
Section 7 summarizes these cases.

For still more complex automata, the CI problem becomes even harder. In fact,
it is impossible if we allow either $\mathcal{I}$ or $\alpha$ to be given by a
PFA. Let $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ be the classes of CI
instances where each of these respectively are given by a PFA, and the other
is given by a DFA. Then letting $\mathcal{P}$ be either of these classes, we
have:

theoremtheoremPFAHardness Determining whether $\mathcal{C}\in\mathcal{P}$ is
feasible is undecidable.

######  Proof 5.4 (Proof sketch).

Checking the feasibility of $\mathcal{C}$ amounts to counting the language of
a PFA, but determining whether the language of a PFA is empty is undecidable
[17, 9].

##  6\. Symbolic Techniques

Previously we have assumed that the automata defining a control improvisation
problem were given explicitly. However, in practice there may be insufficient
memory to store full transition tables, in which case an implicit
representation is required. This prevents us from using the polynomial-time
improvisation scheme of Theorem 4.2, so we must look for alternate methods.
These will depend on the type of implicit representation used. We focus on
representations of DFAs and NFAs by propositional formulae, as used for
example in bounded model checking [4].

######  Definition 6.1.

A _symbolic automaton_ is a transition system over states
$S\subseteq\\{0,1\\}^{n}$ and inputs $\Sigma\subseteq\\{0,1\\}^{m}$
represented by:

  * •

a formula $\mathrm{init}(\overline{x})$ which is true iff
$\overline{x}\in\\{0,1\\}^{n}$ is an initial state,

  * •

a formula $\mathrm{acc}(\overline{x})$ which is true iff
$\overline{x}\in\\{0,1\\}^{n}$ is an accepting state, and

  * •

a formula $\delta(\overline{x},\overline{a},\overline{y})$ which is true iff
there is a transition from $\overline{x}\in\\{0,1\\}^{n}$ to
$\overline{y}\in\\{0,1\\}^{n}$ on input $\overline{a}\in\\{0,1\\}^{m}$ .

A symbolic automaton accepts words in $\Sigma^{*}$ according to the usual
definition for NFAs.

Given a symbolic automaton, it is straightforward to generate a formula whose
models correspond, for example, to accepting paths of at most a given length
(see [4] for details). A SAT solver can then be used to find such a path. We
refer to the length of the longest simple accepting path as the _diameter_ of
the automaton. This will be an important parameter in the runtime of our
algorithms. In some cases an upper bound on the diameter is known ahead of
time: for example, if we only want improvisations of up to some maximum
length, and have encoded that constraint in $\mathcal{I}$. If the diameter is
not known, it can be found iteratively with SAT queries asserting the
existence of a simple accepting path of length $n$, increasing $n$ until we
find no such path exists. The diameter could be exponentially large compared
to the symbolic representation, but this is a worst-case scenario.

Our approach for solving the control improvisation problem with symbolic
automata will be to adapt the procedure of Theorem 4.2, replacing the counting
and sampling techniques used there with ones that work on symbolic automata.
For language size estimation we use the following: lemma-indexed-by-
theoremlemmaSymbolicCount If $\mathcal{S}$ is a symbolic automaton with
diameter $D$, for any $\tau,\delta>0$ we can compute an estimate of
$|L(\mathcal{S})|$ accurate to within a factor of $1+\tau$ in time polynomial
in $|\mathcal{S}|$, $D$, $1/\tau$, and $\log(1/\delta)$ relative to an
$\mathsf{NP}$ oracle.

Sampling from infinite languages can be done by a direct adaptation of the
method for explicit DFAs in Lemma 4.1. lemma-indexed-by-
theoremlemmaSymbPumpSamp There is a polynomial $p(x,y,z)$ such that for any
$N\in\mathbb{N}$ and symbolic automaton $\mathcal{Y}$ with infinite language
and diameter $D$, there is a probabilistic oracle algorithm $S^{\mathsf{NP}}$
which uniformly samples from a subset of $L(\mathcal{Y})$ of size $N$ in
expected time at most $p(|\mathcal{Y}|,D,\log N)$ and which can be constructed
in the same time.

To sample from a finite language, we use techniques for almost-uniform
generation of models of propositional formulae. In theory uniform sampling can
be done exactly using a SAT solver [3], but the only algorithms which work in
practice are _approximate_ uniform generators such as $\mathsf{UniGen}$ [7].
This algorithm guarantees that the probability of returning any given model is
within a factor of $1+\tau$ of the uniform probability, for any given
$\tau>6.84$ (the constant is for technical reasons specific to
$\mathsf{UniGen}$). $\mathsf{UniGen}$ can also do projection sampling, i.e.,
sampling where two models are considered identical if they agree on the set of
variables being projected onto. Henceforth, for simplicity, we will assume we
have a generic almost-uniform generator that can do projection, and will
ignore the $\tau>6.84$ restriction imposed by $\mathsf{UniGen}$ (although we
might want to abide by this in practice in order to be able to use the fastest
available algorithm). We assume that the generator runs in time polynomial in
$1/\tau$ and the size of the given formula relative to an $\mathsf{NP}$
oracle, and succeeds with at least some fixed constant probability. lemma-
indexed-by-theoremlemmaSymbUnifSamp There is a polynomial $q(x,y,z)$ such that
for any $\tau>0$ and symbolic automaton $\mathcal{Y}$ with finite language and
diameter $D$, there is a probabilistic oracle algorithm $S^{\mathsf{NP}}$
which samples from $L(\mathcal{S})$ uniformly up to a factor of $1+\tau$ in
expected time at most $q(|\mathcal{Y}|,D,1/\tau)$, and which can be
constructed in the same time.

Now we can put these methods together to get a version of Theorem 4.2 for
symbolic automata. The major differences are that this scheme requires an
$\mathsf{NP}$ oracle, has some probability of failure (which can be
specified), and returns an improviser with a slightly sub-optimal value of
$\rho$. The proof generally follows that of Theorem 4.2, so we only sketch the
differences here (see the Appendix for a full proof).
theoremtheoremSymbolicScheme There is a procedure that given any CI problem
$\mathcal{C}$ where $\mathcal{I}$ and $\alpha$ are given by symbolic automata
with diameter at most $D$, and any $\epsilon\in[0,1]$, $\rho\in(0,1]$, and
$\tau,\delta>0$, if $\mathcal{C}$ is $(\epsilon,\rho/(1+\tau))$-feasible
returns an $(\epsilon,(1+\tau)^{2}(1+\epsilon)\rho)$-improviser with
probability at least $1-\delta$. Furthermore, the procedure and the
improvisers it generates run in expected time given by some fixed polynomial
in $|\mathcal{C}|$, $D$, $1/\tau$, and $\log(1/\delta)$ relative to an
$\mathsf{NP}$ oracle.

######  Proof 6.2 (Proof sketch).

We first compute estimates $E_{A}$ and $E_{I}$ of $|A|$ and $|I|$ respectively
using Lemma 6.1. Then we break into cases as in Theorem 4.2:

  1. (A)

$E_{A}=\infty$: As in case (A) of Theorem 4.2, using Lemma 6.1 in place of
Lemma 4.1. We obtain a $(0,\rho)$-improviser.

  2. (B)

$1/\rho\leq E_{A}<\infty$: As in case (B) of Theorem 4.2, using Lemma 6.1 in
place of Lemma 4.1. Since we can do only approximate counting and sampling, we
obtain a $(0,(1+\tau)^{2}\rho)$-improviser.

  3. (C)

$(1-\epsilon)/\rho\leq E_{A}<1/\rho$ and $E_{I}=\infty$: As in case (C) of
Theorem 4.2, using Lemmas 6.1 and 6.1 in place of Lemmas 4.1 and 4.1. Our use
of approximate counting/sampling means we obtain only an
$(\epsilon,(1+\tau)^{2}\rho)$-improviser.

  4. (D)

$(1-\epsilon)/\rho\leq E_{A}<1/\rho\leq E_{I}<\infty$: We cannot use the
procedure in case (D) of Theorem 4.2, since it may generate an element of
$L(\mathcal{B})$ with too high probability if our estimate $E_{A}$ is
sufficiently small. Instead we sample almost-uniformly from $L(\mathcal{A})$
with probability $\epsilon$, and from $L(\mathcal{I})$ with probability
$1-\epsilon$. This yields an
$(\epsilon,(1+\tau)^{2}(1+\epsilon)\rho)$-improviser.

  5. (E)

$E_{I}<1/\rho$ or $E_{A}<(1-\epsilon)/\rho$: We return $\bot$.

If $\mathcal{C}$ is $(\epsilon,\rho/(1+\tau))$-feasible, case (E) happens with
probability less than $\delta$ by Theorem 3.1. Otherwise, we obtain an
$(\epsilon,(1+\tau)^{2}(1+\epsilon)\rho)$-improviser.

Therefore, it is possible to approximately solve the control improvisation
problem when the automata are given by a succinct propositional formula
representation. This allows working with general NFAs, and very large automata
that cannot be stored explicitly, but comes at the cost of using a SAT solver
(perhaps not a heavy cost given the dramatic advances in the capacity of SAT
solvers) and possibly having to increase $\rho$ by a small factor.

##  7\. Conclusion

In this paper, we introduced control improvisation, the problem of creating
improvisers that randomly generate variants of words in the languages of
automata. We gave precise conditions for when improvisers exist, and
investigated the complexity of finding improvisers for several major classes
of automata. In particular, we showed that the control improvisation problem
for DFAs can be solved in polynomial time, while it is intractable in most
cases for NFAs and undecidable for PFAs. These results are summarized in Table
1. Finally, we studied the case where the automata are presented symbolically
instead of explicitly, and showed that the control improvisation problem can
still be solved approximately using SAT solvers.

One interesting direction for future work would be to find other tractable
cases of the control improvisation problem deriving from finer structural
properties of the automata than just determinism. Extensions of the theory to
other classes of formal languages, for instance context-free languages
represented by pushdown automata or context-free grammars, are also worthy of
study. Finally, we are investigating further applications, particularly in the
areas of testing, security, and privacy.

| $\alpha$ | DFA | NFA | PFA
---|---|---|---|---
$\mathcal{I}$ |  |  | $L(\mathcal{A})=\infty$ | $L(\mathcal{A})<\infty$ |
DFA |  | poly-time | $\mathsf{\\#P}$-hard |
NFA | $L(\mathcal{I})=\infty$
$L(\mathcal{I})<\infty$ |  $\mathsf{\\#P}$-hard | -
PFA |  | undecidable
Table 1. Complexity of the control improvisation problem when $\mathcal{I}$
and $\alpha$ are given by various different types of automata. The cell marked
‘-’ is impossible since $L(\mathcal{A})\subseteq L(\mathcal{I})$.

#### Acknowledgements

The first three authors dedicate this paper to the memory of the fourth
author, David Wessel, who passed away while it was being written. We would
also like to thank Ben Caulfield, Orna Kupferman, Markus Rabe, and the
anonymous reviewers for their helpful comments. This work is supported in part
by the National Science Foundation Graduate Research Fellowship Program under
Grant No. DGE-1106400, by the NSF Expeditions grant CCF-1139138, and by
TerraSwarm, one of six centers of STARnet, a Semiconductor Research
Corporation program sponsored by MARCO and DARPA.

## References

  * [1] Gérard Assayag, Georges Bloch, Marc Chemillier, Benjamin Lévy, and Shlomo Dubnov.  OMax.  http://repmus.ircam.fr/omax/home, 2012.
  * [2] Gérard Assayag and Shlomo Dubnov.  Using factor oracles for machine improvisation.  Soft Comput., 8(9):604–610, 2004.
  * [3] Mihir Bellare, Oded Goldreich, and Erez Petrank.  Uniform generation of NP-witnesses using an NP-oracle.  Information and Computation, 163(2):510–526, 2000.
  * [4] Armin Biere, Alessandro Cimatti, Edmund M. Clarke, and Yunshan Zhu.  Symbolic model checking without BDDs.  In 5th International Conference on Tools and Algorithms for Construction and Analysis of Systems, pages 193–207, 1999.
  * [5] Christos G. Cassandras and Stéphane Lafortune.  Introduction to Discrete Event Systems.  Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.
  * [6] Supratik Chakraborty, Kuldeep S. Meel, and Moshe Y. Vardi.  A scalable approximate model counter.  In Principles and Practice of Constraint Programming, pages 200–216. Springer, 2013.
  * [7] Supratik Chakraborty, Kuldeep S. Meel, and Moshe Y. Vardi.  Balancing scalability and uniformity in SAT witness generator.  In 51st Design Automation Conference, pages 1–6. ACM, 2014.
  * [8] Loek Cleophas, Gerard Zwaan, and Bruce W. Watson.  Constructing factor oracles.  In In Proceedings of the 3rd Prague Stringology Conference, 2003\.
  * [9] Anne Condon and Richard J. Lipton.  On the complexity of space bounded interactive proofs.  In 30th Annual Symposium on Foundations of Computer Science, pages 462–467. IEEE, 1989.
  * [10] Alain Denise, Marie-Claude Gaudel, Sandrine-Dominique Gouraud, Richard Lassaigne, and Sylvain Peyronnet.  Uniform random sampling of traces in very large models.  In 1st International Workshop on Random Testing, pages 10–19. ACM, 2006.
  * [11] Alexandre Donzé, Rafael Valle, Ilge Akkaya, Sophie Libkind, Sanjit A. Seshia, and David Wessel.  Machine improvisation with formal specifications.  In Proceedings of the 40th International Computer Music Conference (ICMC), September 2014.
  * [12] Andrew D. Gordon, Thomas A. Henzinger, Aditya V. Nori, and Sriram K. Rajamani.  Probabilistic programming.  In International Conference on Software Engineering (ICSE Future of Software Engineering). IEEE, May 2014.
  * [13] Timothy Hickey and Jacques Cohen.  Uniform random generation of strings in a context-free language.  SIAM Journal on Computing, 12(4):645–655, 1983.
  * [14] Sampath Kannan, Z. Sweedyk, and Steve Mahaney.  Counting and random generation of strings in regular languages.  In Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 551–557. SIAM, 1995.
  * [15] Stéphane Lafortune.  Personal Communication, 2015.
  * [16] Edward A. Lee.  Personal Communication, 2013.
  * [17] Masakazu Nasu and Namio Honda.  Mappings induced by PGSM-mappings and some recursively unsolvable problems of finite probabilistic automata.  Information and Control, 15(3):250–273, 1969.
  * [18] Michael O. Rabin.  Probabilistic automata.  Information and Control, 6(3):230–245, 1963.
  * [19] R. Rowe.  Machine Musicianship.  MIT Press, 2001.
  * [20] Michael Sutton, Adam Greene, and Pedram Amini.  Fuzzing: Brute Force Vulnerability Discovery.  Addison-Wesley, 2007.

##  Appendix A Proofs

######  Example D.1 (Factor Oracles).

The factor oracle-based admissibility predicate $\alpha$ described above can
be encoded as a DFA of size $O(|F|\cdot 2^{k})$ as follows: we have a copy of
$F$, denoted $F_{s}$, for every string $s\in\\{0,1\\}^{k}$, each bit of $s$
indicating whether the corresponding previous transition (out of the last $k$)
was non-direct. As each new symbol is processed, we execute the current copy
of $F$ as usual, but move to the appropriate state of the copy of $F$
corresponding to the new $k$-transition history, i.e., if we were in $F_{s}$,
we move to $F_{t}$ where $t$ consists of the last $k-1$ bits of $s$ followed
by a 0 if the transition we took was direct and a 1 otherwise. Making the
states of $F_{s}$ accepting iff the number of 1s in $s$ is in $[\ell,h]$, this
automaton represents $\alpha$ as desired.

*

######  Proof D.2.

First we prune irrelevant states unreachable from the initial state or from
which no accepting state can be reached (this pruning can clearly be done in
polynomial time). If the resulting graph contains a cycle (also detectable in
polynomial time), we return $\infty$. Otherwise $\mathcal{D}$ is a DAG with
multiple edges, and every sink is an accepting state. For each accepting state
$s$ we add a new vertex and an edge to it from $s$. Then there is a one-to-one
correspondence between accepting words of $\mathcal{D}$ and paths from the
initial state to a sink. Now we can compute for each vertex $v$ the number of
paths $p_{v}$ from it to a sink using the usual linear-time DAG algorithm
(traversal in reverse topological order) modified slightly to handle multiple
edges. We return $p_{v}$ with $v$ the initial state.

*

######  Proof D.3.

Having pruned $\mathcal{D}$ as in Lemma 4.1, since $L(\mathcal{D})$ is
infinite there must be some state $s$ of $\mathcal{D}$ such that

  * •

there is a word $x\in\Sigma^{*}$ which takes $\mathcal{D}$ from its initial
state to $s$,

  * •

there is a nonempty word $y\in\Sigma^{*}$ which takes $\mathcal{D}$ from $s$
to itself, and

  * •

there is a word $z\in\Sigma^{*}$ which takes $\mathcal{D}$ from $s$ to an
accepting state.

We can find $x,y,z\in\Sigma^{*}$ as above with $|x|,|y|,|z|\leq|\mathcal{D}|$,
in time polynomial in $|\mathcal{D}|$. Then we have $xy^{n}z\in
L(\mathcal{D})$ for any $n\in\mathbb{N}$. We form a probabilistic algorithm
$S$ which acts as follows: it prints $x$, then picks an integer uniformly at
random from $[0,N-1]$ and prints that many copies of $y$, before finally
printing $z$. Clearly the output of $S$ is a uniform sample from a subset of
$L(\mathcal{D})$ of size $N$. Constructing $S$ takes time polynomial in
$|\mathcal{D}|$ (as this bounds the sizes of $x$, $y$, and $z$) and $\log N$,
and $S$ runs in expected time bounded by a fixed polynomial in these values.

*

######  Proof D.4.

Prune $\mathcal{D}$ and compute the path counts $p_{v}$ as in Lemma 4.1. To
every edge $(u,v)$ in $\mathcal{D}$ assign the weight $p_{v}/p_{u}$. It is
clear that at every vertex the sum of the weights of the outgoing edges is 1
(unless the vertex is a sink). We prove by induction along reverse topological
order that treating these weights as transition probabilities, starting from
any state $u$ and talking a random walk until a sink is reached we obtain a
uniform distribution over all paths from $u$ to a sink. If $u$ is a sink this
holds trivially. If $u$ has a nonempty set of children $S$, then by the
inductive hypothesis for every $v\in S$ starting a walk at $v$ gives a uniform
distribution over the $p_{v}$ paths from $v$ to a sink. Therefore the
probability of following any such path starting at $u$ is
$(p_{v}/p_{u})\cdot(1/p_{v})=1/p_{u}$. So the result holds by induction. In
particular, if we start from the initial state we obtain a uniform
distribution over all paths to a sink, and thus a uniform distribution over
$L(\mathcal{D})$. Since all probabilities are rational with denominators
bounded by ${|\Sigma|}^{|\mathcal{D}|}$, this walk can be performed by a
probabilistic algorithm $S$ of size polynomial in $|\mathcal{D}|$, with
expected time bounded by a fixed polynomial in $|\mathcal{D}|$. Then $S$
returns a uniform sample from $L(\mathcal{D})$, and it can be constructed in
time polynomial in $|\mathcal{D}|$.

*

######  Proof D.5.

We prove this for $\mathcal{N}_{1}$ — the other case is analogous. As shown in
[14], the problem of determining $|L(\mathcal{M})\cap\Sigma^{m}|$ given an NFA
$\mathcal{M}$ over an alphabet $\Sigma$ and $m\in\mathbb{N}$ in unary is
$\mathsf{\\#P}$-complete. We give a polynomial-time (Cook) reduction from this
problem to checking feasibility of a CI instance in $\mathcal{N}_{1}$.

As noted in [14], we can in polynomial time (in $m$, which is acceptable since
$m$ is given in unary) construct an NFA $\mathcal{M^{\prime}}$ such that
$|L(\mathcal{M^{\prime}})|=|L(\mathcal{M})\cap\Sigma^{m}|$. Then we construct
the trivial DFA $\mathcal{T}$ accepting all of $\Sigma^{*}$, and consider the
CI instances $\mathcal{C}_{N}=(\mathcal{M^{\prime}},\mathcal{T},0,1/N)$.
Clearly for these instances we have $I=A=L(\mathcal{M^{\prime}})$. By Theorem
3.1, $\mathcal{C}_{N}$ is feasible iff
$|L(\mathcal{M})\cap\Sigma^{m}|=|L(\mathcal{M^{\prime}})|\geq N$, and since
$\mathcal{C}_{N}\in\mathcal{N}_{1}$ for any $N\in\mathbb{N}$ we can determine
whether this is the case. Since
$|L(\mathcal{M})\cap\Sigma^{m}|\leq|\Sigma|^{m}$, using binary search we can
find the exact value of $|L(\mathcal{M})\cap\Sigma^{m}|$ with polynomially-
many such queries.

*

######  Proof D.6.

We prove this for $\mathcal{P}_{1}$, the other case being similar. Given a PFA
$\mathcal{A}$ with cut-point $p$ over an alphabet $\Sigma$ with at least two
symbols, determining whether the language of $\mathcal{A}$ is empty (i.e.
whether it accepts no words with probability greater than $p$) is undecidable
[17, 9]. For any $N>0$, we can construct a PFA $\mathcal{A^{\prime}}$ by
adding new states and deterministic transitions to $\mathcal{A}$ so that there
are exactly $N$ words taking $\mathcal{A^{\prime}}$ from its initial state to
the initial state of $\mathcal{A}$, and any word which does not have one of
these as a prefix causes $\mathcal{A^{\prime}}$ to reject with probability 1.
Then $L(\mathcal{A^{\prime}})$ is $L(\mathcal{A})$ with one of the $N$
prefixes added to each word. Therefore $|L(\mathcal{A^{\prime}})|\geq N$ iff
$L(\mathcal{A})\neq\emptyset$, and so it is undecidable to determine whether
the language of a PFA has at least $N$ elements.

Constructing the trivial DFA $\mathcal{T}$ accepting all of $\Sigma^{*}$, the
CI instance $\mathcal{C}=(\mathcal{A},\mathcal{T},0,1/N)$ satisfies
$I=A=L(\mathcal{A})$. By Theorem 3.1, $\mathcal{C}$ is feasible iff
$|L(\mathcal{A})|\geq N$. Since checking this latter condition is undecidable,
so is determining feasibility of $\mathcal{P}_{1}$-instances.

*

######  Proof D.7.

Recall that the algorithm in Lemma 4.1 detected accepting cycles by finding
words $x,y,z$ taking the automaton to some state $s$, from $s$ to $s$ along at
least one transition, and to an accepting state respectively. If we impose the
additional constraint $|x|,|y|,|z|\leq n$, then we can check the existence of
such words with a single SAT query. So to test whether $L(\mathcal{S})$ is
infinite, we use one query for each $n\leq D$: since $D$ is the diameter, we
are guaranteed to find an accepting cycle if one exists. Thus if any query is
satisfiable, we return $\infty$.

If instead all the queries fail, then all words in $L(\mathcal{S})$ have
length at most $D$. So the SAT query $\phi$ for accepting paths of length at
most $D$ in fact matches every accepting path. Models of this formula then
correspond to accepting words if we project onto the input variables (i.e.
ignore the values of the variables which encode states). Therefore
$|L(\mathcal{S})|$ is equal to the number of models of $\phi$ after
projection. The general problem of counting models of a propositional formula
(even without projection) is $\mathsf{\\#P}$-complete, but using the SAT
solver we can get probabilistic bounds. An approximate model counter such as
$\mathsf{ApproxMC}$ [6] can return an estimate of the number of models of
$\phi$ which is accurate to within a factor of $1+\tau$ with probability at
least $1-\delta$. In fact $\mathsf{ApproxMC}$ can be easily modified to do
projection counting (see [7]), giving us the required estimate of
$|L(\mathcal{S})|$.

The first stage of this process clearly takes time polynomial in
$|\mathcal{S}|$ and $D$ relative to the oracle. $\mathsf{ApproxMC}$ runs in
time polynomial in $|\phi|=O(D|\mathcal{S}|)$, $1/\tau$, and $\log(1/\delta)$
relative to the oracle, so this procedure does as well.

*

######  Proof D.8.

We look for an accepting cycle using the method in Lemma 6.1. One will be
found since $|L(\mathcal{Y})|$ is infinite, and then we can pump it to get $N$
different words just as in Lemma 4.1.

*

######  Proof D.9.

As noted in Lemma 6.1, since the language is finite every word in it has
length at most $D$. Constructing the formula $\phi$ from that lemma, once we
project onto the input variables there is a one-to-one correspondence between
accepting words and models of $\phi$. So we need to almost-uniformly generate
projected models of a propositional formula. We use an almost-uniform
generator as described above, whose runtime will be polynomial in
$|\phi|=O(D|\mathcal{Y}|)$ and $1/\tau$ relative to the oracle.

*

######  Proof D.10.

The procedure begins by deriving the symbolic representations of $\mathcal{A}$
and $\mathcal{B}$ (the product of $\mathcal{I}$ and the complement of
$\mathcal{A}$). Next we estimate $|A|=|L(A)|$ and $|I|=|L(\mathcal{I})|$ using
Lemma 6.1 with a confidence of $(1-\delta)^{1/2}$. Then with probability at
least $1-\delta$, both these estimates are within a factor of $1+\tau$ of the
true values. We assume this is the case for the rest of the proof, making no
guarantees otherwise. We now break into the same cases as Theorem 4.2, using
our estimates $E_{A}$ and $E_{I}$ of $|A|$ and $|I|$ respectively.

  1. (A)

$E_{A}=\infty$: In this case we must have $|A|=\infty$. We proceed as in case
(A) of Theorem 4.2, but using Lemma 6.1 with $N=\left\lceil
1/\rho\right\rceil$ in place of Lemma 4.1 to obtain a $(0,\rho)$-improviser.

  2. (B)

$1/\rho\leq E_{A}<\infty$: Then $1/\rho(1+\tau)\leq E_{A}/(1+\tau)\leq|A|$. We
proceed as in case (B) of Theorem 4.2, using Lemma 6.1 in place of Lemma 4.1.
Since we are using an almost-uniform generator instead of a uniform one, some
words could have probability as high as $(1+\tau)/|A|\leq(1+\tau)^{2}\rho$,
and so this gives us a $(0,(1+\tau)^{2}\rho)$-improviser.

  3. (C)

$(1-\epsilon)/\rho\leq E_{A}<1/\rho$ and $E_{I}=\infty$: Then
$(1-\epsilon)/\rho(1+\tau)\leq E_{A}/(1+\tau)\leq|A|$, and $|I|=\infty$. We
proceed along the same lines as case (C) of Theorem 4.2. We use Lemma 6.1 as
in the previous case to generate a probabilistic algorithm $S$ almost-
uniformly sampling from $L(\mathcal{A})$. Defining $M=\left\lceil(1/\rho-
E_{A})/(1+\tau)\right\rceil$, we have $\infty=|L(\mathcal{B})|>M\geq 1$. We
can use Lemma 6.1 in place of Lemma 4.1 to get a probabilistic algorithm
$S^{\prime}$ uniformly sampling from a subset of $L(\mathcal{B})$ of size $M$.
Let $G$ be a probabilistic algorithm which with probability $\rho E_{A}$
executes $S$, and otherwise executes $S^{\prime}$. Then since
$L(\mathcal{A})=A$ and $L(\mathcal{B})=I\setminus A$ are disjoint, every word
generated by $G$ has probability either at most $(\rho
E_{A})\cdot(1+\tau)/|A|\leq(1+\tau)^{2}\rho$ (if it is in $A$) or at most
$(1-\rho E_{A})/M=(1-\rho E_{A})/\left\lceil(1/\rho-
E_{A})/(1+\tau)\right\rceil=(1-\rho E_{A})/\left\lceil(1-\rho
E_{A})/(1+\tau)\rho\right\rceil\leq(1+\tau)\rho$ (if it is in $I\setminus A$).
Also $G$ outputs a member of $A$ with probability $\rho E_{A}\geq 1-\epsilon$,
so $G$ is an $(\epsilon,(1+\tau)^{2}\rho)$-improviser and we return it.

  4. (D)

$(1-\epsilon)/\rho\leq E_{A}<1/\rho\leq E_{I}<\infty$: Then
$(1-\epsilon)/\rho(1+\tau)\leq E_{A}/(1+\tau)\leq|A|$, and $1/\rho(1+\tau)\leq
E_{I}/(1+\tau)\leq|I|$. As in the previous case, use Lemma 6.1 to produce a
probabilistic algorithm $S$ almost-uniformly sampling from $L(\mathcal{A})$.
Since $L(\mathcal{I})$ is finite, we can use the same technique to get a
probabilistic algorithm $S^{\prime}$ almost-uniformly sampling from
$L(\mathcal{I})$. Let $G$ be a probabilistic algorithm which with probability
$1-\epsilon$ executes $S$, and otherwise executes $S^{\prime}$. Then $G$
generates each $w\in A$ with probability at most
$[(1-\epsilon)\cdot(1+\tau)/|A|]+[\epsilon\cdot(1+\tau)/|I|]\leq(1+\tau)^{2}\rho+(1+\tau)^{2}\epsilon\rho=(1+\tau)^{2}(1+\epsilon)\rho$,
and each $w\in I\setminus A$ with probability at most
$\epsilon\cdot(1+\tau)/|I|\leq(1+\tau)^{2}\epsilon\rho$. Furthermore $G$
outputs a member of $A$ with probability at least $1-\epsilon$, so $G$ is an
$(\epsilon,(1+\tau)^{2}(1+\epsilon)\rho)$-improviser and we return it.

  5. (E)

$E_{I}<1/\rho$ or $E_{A}<(1-\epsilon)/\rho$: It is possible that the problem
is not $(\epsilon,\rho/(1+\tau))$-feasible, so the procedure returns $\bot$.

In the cases where an almost-uniform generator is used, there is some constant
probability that the generator will fail. If that happens, the improviser just
runs the generator again: since the failure probability is a fixed constant,
so is the expected number of repetitions needed, and thus the expected runtime
of the improviser is just multiplied by an overall constant.

Now if $\mathcal{C}$ is $(\epsilon,\rho/(1+\tau))$-feasible, by Theorem 3.1 we
have $1/\rho\leq|I|/(1+\tau)\leq E_{I}$ and
$(1-\epsilon)/\rho\leq|A|/(1+\tau)\leq E_{A}$ with probability at least
$1-\delta$. So with probability $1-\delta$ case (E) does not happen, and the
procedure returns an $(\epsilon,(1+\tau)\rho)$-improviser.


# A finitary adjoint functor theorem

Jiří Adámek  Department of Mathematics, Faculty of Electrical Engineering
Czech Technical University in Prague, Czech Republic
Institute for Theoretical Computer Science, Technical University of
Braunschweig, Germany<EMAIL_ADDRESS>and  Lurdes Sousa  University of
Coimbra, CMUC, Department of Mathematics, Portugal
Polytechnic of Viseu, ESTGV, Portugal<EMAIL_ADDRESS>To the memory of Věra
Trnková

###### Abstract.

Graduated locally finitely presentable categories are introduced, examples
include categories of sets, vector spaces, posets, presheaves and boolean
algebras. A finitary functor between graduated locally finitely presentable
categories is proved to be a right adjoint if and only if it preserves
countable limits. For endofunctors on vector spaces or pointed sets even
countable products are sufficient. Surprisingly, for set functors there is a
single exception of a (trivial) finitary functor preserving countable products
but not countable limits.

###### Key words and phrases:

Locally finitely presentable categories, finitary functors

###### 2010 Mathematics Subject Classification:

18A22, 18A35, 18A40, 18B05

Supported by the Grant Agency of the Czech Republic: Grant 22-02964S

Partially supported by the Centre for Mathematics of the University of Coimbra
\- UIDB/00324/2020, funded by the Portuguese Government through FCT/MCTES

##  1\. Introduction

A functor between locally presentable categories is a right adjoint iff it is
accessible and preserves limits [1, Thm. 1.66]. We introduce a wide class of
locally finitely presentable categories, called graduated, and prove that a
finitary functor between them is a right adjoint iff it preserves countable
limits. Examples of graduated categories include categories of

  1. (1)

sets, posets, boolean algebras, $M$-sets for finite monoids $M$, and left
modules over finite semirings;

  2. (2)

vector spaces and relational structures of finitary signatures.

Our paper has been inspired by Tendas who proved the following result for
locally finitely presentable categories having (a) only countable many
finitely presentable objects (up to isomorphism) and (b) finite hom-sets for
them: a finitary functor between such categories preserves limits iff it
preserves countable limits [2, Remark 2.10]. The examples in (1) above satisfy
these conditions, those of (2) do not in general. Our proof is entirely
different from that of Tendas.

A second inspiration of our paper is Trnková’s result concerning the question
when functors preserving products automatically preserve limits [4]. Can one
reduce countable limits to countable products? The answer is affirmative for
endofunctors of categories such as vector spaces or pointed sets. Surprisingly
such a reduction is almost, but not completely, possible for set functors.
Indeed, the functor

$C_{01}\text{ defined by }\emptyset\mapsto\emptyset\;\;\text{and}\;\;X\mapsto
1\;\;\text{for all $X\not=\emptyset$}$

preserves all products but not countable limits. This is the single exception:
a finitary set functor preserving countable products but not countable limits
is naturally isomorphic to $C_{01}$.

##  2\. Graduated categories

In this section graduated locally finitely presentable categories are
introduced. In the subsequent section we prove that a finitary functor between
graduated categories is a right adjoint iff it preserves countable limits.

Recall that a codirected poset is a poset in which every finite subset has a
lower bound. Limits of diagrams indexed by codirected posets are called
codirected limits.

######  Definition 2.1.

A category has finitary codirected limits if every codirected limit cone
$\pi_{i}\colon L\to L_{i}\;(i\in I)$ has the following property:

For every monomorphism $q\colon Q\to L$ with $Q$ finitely presentable some
$\pi_{i}\cdot q$ is monic.
---

Recall that a concrete category is a category $\mathcal{K}$ equipped with a
faithful (forgetful) functor $U\colon\mathcal{K}\to\mathcal{S}et$.

######  Lemma 2.2.

A concrete category with the forgetful functor preserving codirected limits
and monomorphisms has finitary codirected limits whenever the underlying sets
of finitely presentable objects are finite.

###### Proof.

Let $U\colon\mathcal{K}\to\mathcal{S}et$ preserve codirected limits and
monomorphisms. Given a finitely presentable object $Q$, for every monomorphism
$m\colon Q\to L$, where $\pi_{i}\colon L\to D_{i}\;(i\in I)$ is a codirected
limit, consider the monomorphism $Um\colon UQ\to UL$ defining a finite subset
of $UL$. Since $(U\pi_{i})_{i\in I}$ is a limit cone, it is collectively
monic. Thus for every distinct pair $x\not=y$ in $Um[UQ]$ there exists
$i_{0}\in I$ with $U\pi_{i_{0}}(x)\not=U\pi_{i_{0}}(y)$. Since the number of
such pairs is finite, $i_{0}$ can be chosen independent of $x,y$. In other
words, $U(\pi_{i_{0}}\cdot m)$ is monic. Since $U$ is faithful, it follows
that $\pi_{i_{0}}\cdot m$ is monic. ∎

######  Examples 2.3.

The following categories satisfy the conditions of Lemma 2.2, thus they have
finitary codirected limits:

  1. (1)

$\mathcal{S}et$ and $\mathcal{S}et_{p}$ (pointed sets).

  2. (2)

The presheaf category $\mathcal{S}et^{\mathcal{A}^{op}}$, $\mathcal{A}$
finite. Consider $U\colon\mathcal{S}et^{\mathcal{A}^{op}}\to\mathcal{S}et$
given by
$U(\mathcal{A}^{op}\xrightarrow{A}\mathcal{S}et)=\coprod_{s\in\mathcal{A}}As$.
Since codirected limits commute in $\mathcal{S}et$ with coproducts, they are
preserved by $U$.

  3. (3)

$\mathcal{P}os$, the category of posets.

  4. (4)

$\mathcal{B}ool$, the category of boolean algebras.

  5. (5)

$\Omega$-$\mathcal{R}el$, the category of relational structures of a signature
$\Omega=(\Omega_{n})_{n\in\mathds{N}}$. Objects are pairs $A=(X,(\omega_{A}))$
consisting of a set $X$ with relations $\omega_{A}\subseteq X^{n}$ for all
$\omega\in\Omega_{n}$. Finitely presentable objects are such that both $X$ and
$\coprod_{\omega\in\Omega}\omega_{A}$ are finite sets.

  6. (6)

$M$-$Set$ ($M$ a finite monoid), the category of sets with an action of $M$.

  7. (7)

$S$-$\mathcal{M}od$ ($S$ a finite semiring), the category of left modules over
$S$.

######  Proposition 2.4.

For every field $K$ the category $K$-$\mathcal{V}ec$ of vector spaces has
finitary codirected limits.

###### Proof.

Let $\pi_{i}\colon L\to L_{i}\;(i\in I)$ be a limit cone of a codirected
diagram $D$. We prove that given a subspace of $L$ with basis
$\\{x_{1},\,\dots,\,x_{n}\\}$, there exists $i\in I$ such that the vectors
$\pi_{i}(x_{1}),\,\dots,\,\pi_{i}(x_{n})$ are linearly independent in $L_{i}$.
We proceed by induction.

If $n=1$, then $x_{1}\not=0$. This implies, since $(\pi_{i})_{i\in I}$ is a
collectively monic cone, that $\pi_{i}(x_{1})\not=0$ for some $i$.

If the statement holds for $n$, we prove it for $n+1$. Since $x_{n+1}\not=0$,
we have $j\in I$ with $\pi_{j}(x_{n+1})\not=0$. Thus $\pi_{i}(x_{n+1})\not=0$
for all $i\leq j$. By induction hypothesis (and since $I$ is codirected) we
can assume that our $j$ is chosen so that
$\pi_{j}(x_{1}),\,\dots,\,\pi_{j}(x_{n})$ are linearly independent. We prove
that some $i\leq j$ makes $\pi_{i}(x_{1}),\,\dots,\,\pi_{i}(x_{n+1})$ linearly
independent. Assuming the contrary, we derive a contradiction.

There is a nontrivial linear combination

$\sum_{k=1}^{n+1}\lambda_{k}\pi_{j}(x_{k})=0.$

Since $\pi_{j}(x_{1}),\,\dots,\,\pi_{j}(x_{n})$ are linearly independent, this
implies $\lambda_{n+1}\not=0$. For $\mu_{k}=-\lambda_{k}/\lambda_{n+1}$ we get

$\pi_{j}(x_{n+1})=\sum_{k=1}^{n}\mu_{k}\pi_{j}(x_{k}).$

For every $i\in I$ with $i\leq j$ there is, analogously, a possibility to
express $\pi_{i}(x_{n+1})$ as a linear combination as follows

$\pi_{i}(x_{n+1})=\sum_{k=1}^{n}\sigma_{k}\pi_{i}(x_{k}).$

From $\pi_{j}=d_{ij}\cdot\pi_{i}$ (where $d_{ij}\colon L_{i}\to L_{j}$ is the
connecting morphism of our diagram $D$), this yields

$\pi_{j}(x_{n+1})=\sum_{k=1}^{n}\sigma_{k}\pi_{j}(x_{k}).$

Thus

$\sum_{k=1}^{n}(\mu_{k}-\sigma_{k})\pi_{j}(x_{k})=0.$

This implies $\mu_{k}=\sigma_{k}$ for all $k$, since the vectors
$\pi_{j}(x_{1}),\,\dots,\,\pi_{j}(x_{n})$ are linearly independent.

Thus we have proved that for every $i\leq j$ we have

$\pi_{i}(x_{n+1})=\sum_{k=1}^{n}\mu_{k}\pi_{i}(x_{k})=\pi_{i}\left(\sum_{k=1}^{n}\mu_{k}x_{k}\right).$

Since $I$ is codirected, the shortened diagram of all $L_{i}$, $i\leq j$, has
the limit cone $(\pi_{i})_{i\leq j}$. This implies that in $L$ we have

$x_{n+1}=\sum_{k=1}^{n}\mu_{k}x_{k}.$

This is the desired contradiction since $x_{1},\,\dots,\,x_{n+1}$ are linearly
independent. ∎

######  Examples 2.5.

(1) The category $\mathcal{A}b$ of abelian groups does not have finitary
codirected limits. Consider the $\omega^{\mathrm{op}}$-chain of groups
$\mathds{Z}_{2^{k}}=\mathds{Z}/\text{mod}\,{2^{k}}\mathds{Z}$ for
$k\in\mathds{N}$ with connecting morphisms given by the canonical quotients
$\mathds{Z}_{2^{m}}\to\mathds{Z}_{2^{n}}:p\mapsto p\,\text{mod}\,2^{n}$, for
$m\geq n$. Its limit is $\mathds{Z}$ and the limit cone is given by the
canonical quotients. Although $\mathds{Z}$ is finitely presentable, none of
the limit maps is monic.

(2) Analogously for the category $\mathcal{U}n$ of unary algebras on one
operation: we can view the above chain as an $\omega^{\mathrm{op}}$-chain of
unary algebras:

${1}$${2}$${\bullet}$${3}$${1}$${\dots}$${0}$${0}$

This shows that $\mathcal{U}n$ does not have finitary codirected limits.

######  Definition 2.6.

A locally finitely presentable category is graduated if it has finitary
codirected limits and to every finitely presentable object $A$ a natural
number

$\text{gr\hskip 0.42677pt}A$

(the grade) is assigned satisfying the following:

Every (proper) subobject and every (proper) strong quotient of $A$ is finitely
presentable and has grade at most (smaller than, resp.) $\text{gr\hskip
0.42677pt}A$.
---

######  Remark 2.7.

In particular, isomorphic finitely presentable objects have the same grade.
Moreover, if $A$ and $B$ are finitely presentable objects of the same grade,
every monomorphism and every strong epimorphism between them is invertible.

######  Examples 2.8.

The following categories are graduated.

  1. (1)

$\mathcal{S}et$ and $\mathcal{S}et_{p}$. Put

$\text{gr\hskip 0.42677pt}A=\text{card}A.$

  2. (2)

$\mathcal{S}et^{\mathcal{A}^{\mathrm{op}}}$ for $\mathcal{A}$ finite. Put

$\text{gr\hskip 0.42677pt}A=\sum_{s\in\mathcal{A}}\text{card}As.$

  3. (3)

$\mathcal{P}os$. Put

$\text{gr\hskip 0.42677pt}A=\text{number of comparable pairs}.$

Indeed, every proper subposet of a finite poset $A$ has clearly less
comparable pairs than $A$. Moreover, given a strong epimorphism $e\colon A\to
B$, every comparable pair in $B$ has the form $b\leq b^{\prime}$ for some
sequence $a_{0},\dots,\,a_{2n}$ such that $b=e(a_{0}),\,b^{\prime}=e(a_{2n})$
and for each $k=1,\dots,n$ we have

$a_{2k-2}\leq a_{2k-1}\,\text{ and }\,e(a_{2k-1})=e(a_{2k}).$

In case $A$ and $B$ have the same number of comparable pairs, it is easy to
see that $e$ is bijective, and $b\leq b^{\prime}$ in $B$ iff
$b=e(a_{0}),\,b^{\prime}=e(a_{1})$ for $a_{0}\leq a_{1}$ in $A$. Thus $e$ is
an isomorphism.

  4. (4)

$\mathcal{B}ool$. Every finitely presentable boolean algebra is finite and we
put

$\text{gr\hskip 0.42677pt}A=\text{card}\,A.$

  5. (5)

$\Omega$-$\mathcal{R}el$. For a relational structure $A=(X,(\omega_{A}))$ put

$\text{gr\hskip
0.42677pt}A=\text{card}\,X+\sum_{\omega\in\Omega}\text{card}\,\omega_{A}.$

If $B$ is a proper subobject of $A$, and has the same elements, then
$\omega_{B}\not\subseteq\omega_{A}$ for some $\omega$, thus $\text{gr\hskip
0.42677pt}B<\text{gr\hskip 0.42677pt}A$. This inequality also holds if $B$ has
less elements than $A$. The argument for proper quotients $B$ is similar: a
quotient $e\colon A\twoheadrightarrow B$ whose underlying map is bijective is
indeed an isomorphism in $\Omega$-$\mathcal{R}el$.

  6. (6)

$M$-$\mathcal{S}et$ for all finite monoids $M$. Every finitely presentable
$M$-set $A$ is finite, and we put

$\text{gr\hskip 0.42677pt}A=\text{card}A.$

In contrast, $M$-$\mathcal{S}et$ is not graduated for the monoid
$M=(\mathds{N},+,0)$: the category $M$-$\mathcal{S}et\cong\mathcal{U}n$ does
not have finitary codirected limits (Example 2.5).

  7. (7)

$S$-$\mathcal{M}od$ for every finite semiring $S$: here also $\text{gr\hskip
0.42677pt}A=\text{card}A.$

  8. (8)

$K$-$\mathcal{V}ec$. Put

$\text{gr\hskip 0.42677pt}A=\text{dim}A.$

##  3\. The finitary adjoint functor theorem

Recall that every locally finitely presentable category has a (strong epi,
mono)-factorization system of morphisms ([1, Prop. 1.61]).

######  Lemma 3.1.

Every object $K$ of a graduated locally finitely presentable category is the
directed colimit of the diagram of all its finitely presentable subobjects.

###### Proof.

Let $\mathcal{K}_{fp}$ denote the full subcategory of $\mathcal{K}$ on all
finitely presentable objects. Since our category $\mathcal{K}$ is locally
finitely presentable, $K$ is the canonical filtered colimit of the diagram

$D_{K}\colon\mathcal{K}_{fp}\downarrow
K\to\mathcal{K},\;\;(A\xrightarrow{a}K)\mapsto A$

(see [1, Prop. 1.22]). Let $m_{a}\cdot a^{\prime}=a$ be a (strong epi,
mono)-factorization for each $a\colon A\to K$:

${A}$${B}$${{A^{\prime}}}$${{B^{\prime}}}$${K}$$\scriptstyle{f^{\prime}}$$\scriptstyle{m_{a}}$$\scriptstyle{m_{b}}$$\scriptstyle{a^{\prime}}$$\scriptstyle{f}$$\scriptstyle{b^{\prime}}$

For every connecting morphism $f\colon(A,a)\to(B,b)$ of $D_{K}$ the diagonal
fill-in property yields a corresponding monomorphism $f^{\prime}\colon
A^{\prime}\to B^{\prime}$.

We thus obtain a diagram $D^{\prime}_{K}$ of objects $A^{\prime}$ and
connecting morphisms $f^{\prime}$. For each finitely presentable object $A$
the strong epimorphism $a^{\prime}$ proves that $A^{\prime}$ is finitely
presentable (since $\mathcal{K}$ is graduated). Thus $D^{\prime}_{K}$ is a
directed diagram of finitely presentable subobjects of $K$.

Conversely, every finitely presentable subobject $m^{\prime}\colon
A^{\prime}\to A$ has the form $m_{a}$ for $a=m^{\prime}$. Thus
$D^{\prime}_{K}$ is the diagram of all finitely presentable subobjects of $K$:
Its colimit is, obviously, $m_{a}\colon A^{\prime}\to K$ for
$(A,a)\in\mathcal{K}_{fp}\downarrow\mathcal{K}$. ∎

######  Remark 3.2.

Let $I$ be a countably codirected poset: every countable subset has a lower
bound.

(1) Given a decomposition $I=\bigcup_{k\in\mathds{N}}I_{k}$, some $I_{k}$ is
initial, i.e. every element of $I$ lies over some element of $I_{k}$. Indeed,
assuming the contrary, for each $k$ we have a counter-example $i_{k}\in I$ not
majorizing elements of $I_{k}$. The countable set
$\\{i_{k}\\}_{k\in\mathds{N}}$ has a lower bound $j\in I$. But this is a
contradiction: $j\not\in I_{k}$ for any $k$.

(2) Given a diagram $D\colon I\to\mathcal{K}$, for every initial subset
$J\subseteq I$ the limits of $D$ and of its restriction $D/J\colon
J\to\mathcal{K}$, are the same. More precisely: the limit cone $\pi_{i}\colon
L\to Di\;(i\in I)$ of $D$ yields a limit cone $\pi_{j}\colon L_{j}\to
Dj\;(j\in J)$ of $D/J$, and vice versa.

######  Theorem 3.3.

Let $F\colon\mathcal{K}\to\mathcal{L}$ be a finitary functor between locally
finitely presentable categories with $\mathcal{K}$ graduated. Then $F$ is a
right adjoint if and only if it preserves countable limits.

###### Proof.

(1) By the Adjoint Functor Theorem [1, Thm. 1.66], it is sufficient to prove
that $F$ preserves limits. We prove below that it preserves countably
codirected limits. This is sufficient: the limit of every diagram
$D\colon\mathcal{D}\to\mathcal{K}$ is a countably codirected limit of limits
of diagrams $D/\mathcal{D}^{\prime}$, where $\mathcal{D}^{\prime}$ ranges over
countable subcategories of $\mathcal{D}$.

(2) Let $I$ be a countably codirected poset and $D=(D_{i})_{i\in I}$ a diagram
in $\mathcal{K}$ with a limit cone $(\pi_{i})_{i\in I}$:

${L}$${{D_{i}}}$${{D_{j}}}$$\scriptstyle{d_{ij}}$$\scriptstyle{\pi_{i}}$$\scriptstyle{\pi_{j}}$$\scriptstyle{(i\leq
j\text{ in }I)}$$\scriptstyle{\dots}$

For every cone in $\mathcal{L}$

${Q}$${{FD_{i}}}$${{FD_{j}}}$$\scriptstyle{Fd_{ij}}$$\scriptstyle{q_{i}}$$\scriptstyle{q_{j}}$$\scriptstyle{\dots}$

we prove that a unique factorization through $(F\pi_{i})$ exists.

We can restrict ourselves to cones with $Q$ finitely presentable in
$\mathcal{L}$. Indeed, since $\mathcal{L}_{fp}$ is a dense subcategory of
$\mathcal{L}$, that result then extends to all cones of $FD$.

(2a) Existence. First we show that for every morphism $q\colon Q\to FK$ with
$K\in\mathcal{K}$ and $Q$ finitely presentable there is a least subobject
$m\colon M\rightarrowtail K$ with $M$ finitely presentable such that $q$
factorizes through $Fm$. For that, we express $K$ as a directed colimit of all
its finitely presentable subobjects (Lemma 3.1) and use that $F$ preserves
that colimit. Thus $q$ factorizes through $Fm\colon FM\to FK$ for some
subobject $m\colon M\rightarrowtail K$ with $M\in\mathcal{K}_{fp}$. We claim
that there exists a least such subobject: one contained in every subobject
$m^{\prime}\colon M^{\prime}\rightarrowtail K$ with
$M^{\prime}\in\mathcal{K}_{fp}$ such that $q$ factorizes through
$Fm^{\prime}$.

Indeed, first choose an arbitrary finitely presentable subobject $m_{0}\colon
M_{0}\rightarrowtail K$ such that $q=Fm_{0}\cdot u_{0}$ for some $u_{0}\colon
Q\to FM_{0}$. If $m_{0}$ is not the least one, then there exists a finitely
presentable subobject $m\colon M\rightarrowtail K$ such that

$q=Fm\cdot u\text{ (for some $u$) and }m_{0}\not\subseteq m.$

Form the intersection $m_{1}$ of $m_{0}$ and $m$ as follows:

${{M_{1}}}$${{M_{0}}}$${M}$${K}$$\scriptstyle{m^{\prime}_{0}}$$\scriptstyle{m^{\prime}}$$\scriptstyle{m_{0}}$$\scriptstyle{m}$$\scriptstyle{m_{1}}$

Since $F$ preserves this pullback and $Fm_{0}\cdot u_{0}=Fm\cdot u$, we see
that $q$ factorizes through $Fm_{1}$:

${Q}$${{FM_{1}}}$${{FM_{0}}}$${FM}$${FK}$$\scriptstyle{Fm^{\prime}_{0}}$$\scriptstyle{Fm^{\prime}}$$\scriptstyle{Fm_{0}}$$\scriptstyle{Fm}$$\scriptstyle{Fm_{1}}$$\scriptstyle{\exists!}$$\scriptstyle{u_{0}}$$\scriptstyle{u}$

Since $m_{0}\not\subseteq m_{1}$, we know that $m^{\prime}_{0}$ is not
invertible. Therefore, $M_{1}$ is a proper subobject of $M_{0}$ and we get

$\text{gr\hskip 0.42677pt}M_{1}<\text{gr\hskip 0.42677pt}M_{0}.$

We now iterate this procedure: either $M_{1}$ is the desired least subobject,
or we find $M_{2}$ with $\text{gr\hskip 0.42677pt}M_{2}<\text{gr\hskip
0.42677pt}M_{1}$, etc. After less than $\text{gr\hskip 0.42677pt}M_{0}$ steps
we obtain the desired least subobject.

For each $i\in I$ let $m_{i}\colon M_{i}\to D_{i}$ be the least subobject with
$M_{i}$ finitely presentable such that

$q_{i}=Fm_{i}\cdot r_{i}\;\text{ for some }r_{i}\colon Q\to FM_{i}.$

Then the sets

$I_{n}=\\{i\in I;\,\text{gr\hskip 0.42677pt}M_{i}=n\\}$

fulfil $I=\displaystyle{\bigcup_{n\in\mathds{N}}I_{n}}$. By Remark 3.2, some
$I_{k}$ is initial in $I$. Thus the diagram $D_{0}=(D_{i})_{i\in I_{k}}$ has
the same limit as $D$.

Next we prove that each connecting morphism $d_{ij}\colon D_{i}\to
D_{j}\;(i\leq j\,\text{ in $I_{k}$})$ of $D_{0}$ restricts to a morphism
$m_{ij}\colon M_{i}\to M_{j}$. That is, we have a commutative square as
follows:

${{M_{i}}}$${{M_{j}}}$${Di}$${Dj}$$\scriptstyle{m_{i}}$$\scriptstyle{m_{j}}$$\scriptstyle{m_{ij}}$$\scriptstyle{d_{ij}}$

Let us form a (strong epi, mono)-factorization of $d_{ij}\cdot m_{i}$ on the
left:

${Q}$${{M_{i}}}$${{M_{j}}}$${{FM_{i}}}$${{FM_{j}}}$${M}$${FM}$${{D_{i}}}$${{D_{j}}}$${{FD_{i}}}$${{FD_{j}}}$$\scriptstyle{e}$$\scriptstyle{v}$$\scriptstyle{m_{j}}$$\scriptstyle{m}$$\scriptstyle{m_{i}}$$\scriptstyle{d_{ij}}$$\scriptstyle{Fd_{ij}}$$\scriptstyle{Fm_{i}}$$\scriptstyle{Fe}$$\scriptstyle{Fv}$$\scriptstyle{Fm_{j}}$$\scriptstyle{Fm}$$\scriptstyle{r_{j}}$$\scriptstyle{r_{i}}$$\scriptstyle{q_{j}}$

We will find $v$ making that diagram commutative. The right-hand diagram shows
that $q_{j}$ factorizes through $Fm$. This implies $m_{j}\leq m$ (by the
minimality of $m_{j}$). Therefore

$\text{gr\hskip 0.42677pt}M\geq\text{gr\hskip 0.42677pt}M_{j}=k.$

But the strong epimorphism $e\colon M_{i}\to M$ yields

$\text{gr\hskip 0.42677pt}M\leq\text{gr\hskip 0.42677pt}M_{i}=k,$

hence $\text{gr\hskip 0.42677pt}M=k$. Thus $m$ and $m_{j}$ represent the same
subobject of $D_{j}$: $m=m_{j}\cdot v$ for some isomorphism $v\colon M\to
M_{j}$. The desired morphism is

$m_{ij}=v\cdot e.$

Indeed, $m_{j}\cdot m_{ij}=m_{j}\cdot v\cdot e=m\cdot e=d_{ij}\cdot m_{i}$.
Moreover, since $e$ is a strong epimorphism, so is $m_{ij}$, and thus, since
$M_{i}$ and $M_{j}$ have the same grade, $m_{ij}$ is invertible $(i\leq
j\,\text{ in }I_{k})$ (Remark 2.7).

The codirected diagram $\hat{D}$ of objects $M_{i}$ and morphisms
$m_{ij}\;(i\leq j\,\text{ in }I_{k})$ has invertible connecting morphisms,
hence its limit (with invertible limit maps) is clearly absolute. Thus $F$
preserves it. The morphisms $r_{i}\colon Q\to FM_{i}$ form a cone of
$F\hat{D}$: in the right-hand diagram above the upper part commutes because
$Fm_{j}$ is monic, and by post-composing by $Fm_{j}$ one gets
$q_{j}=Fd_{ij}\cdot q_{i}$. If $\hat{\pi}_{i}\colon\hat{L}\to M_{i}\,(i\in
I_{k})$ is a limit of $\hat{D}$, we obtain a unique morphism

$r\colon Q\to F\hat{L}\,\text{ with }r_{i}=F\hat{\pi}_{i}\cdot r\;\;(i\in
I_{k}).$

The natural transformation from $\hat{D}$ to $D_{0}$ with components
$m_{i}\colon M_{i}\to D_{i}\,(i\in I_{k})$ yields (since $D$ and $D_{0}$ have
the same limit) a morphism $s\colon\hat{L}\to L$ with
$m_{i}\cdot\hat{\pi}_{i}=\pi_{i}\cdot s\;(i\in I_{k})$. The desired
factorization of $(q_{i})$ through $(F\pi_{i})$ is given by

$Fs\cdot r\colon Q\to FL.$

Indeed, for $i\in I_{k}$ we have $F\pi_{i}\cdot(Fs\cdot r)=Fm_{i}\cdot
F\hat{\pi}_{i}\cdot r=Fm_{i}\cdot r_{i}=q_{i}$.

(2b) Uniqueness. Given $u,v\colon Q\to FL$ merged by $F\pi_{i}$ for every
$i\in I$, we prove $u=v$. Form the directed colimit of all finitely
presentable subobjects $m\colon M\rightarrowtail L$ of $L$ (see Lemma 3.1).
Both $u$ and $v$ factorize through $Fm$ for one of these subobjects, since $F$
preserves that directed colimit and $Q\in\mathcal{K}_{fp}$. Let
$u^{\prime},\,v^{\prime}$ be the corresponding factorizations:

${Q}$${FL}$${{FD_{j}}}$${FM}$$\scriptstyle{v}$$\scriptstyle{u}$$\scriptstyle{u^{\prime}}$$\scriptstyle{v^{\prime}}$$\scriptstyle{F\pi_{j}}$$\scriptstyle{Fm}$

Since $\mathcal{K}$ is graduated and $M$ finitely presentable, there exists
$j\in I$ with $\pi_{j}\cdot m$ monic. Then from $F\pi_{j}\cdot u=F\pi_{j}\cdot
v$ we get $u^{\prime}=v^{\prime}$ (since $F(\pi_{j}\cdot m)$ is monic and
merges $u^{\prime}$ and $v^{\prime}$). That is, $u=v$, as required. ∎

######  Example 3.4.

Preservation of finite limits is not sufficient for being a right adjoint even
for finitary set functors. Indeed, consider the subfunctor

$H\hookrightarrow(-)^{\mathds{N}}$

assigning to every set $X$ the set $HX$ of all sequences $a\colon\mathds{N}\to
X$ that are eventually constant: there is $n\in\mathds{N}$ with $a(n)=a(m)$
for all $m\geq n$. Then $H$ clearly preserves finite products: a sequence in
$X\times Y$ is eventually constant iff both of its projections (to
$X^{\mathds{N}}$ and $Y^{\mathds{N}}$) are. $H$ also preserves equalizers.
However, $H$ does not preserve the product

$A=\prod_{n\in\mathds{N}}A_{n}\,\text{ where }A_{n}=\\{0,1,\dots,n\\}.$

Indeed, $HA_{n}$ contains the sequence $s_{n}=(0,1,\dots,n,n,n,\dots)$. Thus
$(s_{n})_{n\in\mathds{N}}\in\Pi_{n\in\mathds{N}}HA_{n}$. But no element of
$HA$ corresponds to $(s_{n})$.

##  4\. Absolute intersections

In categories such as $K$-$\mathcal{V}ec$ and $\mathcal{S}et_{p}$ finite
intersections are absolute limits (preserved by all functors). We prove this,
using ideas of Trnková [3] who proved that nonempty intersections in
$\mathcal{S}et$ are absolute (see Remark 4.4).

######  Definition 4.1.

A category $\mathcal{K}$ has absolute intersections provided that all
monomorphisms split, and for every intersection of monomorphisms $m$ and
$m^{\prime}$

(4.1)
${C}$${B}$${{B^{\prime}}}$${A}$$\scriptstyle{m^{\prime}}$$\scriptstyle{i^{\prime}}$$\scriptstyle{e^{\prime}}$$\scriptstyle{m}$$\scriptstyle{e}$$\scriptstyle{i}$

there exist splittings $e$ of $m$ and $e^{\prime}$ of $i^{\prime}$ with

(4.2) $e\cdot m^{\prime}=i\cdot e^{\prime}\colon B^{\prime}\to B.$

######  Proposition 4.2.

The pullback in the above definition is absolute.

###### Proof.

Given a functor $F\colon\mathcal{K}\to\mathcal{L}$ and a commutative square in
$\mathcal{L}$ as follows

(4.3)
${U}$${FB}$${{FB^{\prime}}}$${FA}$$\scriptstyle{u}$$\scriptstyle{u^{\prime}}$$\scriptstyle{Fm}$$\scriptstyle{Fm^{\prime}}$

we prove that the desired factorization of $(u,u^{\prime})$ through
$(Fi,Fi^{\prime})$ is

$v=Fe^{\prime}\cdot u^{\prime}\colon U\to FC.$

The uniqueness is clear since $Fi$ is monic. Our task is to verify that the
diagram below commutes:

${U}$${{FB^{\prime}}}$${FB}$${FC}$${{FB^{\prime}}}$$\scriptstyle{u}$$\scriptstyle{u^{\prime}}$$\scriptstyle{Fi}$$\scriptstyle{Fi^{\prime}}$$\scriptstyle{u^{\prime}}$$\scriptstyle{Fe^{\prime}}$

The left-hand triangle does:

$\begin{array}[]{rlr}Fi\cdot(Fe^{\prime}\cdot u^{\prime})&=Fe\cdot
Fm^{\prime}\cdot u^{\prime}&\text{by \eqref{eq:(2)}}\\\ &=Fe\cdot Fm\cdot
u&\text{by \eqref{eq:(3)}}\\\ &=u&\text{as $e\cdot
m=\mathrm{id}$.}\end{array}$

The right-hand triangle commutes because $Fm^{\prime}$ is monic, and we have

$\begin{array}[]{rlr}Fm^{\prime}\cdot u^{\prime}&=Fm\cdot u&\text{by
\eqref{eq:(3)}}\\\ &=Fm\cdot Fe\cdot Fm\cdot u&\text{as $e\cdot
m=\mathrm{id}$}\\\ &=Fm\cdot Fe\cdot Fm^{\prime}\cdot u^{\prime}&\text{by
\eqref{eq:(3)}}\\\ &=Fm\cdot Fi\cdot Fe^{\prime}\cdot u^{\prime}&\text{by
\eqref{eq:(2)}}\\\ &=Fm^{\prime}\cdot(Fi^{\prime}\cdot Fe^{\prime}\cdot
u^{\prime})&\text{by \eqref{eq:(1)}}.\end{array}$

∎

######  Examples 4.3.

(1) The category $K$-$\mathcal{V}ec$ has absolute intersections. Without loss
of generality we assume that in the pullback (4.1) the objects fulfil

$B\subseteq A,\,B^{\prime}\subseteq A\;\text{and}\;C=B\cap B^{\prime},$

and the morphisms are the inclusion maps. We decompose the spaces $B$ and
$B^{\prime}$ as follows:

$B=B_{0}\oplus C\;\text{ and }B^{\prime}=B^{\prime}_{0}\oplus C.$

Then $A$ has the following decomposition:

$A=A_{0}\oplus B_{0}\oplus B^{\prime}_{0}\oplus C.$

The desired splittings are as follows:

${C}$${{B_{0}\oplus C}}$${{B^{\prime}_{0}\oplus C}}$${{A_{0}\oplus B_{0}\oplus
B^{\prime}_{0}\oplus
C}}$$\scriptstyle{[0,\mathrm{id}]}$$\scriptstyle{[0,\mathrm{id},0,\mathrm{id}]}$

(2) The category $\mathcal{S}et_{p}$ has absolute intersections. Without loss
of generality we assume that, again, the morphisms in the pullback (4.1) are
inclusion maps. In particular, all four objects have the same specified
element $c\in C$. Define $e\colon(A,c)\to(B,c)$ and
$e^{\prime}\colon(B^{\prime},c)\to(C,c)$ by

$e(x)=\left\\{\begin{array}[]{ll}y&\text{if $y\in B$}\\\
c&\text{else}\end{array}\right.\hskip
42.67912pte^{\prime}(z)=\left\\{\begin{array}[]{ll}z&\text{if $z\in C$}\\\
c&\text{else}.\end{array}\right.$

These are the desired splittings.

######  Remark 4.4.

(1) We conclude that an endofunctor of $K$-$\mathcal{V}ec$ or
$\mathcal{S}et_{p}$ preserves (finite) products iff it preserves (finite)
limits. This also follows from results presented by Trnková in [4] (Prop. 4
and Example B). In that paper Trnková studies categories $\mathcal{K}$ such
that every functor with domain $\mathcal{K}$ preserving products preserves
limits. Besides vector spaces and pointed sets, Trnková shows that examples of
such categories $\mathcal{K}$ include sets with monomorphisms and topological
$T_{1}$-spaces with closed maps.

(2) Every nonempty finite intersection in $\mathcal{S}et$ is absolute. Indeed,
this is analogous to the case $\mathcal{S}et_{p}$: given subsets $m\colon
B\hookrightarrow A$ and $m^{\prime}\colon B^{\prime}\hookrightarrow A$ with
$c\in B\cap B^{\prime}$, we define $e\colon A\to B$ and $e^{\prime}\colon
B^{\prime}\to B\cap B^{\prime}$ as in Example 4.3(2). Preservation of nonempty
intersections was proved by Trnková (cf. [3, Proposition 2.1]).

##  5\. Set functors preserving countable products

We have seen that for endofunctors of $\mathcal{S}et_{p}$ there is no
difference between preservation of countable products and countable limits. Is
the same true for $\mathcal{S}et$? Not quite:

######  Example 5.1.

The functor $C_{01}$ given by $C_{01}\emptyset=\emptyset$ and $C_{01}X=1$ for
all $X\not=\emptyset$ clearly preserves products. But it does not preserve the
intersection of the coproduct injections of $1+1$:

${\emptyset}$${\emptyset}$${1}$${1}$${1}$${1}$${{1+1}}$${1}$$\scriptstyle{C_{01}}$

This is the unique such set functor (up to natural isomorphism), as we now
prove.

######  Definition 5.2.

(Trnková [5]) Let $H$ be a set functor. An element $x\in HX$ is distinguished
if for all parallel pairs $f,g\colon X\to Y$ we have $Hf(x)=Hg(x)$.

######  Example 5.3.

(1) Every element $x\in H\emptyset$ is distinguished.

(2) If $x\in HX$ is distinguished, so is $Hf(x)\in HY$ for each $f\colon X\to
Y$.

The following result can be derived from [3, Prop. I.4] and [5, Prop. II.6].
We present a short proof for the convenience of the reader.

######  Proposition 5.4.

Every set functor without distinguished elements preserves finite
intersections.

###### Proof.

Let $H\colon\mathcal{S}et\to\mathcal{S}et$ have no distinguished element. By
the above example, $H\emptyset=\emptyset$. We already know from Remark 4.4
that $H$ preserves nonempty intersections. Thus we only need to consider
disjoint subsets $A_{1},\,A_{2}$ of $B$:

${\emptyset}$${{A_{1}}}$${{A_{2}}}$${B}$$\scriptstyle{m_{1}}$$\scriptstyle{m_{2}}$

Suppose $H$ does not preserve this pullback, then we prove that it has a
distinguished element. Since $H\emptyset=\emptyset$ and $H$ does not preserve
the above pullback, there exist $t_{i}\in HA_{i}$ with
$Hm_{1}(t_{1})=Hm_{2}(t_{2})=t$. The element $t\in HB$ is distinguished.
Indeed, for every pair $f,g\colon B\to Y$ we can choose a map $h\colon B\to Y$
coinciding on $A_{1}$ with $f$ and on $A_{2}$ with $g$:

$h\cdot m_{1}=f\cdot m_{1}\;\text{ and }\;h\cdot m_{2}=g\cdot m_{2}.$

Then

$Ff(t)=F(f\cdot m_{1})(t_{1})=Fh(Fm_{1}(t_{1}))=Fh(t)$

as well as

$Fg(t)=F(g\cdot m_{2})(t_{2})=Fh(Fm_{2}(t_{2}))=Fh(t).$

∎

######  Theorem 5.5.

Every set functor $H\not\simeq C_{01}$ preserving finite products preserves
finite limits.

###### Proof.

Let $H$ preserve finite products. We know that $H1\simeq 1$, and we put

$H1=\\{a_{1}\\}.$

Since $H$ preserves the product $\emptyset=\emptyset\times\emptyset$, we have

$H\emptyset=\emptyset\;\text{ or }\;H\emptyset\simeq 1.$

(a) Let $H\emptyset$ contain an element $a_{0}$. Then, by Example 5.3, the
element $a_{1}=Ht(a_{0})$ (for the unique $t\colon\emptyset\to 1$) is
distinguished. For every set $X\not=\emptyset$ we put

$a_{X}=Hf(a_{1})\;\text{for}\;f\colon 1\to X$

and prove

$HX=\\{a_{X}\\}\;\text{ for all $X$.}$

Thus $H$ is naturally isomorphic to the constant functor of value $1$, and
preserves limits.

Our equation $HX=\\{a_{X}\\}$ holds for $\emptyset$ and $1$, so we can assume
that card$\,X\geq 2$. We first observe that $H$ maps every constant function
$f\colon X\to Y$ of value $y$, $f=\text{const}\,y$, to the constant function
of value $a_{Y}$:

$H(\text{const}\,y)=\text{const}\,a_{Y}.$

Indeed, we have $f^{\prime}\colon 1\to Y$ making the left-hand triangle below
commutative

${1}$${{\\{a_{1}\\}}}$${X}$${Y}$${HX}$${HY}$$\scriptstyle{!}$$\scriptstyle{f^{\prime}}$$\scriptstyle{f}$$\scriptstyle{H!}$$\scriptstyle{Hf}$$\scriptstyle{Hf^{\prime}}$

Thus the right-hand triangle verifies the statement: since $a_{1}$ is
distinguished, $Hf^{\prime}(a_{1})=a_{Y}$. Choose $x_{1}\not=x_{2}$ in $X$ and
put

$f_{i}=\langle\mathrm{id},\text{const}\,x_{i}\rangle\colon X\to X\times
X\;\;(i=1,2).$

The projections $\pi_{l},\,\pi_{r}$ make the following diagrams commutative
for $i=1,2$:

${X}$${HX}$${X}$${{X\times X}}$${X}$${HX}$${{H(X\times
X)}}$${HX}$$\scriptstyle{\mathrm{id}}$$\scriptstyle{f_{i}}$$\scriptstyle{\text{const}\,x_{i}}$$\scriptstyle{\pi_{l}}$$\scriptstyle{\pi_{r}}$$\scriptstyle{\mathrm{id}}$$\scriptstyle{Hf_{i}}$$\scriptstyle{\text{const}\,a_{X}}$$\scriptstyle{H\pi_{l}}$$\scriptstyle{H\pi_{r}}$

Since $H$ preserves $X\times X$, the pair $H\pi_{l}$, $H\pi_{r}$ is
collectively monic. This proves

$Hf_{1}=Hf_{2}\colon HX\to H(X\times X).$

Next consider the following map

$g\colon X\times X\to X,\;g(u,v)=\left\\{\begin{array}[]{ll}x_{1}&\text{if
$v=x_{1}$}\\\ u&\text{else.}\end{array}\right.$

Then the diagram below commutes:

${X}$${{X\times
X}}$${X}$${X}$$\scriptstyle{\text{const}\,x_{1}}$$\scriptstyle{\mathrm{id}}$$\scriptstyle{g}$$\scriptstyle{f_{1}}$$\scriptstyle{f_{2}}$

Apply $H$ to it and get (using $H(\text{const}\,x_{1})=\text{const}\,a_{X}$)
that

$\mathrm{id}_{HX}=\text{const}\,a_{X}.$

This proves $HX=\\{a_{X}\\}.$

(b) Let $H\emptyset=\emptyset$. If $a_{1}\in H1$ is distinguished, then, as in
(a), we derive $HX=\\{a_{X}\\}$ for all $X\not=\emptyset$. Thus $H$ is
naturally isomorphic to $C_{01}$.

If $a_{1}$ is not distinguished, then $H$ has no distinguished element ($a\in
HX$ distinguished implies $Hf(a)$ distinguished for $f\colon X\to 1$). Apply
Proposition 5.4 to conclude that $H$ preserves finite limits. ∎

######  Corollary 5.6.

A finitary set functor $H\not\simeq C_{01}$ is a right adjoint if and only if
it preserves countable products.

## References

  * [1] J. Adámek and J. Rosický, Locally presentable and accessible categories, Cambridge Univ. Press, Cambridge 1994.
  * [2] G. Tendas, On continuity of accessible functors, Appl. Categ. Structures 30 (2022), no. 5, 937–946.
  * [3] V. Trnková, Some properties of set functors, Comment. Math. Univ. Carolinae 10 (1969), 323-352.
  * [4] V. Trnková, When the product-preserving functors preserve limits, Comment. Math. Univ. Carolinae 11 (1970), 365-378.
  * [5] V. Trnková, On descriptive classification of set-functors I, Comment. Math. Univ. Carolinae 12 (1971), 143-174.