{'fraction_non_alphanumeric': 0.04890941216647612, 'fraction_numerical': 0.009428499309566586, 'mean_word_length': 4.111954459203036, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Control Improvisation

We formalize and analyze a new problem in formal language theory termed control improvisation. Given a specification language, the problem is to produce an improviser, a probabilistic algorithm that randomly generates words in the language, subject to two additional constraints: the satisfaction of a quantitative soft constraint, and the exhibition of a specified amount of randomness. Control improvisation has many applications, including for example systematically generating random test vectors satisfying format constraints or preconditions while being similar to a library of seed inputs. Other applications include robotic surveillance, machine improvisation of music, and randomized variants of the supervisory control problem. We describe a general framework for solving the control improvisation problem, and use it to give efficient algorithms for several practical classes of instances with finite automaton and context-free grammar specifications. We also provide a detailed complexity analysis, establishing #P-hardness of the problem in many other cases. For these intractable cases, we show how symbolic techniques based on Boolean satisfiability (SAT) solvers can be used to find approximate solutions. Finally, we discuss an extension of control improvisation to multiple soft constraints that is useful in some applications.


INTRODUCTION
We introduce and formally characterize a new formal language-theoretic problem termed control improvisation. Given a specification language or hard constraint, the problem is to produce an improviser, a probabilistic algorithm that randomly generates words in the language, subject to two additional constraints: the generated words should satisfy a quantitative soft constraint, and the improviser must exhibit a specified amount of randomness.
The original motivation for this problem came from a topic known as machine improvisation of music [Rowe 2001]. 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 generated melodies should be actual variations on the reference melody, neither reproducing it exactly nor being so different as to be unrecognizable. Finally, the algorithm should be sufficiently randomized that running it several times produces a variety of different improvisations. In previous work [Donzé et al. 2014], 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 harmonization 1 .
These three properties of a generation algorithm are not specific to music. Consider black-box fuzz testing [Sutton et al. 2007], 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 timeof-day constraints and limits on energy usage [Akkaya et al. 2016]) and randomized variants of the supervisory control problem [Cassandras and Lafortune 2006], 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 [Lafortune 2015].
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 as a function of the type of specification used for the hard and soft constraints. 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 [Hickey and Cohen 1983;Kannan et al. 1995], and sampling from the satisfying assignments of a Boolean formula [Jerrum et al. 1986;Bellare et al. 2000;Chakraborty et al. 2014]. Probabilistic programming techniques [Gordon et al. 2014] 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, and a general framework for constructing efficient improvisation schemes (Sec. 3); -A detailed complexity analysis of several practical classes of CI instances with specifications of different kinds: -Finite automata: a polynomial-time improvisation scheme for deterministic automata and a #P-hardness result for nondeterministic automata (Sec. 4); -Context-free grammars: polynomial-time improvisation schemes when one specification is an unambiguous grammar, and a #P-hardness result when both specifications are such grammars (Sec. 5); -Boolean formulas: a symbolic approach based on Boolean satisfiability (SAT) solving that can be used, for example, with finite-state automata that are too large to represent explicitly (Sec. 6); -An extension of the basic control improvisation definition to allow multiple soft constraints (Sec. 7).
Compared to the earlier version of this paper (Fremont et al. [2015]), the CI definition has been elaborated with explicit length bounds and a more general randomness requirement. The material on generic improvisation schemes, context-free grammar specifications, and multiple soft constraints is entirely new.

BACKGROUND AND PROBLEM DEFINITION
In this section, we first define notation and provide 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 the definition.

Notation
We abbreviate deterministic and nondeterministic finite automata as DFAs and NFAs respectively. Similarly we refer to a context-free grammar as a CFG, and an unambiguous context-free grammar as a UCFG. We write the set {1, . . . , k} for k ∈ N + as [k]. For any alphabet Σ, we denote the length of a finite word w ∈ Σ * by |w|. We also write Σ ≤n for ∪ 0≤i≤n Σ i . Finally, if L is a language over Σ, we sometimes denote Σ * \ L by L.
We refer to several standard complexity classes: P and NP, the class #P of counting versions of NP problems, its decision analogue PP, the polynomial-time hierarchy PH, and the class FP of polynomial-time computable functions. For definitions of these classes and the relationships between them, see Arora and Barak [2009].

Motivation: Factor Oracles
An effective and practical approach to machine improvisation of music (used for example in the prominent OMax system [Assayag et al. 2012]) is based on a data structure called the factor oracle [Assayag and Dubnov 2004;Cleophas et al. 2003]. Given a word w ref of length N that is a symbolic encoding of a reference melody, a factor oracle F is an automaton constructed from w ref with the following key properties: F has N + 1 states, all accepting, chained linearly with direct transitions labelled with the letters in w ref , and with potentially additional forward and backward transitions. Figure 1 depicts F for w ref = bbac. A word w accepted by F consists of concatenated "factors" (subwords) of w ref , and its dissimilarity with w ref is correlated with the number of non-direct transitions. By assigning a small probability α to non-direct transitions, F becomes a generative Markov model with tunable "divergence" from w ref . In order to impose more musical structure on the generated words, our previous work [Donzé et al. 2014] 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, (ii) it includes a quantitative requirement on which strings are admissible based on their divergence from a reference string, and (iii) it enforces diversity in the generated strings. 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 ref that it represents can be encoded in our formalism.

Problem Definition
A control improvisation problem is defined in terms of two languages specifying the hard and soft constraints. The complexity of the problem depends on how these languages are represented, and we will consider several representations in this paper. We use the general term specification to refer to the representation of a language.
Definition 2.1. A specification X is a finite representation of a language L(X ) over a finite alphabet Σ. For example, X could be a finite automaton or a context-free grammar.
Definition 2.2. Fix a hard specification H, a soft specification S, and length bounds m, n ∈ N. An improvisation is any word w ∈ L(H) such that m ≤ |w| ≤ n, and we write I for the set of all improvisations. An improvisation w ∈ I is admissible if w ∈ L(S), and we write A for the set of all admissible improvisations.
Observe that because we impose an upper bound on the length of an improvisation, the sets I and A are finite 2 .
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 we put Σ = {0, 1} and m = n = 3, and let H be a DFA which accepts all strings that do not have two 1s in a row. To ensure that our variations are similar to s, we let S be a DFA accepting words with Hamming distance at most 1 from s. 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? First, we require our generated improvisation to be admissible with probability at least 1 − ǫ for some specified ǫ. When the soft specification S 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. Note that this requirement can be relaxed by increasing the value of ǫ, justifying the term "soft specification". Other types of quantitative requirements are interesting and worthy of study, but in this paper we focus on the probabilistic constraint above. Note also that while the soft specification S by itself is a property true or false for any word, the soft constraint requirement is not a property of individual words: it constrains the distribution from which we generate words. This is an important asymmetry between the hard and soft constraints: in particular, it means that we must consider both the language L(S) and its complement L(S), as we may have to generate words from each.
Second, since we want a variety of improvisations, we impose a randomness requirement: every improvisation must be generated with a probability within a desired range [λ, ρ]. This requirement is designed to accommodate two different needs for randomness. In fuzz testing, for example, in order to ensure coverage we might want to ensure that every test case can be generated and so put λ > 0. By contrast, in music improvisation it is not important that every possible melody can be generated; rather, we simply want no improvisation to arise too frequently. So in this application we might put λ = 0 but ρ < 1. Our definition allows any combination of these two cases. Note that if there are N improvisations, then setting λ or ρ equal to 1/N forces the distribution to be uniform. So uniform sampling as used in fuzz testing or constrained random verification is a special case of control improvisation. We also note that other randomness requirements are possible, for example ensuring variety by imposing some minimum distance between generated improvisations. This could be reasonable in a setting such as music or robotics 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. Combining these requirements, we obtain our definitions of an acceptable distribution over improvisations and thus of an improviser: Definition 2.3. Given C = (H, S, m, n, ǫ, λ, ρ) with H, S, m, and n as in Definition 2.2, ǫ ∈ [0, 1] ∩ Q an error probability, and λ, ρ ∈ [0, 1] ∩ Q probability bounds, a distribution D : Σ * → [0, 1] is an improvising distribution if it satisfies the following requirements: If there is an improvising distribution, we say that C is feasible. An improviser for a feasible C is an expected finite-time probabilistic algorithm generating strings in Σ * whose output distribution (on empty input) is an improvising distribution.
To summarize, if C 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, C = (H, S, 3, 3, 0, 0, 1/4) is not feasible since ǫ = 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 ρ to 1/3 would make C feasible. Increasing ǫ 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 (H, S, 3, 3, 1/4, 0, 1/4). This would not be an improviser if we put λ > 0, however, since the improvisation 010 is generated with probability 0.
Definition 2.4. Given C = (H, S, m, n, ǫ, λ, ρ), the control improvisation (CI) problem is to decide whether C is feasible, and if so to generate an improviser for C. The size |C| of a CI instance is the total size of the bit representation of its parameters, treating m and n as being represented in unary and all other numerical parameters in binary.
When more than one CI instance is being discussed, we use subscripts to disambiguate parameters: for example n C is the value of n in the instance C. Similarly, we write I C and A C for the sets of improvisations and admissible improvisations respectively with respect to C.
Since we are interested in the complexity of the CI problem as a function of the type of specification used, we define classes of instances based on those: Definition 2.5. If A and B are classes of specifications, CI(A,B) is the class of CI instances C = (H, S, m, n, ǫ, λ, ρ) where H ∈ A and S ∈ B. When discussing decision problems, we use the same notation for the feasibility problem associated with the class (i.e. given C ∈ CI(A,B), decide whether it is feasible).
For example, CI(UCFG,DFA) is the class of instances where the hard specification is an unambiguous context-free grammar and the soft specification is a deterministic finite automaton.
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.6. A polynomial-time improvisation scheme for a class P of CI instances is an algorithm S with the following properties:

Correctness:
For any C ∈ P, if C is feasible then S(C) is an improviser for C, and otherwise S(C) = ⊥.

Scheme efficiency:
There is a polynomial p : R → R such that the runtime of S on any C ∈ P is at most p(|C|). Improviser efficiency: There is a polynomial q : R → R such that for every C ∈ P, if G = S(C) = ⊥ then G has expected runtime at most q(|C|).
The improviser efficiency requirement prevents the scheme from, for example, being polynomial-time only by offloading an exponential search into the generated improviser. Accordingly, when we say an improvisation scheme is polynomial-time relative to an oracle, the runtimes of both the scheme and its generated improvisers are measured relative to the oracle. 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 subsequent sections, we will identify several classes that have such improvisation schemes.

EXISTENCE OF IMPROVISERS, AND A GENERIC IMPROVISATION SCHEME
In this section, we first give necessary and sufficient conditions for an improviser to exist for a given CI instance. The proof is constructive, and leads to a generic procedure for solving the CI problem using a few abstract operations on specifications. All of the improvisation schemes given in this paper are derived by instantiating this procedure for particular classes of CI instances. Finally, we use the procedure to give a general #P upper bound on the complexity of CI for a wide range of specifications.
First, 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 C = (H, S, m, n, ǫ, λ, ρ), the following are equivalent: (1) C is feasible.
(2) The following inequalities hold 3 : There is an improviser for C.
Let D be the distribution on I which picks uniformly from A with probability 1 − ǫ opt and otherwise picks uniformly from I \ A. Note that this distribution is well-defined, since if A = ∅ then ǫ opt = 1, and if I \ A = ∅ then ρ|A| = ρ|I| ≥ 1 and so ǫ opt = 0. Clearly, D satisfies the hard constraint requirement.
Therefore for any w ∈ I we always have λ ≤ D(w) ≤ ρ, and thus D satisfies the randomness requirement.
This shows that D is an improvising distribution. Since it has finite support and rational probabilities, there is an expected finite-time probabilistic algorithm sampling from it, and this algorithm is an improviser for C.
Remark 3.2. In fact, whenever 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. There can of course be other improvising distributions assigning a variety of probabilities between λ and ρ, but one of this simple form is always guaranteed to exist.
The intuition behind the improviser constructed in Theorem 3.1 is as follows: attempt to assign the minimum allowed probability λ to the elements of I \ A, spreading the rest uniformly over A. This may assign a probability to the elements of A that is greater than the maximum allowed probability ρ. In that case, we clamp the probabilities of the admissible improvisations at ρ, and spread the remainder uniformly over I \ A. This intuition suggests that the error probability ǫ opt achieved by this improviser is optimal, since we attempt to give A as high a probability as we can. In fact, this is the case (justifying the notation ǫ opt ): the smallest error probability compatible with the hard constraint and randomness requirements is ǫ opt .
PROOF. Immediate from Theorem 3.1, noting that ǫ ≥ ǫ opt if and only if inequalities (2b) and (2c) in the Theorem hold.
Beyond just giving conditions for feasibility, the proof of Theorem 3.1 suggests a generic procedure for solving the CI problem. It uses a few basic operations on specifications:

Intersection:
Given two specifications X and Y, compute a specification Z such that L(Z) = L(X ) ∩ L(Y).

Difference:
Given two specifications X and Y, compute a specification Z such that L(Z) = L(X ) \ L(Y). Length Restriction: Given a specification X and m, n ∈ N in unary, compute a specifi- Given a specification X and a bound n ∈ N in unary on the length of strings in L(X ) (which is therefore finite), compute |L(X )|. Uniform Sampling: Given a specification X and a bound n ∈ N in unary on the length of strings in L(X ), sample uniformly at random from L(X ).
If these operations can be implemented efficiently for a particular type of specification, then we can efficiently solve the corresponding CI problems: THEOREM 3.4. Suppose SPEC is a class of specifications that supports the operations above. Suppose further that the operations can be done in polynomial time (expected time in the case of uniform sampling). Then there is a polynomial-time improvisation scheme for CI(SPEC,SPEC). PROOF. Given a problem C ∈ CI(SPEC,SPEC) with C = (H, S, m, n, ǫ, λ, ρ), the scheme works as follows. First, we construct representations of all the sets we need. Applying length restriction to H, we obtain a specification I such that L(I) = {w ∈ L(H) | m ≤ |w| ≤ n} = I. Applying intersection to I and S, we get a specification A such that L(A) = L(I) ∩ L(S) = I ∩ L(S) = A. Finally, applying difference to I and A gives a specification B such that L(B) = I \ A.
Next, applying counting to I and A (with bound n, since all words in I have length at most n), we compute |I| and |A|. We can then check whether the inequalities in Theorem 3.1 are satisfied. If not, then C is not feasible and we return ⊥. Otherwise, C is feasible and we will build an improviser sampling from the same distribution constructed in the proof of Theorem 3.1. As there, let ǫ opt = max(1 − ρ|A|, λ|I \ A|) (easily computed since we know |I| and |A|, and |I \ A| = |I| − |A|), and let D be the distribution on I that with probability 1 − ǫ opt picks uniformly from A and otherwise picks uniformly from I \ A. Since the inequalities in Theorem 3.1 are true, its proof shows that D is an improvising distribution for C.
We can easily build a probabilistic algorithm G sampling from D: it simply flips a coin, applying uniform sampling to A with probability 1 − ǫ opt and otherwise applying uniform sampling to B. Since L(A) = A and L(B) = I \ A, the output distribution of G is D and so G is an improviser for C.
This procedure is clearly correct. Since the intersection, difference, and length restriction operations take polynomial time, the constructed specifications I, A, and B have sizes polynomial in |H|, |S|, m, and n, and thus in |C|. So the subsequent counting and sampling operations performed on these specifications will also be polynomial in |C|. In particular, the computed values of |I| and |A| have polynomial bitwidth, so the same is true of ǫ opt , and the arithmetic performed by the procedure also takes time polynomial in |C|. Therefore in total the procedure runs in polynomial time. The improvisers generated by the procedure run in expected polynomial time, since the bitwidth of ǫ opt is polynomial and uniform sampling takes expected polynomial time. So the procedure is a polynomial-time improvisation scheme.
Note that since we use the operations on specifications as black boxes, the construction above relativizes: if the operations can be done in polynomial time relative to an oracle O, then the Theorem yields an improvisation scheme that is polynomial-time relative to O (where both the scheme and the generated improvisers may query O). This allows us to upper bound the complexity of CI problems under very weak assumptions on the type of specifications.
THEOREM 3.5. Suppose SPEC is a class of specifications such that membership in the language of a specification can be decided in polynomial time relative to a PH oracle. Then CI(SPEC,SPEC) has an improvisation scheme that is polynomial-time relative to a #P oracle.
Without the PH oracle, this essentially follows from the fact that if specifications are decision algorithms with uniformly polynomial runtimes which test membership in their respective languages, then counting and sampling can be done with a #P oracle. However, instantiating the general operations used by Theorem 3.4 is somewhat tricky since we need to keep track of the runtimes of the specifications. So instead we just verify that the particular counting and sampling queries needed by the construction in Theorem 3.4 can be implemented with a #P oracle. This whole argument relativizes to the PH oracle, which can then be eliminated via Toda's theorem. PROOF OF THEOREM 3.5. By assumption there is a polynomial-time algorithm M PH (w, X ) that decides whether w ∈ L(X ) for any specification X ∈ SPEC. Then , so whether w ∈ A C is decidable in time polynomial in |w| and |C| relative to a PH oracle. Since any w ∈ I C has length at most n C , and in particular polynomial in |C|, this shows that the relations NP PH -relations 4 . Therefore computing |I C | = |{w ∈ Σ * | (C, w) ∈ R I }| is a #P PH problem, and likewise for |A C |. Furthermore, sampling uniformly from A C and I C \ A C is equivalent to sampling uniformly from the witnesses of C under the relations R A and R I\A respectively. This can be done in polynomial expected time relative to a #P PH oracle (relativizing the algorithms of Jerrum et al. [1986] or Bellare et al. [2000]). So the construction in Theorem 3.4 yields an improvisation scheme for CI(SPEC,SPEC) that is polynomial-time relative to a #P PH oracle.
To remove the PH oracle, note that PP PH ⊆ P PP by the stronger form of Toda's theorem [Toda 1991]. Since #P PH ⊆ FP PP PH by a standard binary search argument, we have #P PH ⊆ FP PP PH ⊆ FP P PP = FP PP ⊆ FP #P . So the polynomial-time improvisation scheme (and the improvisers it generates) can simulate the #P PH oracle using only a #P oracle.
This general argument establishes that for a wide range of specifications (i.e. those which do not require resources beyond PH to evaluate), the complexity of the CI problem is between polynomial-time and #P. In the next few sections, we will pin down the complexity of several natural classes of CI problems as being at one end or the other of this range.

AUTOMATA SPECIFICATIONS
In this section we consider specifications that are finite automata. For deterministic automata, we give a polynomial-time improvisation scheme, but show that for nondeterministic automata the CI problem becomes #P-hard.
DFAs are perhaps the simplest type of specification. They capture the notion of a finite-memory specification, where membership of a word can be determined by scanning the word left-to-right, only being able to remember a finite number of alreadyseen symbols. An example of a finite-memory specification S is one such that w ∈ L(S) iff each subword of w of a fixed constant length satisfies some condition.
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 ref is by counting the number of non-direct transitions that w causes F to take. Since DFAs cannot do unbounded counting, we can use a sliding window of some finite size k. Then our soft specification S 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 [ℓ, h]. This predicate can be encoded as a DFA of size O(|F | · 2 k ) as follows: we have a copy of F , denoted F s , for every string s ∈ {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 [ℓ, h], this automaton represents α as desired. The size of the automaton grows exponentially in the size of the window, but for small windows it can be reasonable.
When both the hard and soft specifications are DFAs, we can instantiate the procedure of Theorem 3.4 to get a polynomial-time improvisation scheme. To do this, we use a classical method for counting and uniformly sampling from the language of a DFA (see for example Hickey and Cohen [1983]). The next two lemmas summarize the results we need, proofs being given in the Appendix for completeness. PROOF. We instantiate the five operations needed by Theorem 3.4.

Intersection:
Given two DFAs X and Y, we can construct a DFA Z such that L(Z) = L(X ) ∩ L(Y) with the standard product construction. The time needed to do this and the size of Z are both O(|X ||Y|).

Difference:
Given two DFAs X and Y, we can construct a DFA Z such that L(Z) = L(X ) \ L(Y) by complementing Y with the standard construction, and then taking the product with X . The time required and resulting automaton size are polynomial, as for intersection.
Length Restriction: Given a DFA X and m, n ∈ N in unary, we can construct a DFA R of size O(n) such that L(R) = {w ∈ Σ * | m ≤ |w| ≤ n} (the states track how many symbols have been read so far, up to n + 1). Then letting Y be the product of X and R, we have L(Y) = {w ∈ L(X ) | m ≤ |w| ≤ n} as desired. Polynomial runtime and automaton size follow from the same properties for the product operation.
Since we can perform all of these operations in polynomial time, Theorem 3.4 yields a polynomial-time improvisation scheme.
So we can efficiently solve CI problems with specifications given by deterministic finite automata. However, if we have nondeterministic automata, this technique breaks down because there is no longer a one-to-one correspondence between accepting paths in the automaton and words in its language. Indeed, counting the language of an NFA is known to be hard, and this translates into hardness of CI. PROOF. We prove this for CI(NFA,DFA) -the other case is similar. As shown by Kannan et al. [1995], the problem of determining |L(M) ∩ Σ m | given an NFA M over an alphabet Σ and m ∈ N in unary is #P-complete. We give a polynomial-time (Cook) reduction from this problem to checking feasibility of a CI instance in CI(NFA,DFA).
For any NFA M and positive N ∈ N, consider the CI(NFA,DFA) instance C N = (M, T , m, m, 0, 0, 1/N ) where T is the trivial DFA accepting all of Σ * . Clearly for this instance we have I = A = L(M) ∩ Σ m . By Theorem 3.1, C N is feasible iff |L(M) ∩ Σ m | ≥ 1/(1/N ) = N , and so we can determine whether the latter is the case with a feasibility query for a CI(NFA,DFA) instance. Since |L(M) ∩ Σ m | ≤ |Σ| m , using binary search we can find the exact value of |L(M)∩Σ m | with polynomially-many such queries (recalling that m is given in unary).
This result indicates that in general, the control improvisation problem is probably intractable in the presence of NFAs or more complex automata such as probabilistic automata 5 [Rabin 1963].

CONTEXT-FREE GRAMMAR SPECIFICATIONS
Next we consider specifications that are context-free grammars. These are useful, for example, in the fuzz testing application where we want to generate tests conforming to a file format. Unfortunately, CFGs are more concise than NFAs, and so our hardness result for the latter immediately rules out a polynomial-time improvisation scheme.
PROOF. Follows from Theorem 4.5, since an NFA can be converted to an equivalent CFG in polynomial time.
However, CFGs used in practice are often designed to be unambiguous, enabling faster parsing. For UCFGs there are polynomial-time algorithms for counting and uniform sampling [Hickey and Cohen 1983;McKenzie 1997], giving hope for a polynomial-time improvisation scheme. A complication is that UCFGs are not closed under intersection, and indeed we will see below that when both hard and soft specifications are UCFGs and intersecting them is required, the CI problem is #P-hard. But when one specification is a UCFG and the other is a DFA, there is a polynomial-time improvisation scheme.
To use the procedure of Theorem 3.4 in this case, we need to be able to intersect a UCFG G and a DFA D. By a classical result of Bar-Hillel et al. [1961], their intersection is a context-free language, and we can compute a CFG H such that L(H) = L(G) ∩ L(D) in polynomial time. However, in order to then sample from this intersection, we need H to be unambiguous. As noted by Ginsburg and Ullian [1966], this is actually accomplished by the construction of Bar-Hillel et al. [1961]. However their presentation does not explicitly demonstrate this fact, so for completeness we present a proof. We also modify the algorithm in several ways to improve its complexity (this is important in practice since the construction, while polynomial, has relatively high degree). PROOF. First convert G to a CFG G ′ = (V, Σ, P, S) such that (1) L(G ′ ) = L(G) \ {ǫ}, and (2) the RHS of every production in P has length at most 2 and does not contain ǫ.
This transformation can be done in a way that the time required and the size of G ′ are both O(|G|), and in the process we determine whether ǫ ∈ L(G) [Hopcroft et al. 2001, Sec. 7.4.2]. Furthermore, it is simple to check that since G is unambiguous, this procedure ensures that G ′ is also. The rest of our algorithm will build an unambiguous CFG H such that L(H) = L(G ′ ) ∩ L(D), and thus ǫ ∈ L(H). If ǫ ∈ L(G) ∩ L(D) (which we can easily check, since we know whether ǫ ∈ L(G) from above, and checking if ǫ ∈ L(D) is trivial), we can simply add the production S → ǫ to H without introducing any ambiguity. Therefore ultimately we will have L(H) = L(G) ∩ L(D) as desired.
The main construction of Bar-Hillel et al. [1961] works on DFAs with a single accepting state: there is an initial preprocessing step which writes D as a union of |F | DFAs of that form, so that the construction can be carried out on each and the resulting grammars combined. Doing this would contribute a factor of |F | to our algorithm's runtime, so instead we modify D to produce an NFA D ′ = (Q ′ , Σ, δ ′ , q 0 , F ′ ) as follows. We add two new states ACCEPT and REJECT, where δ(ACCEPT, a) = δ(REJECT, a) = REJECT for every a ∈ Σ. Also for any transition δ(x, a) = y where y ∈ F , we add a transition from x to ACCEPT on input a -note that this makes D ′ nondeterministic. Finally, we make ACCEPT the only accepting state of D ′ . Clearly we can construct D ′ in time linear in |D|.
Now consider any nonempty word w ∈ L(D), which we may write a 0 . . . a n for some n ≥ 0. Let w ′ be w without its last symbol a n (so w ′ = ǫ if w has length 1). Since w ∈ L(D) there is some x ∈ Q and y ∈ F such that δ(q 0 , w ′ ) = x and δ(x, a n ) = y. Therefore w ∈ L(D ′ ), since D ′ on input w ′ can follow unmodified transitions from D to reach x, and then the new transition from x to ACCEPT on input a n . Conversely, if w ∈ L(D ′ ) then executing D ′ on input w we must end in state ACCEPT, and all transitions except the last must be transitions of D (since once we follow a new transition to ACCEPT, any further transitions will end in REJECT). Note that this means there is only one accepting path in D ′ corresponding to w -this will be important later. If the last transition in this path is from state x on input a, then by construction δ(x, a) ∈ F and so w ∈ L(D). Therefore L(D ′ ) = L(D) \ {ǫ}, and since ǫ ∈ L( Now, following Bar-Hillel et al. [1961], we build the CFG H = (V , Σ,P ,Ŝ) wherê V = (Q ′ × V × Q ′ ) ∪ Σ andŜ = (q 0 , S, ACCEPT). There are two 6 kinds of productions in P : (1) For every production A → BC in P , we add the productions (x, A, z) → (x, B, y)(y, C, z) for all x, y, z ∈ Q ′ toP .
(2) For every production A → b in P , we add the productions (x, A, y) → b for all x, y ∈ Q ′ such that (x, b, y) ∈ δ ′ toP . It remains to show that H is unambiguous. Take any word w ∈ L(H), and any two derivation trees T 1 and T 2 for w. Observe that by the way we constructed the productions of H above, if we drop the first and third components of the labels on the non-leaf nodes of T 1 or T 2 we obtain a derivation tree for w from the grammar G ′ . Therefore since G ′ is unambiguous, T 1 and T 2 have the same tree structure. Now we prove by induction on trees that every node in T 1 has the property that its label is identical to the corresponding node in T 2 . For the leaf nodes this is immediate, since they spell out w in either tree. For nodes one level up, i.e. those to which a production of type 2 is applied, it is proved by Bar-Hillel et al. [1961] that if these are written from left to right they form a sequence (q 0 , v 0 , q 1 ), (q 1 , v 1 , q 2 ), . . . , (q n−1 , v n−1 , q n ) where q 0 q 1 . . . q n is an accepting path for w in D ′ . Since as shown above there is only one such path, these nodes also have the property. Finally, observe that under productions of type 1, the state labels of the parent node are uniquely determined by those of its children. So if all of a node's children satisfy the property, so does the node itself, and thus by induction all nodes have the property. Therefore T 1 and T 2 are identical, and so H is unambiguous.
The next two lemmas put the known results on counting and sampling for UCFGs into the form we need. LEMMA 5.3. Given a UCFG G and m, n ∈ N in unary, we can compute |{w ∈ L(G) | m ≤ |w| ≤ n}| in polynomial time.
PROOF. The algorithms of Hickey and Cohen [1983] or McKenzie [1997] can compute |L(G) ∩ Σ i | in time polynomial in |G| and i (both algorithms do this as a preliminary step to sampling uniformly from L(G) ∩ Σ i ). We do this for every i such that m ≤ i ≤ n, and return the sum of the results 7 .
LEMMA 5.4. Given a UCFG G and m, n ∈ N in unary, we can uniformly sample from {w ∈ L(G) | m ≤ |w| ≤ n} in expected polynomial time.
PROOF. As in the previous lemma, compute for each i from m to n the count c i = |L(G) ∩ Σ i |. Pick a random j so that the probability of obtaining i is c i / k c k . Then use the algorithms of Hickey and Cohen [1983] or McKenzie [1997] to sample uniformly from L(G) ∩ Σ j , and return the result. The probability of obtaining any w ∈ L(G) with m ≤ |w| ≤ n is (c |w| / k c k ) · (1/|L(G) ∩ Σ |w| |) = 1/ k c k = 1/|{w ∈ L(G) | m ≤ |w| ≤ n}|, as desired. Furthermore, the counting and sampling both take expected time polynomial in |G| and n.
Putting this all together, we obtain a polynomial-time improvisation scheme for the case where the hard specification is a UCFG.
PROOF. We follow the procedure of Theorem 3.4 with one modification: we do not perform length restriction explicitly, since the counting and sampling algorithms effectively do so (i.e. they only count/sample words of a given length). Applying Lemma 5.2 to H and S, we obtain a UCFG A such that {w ∈ L(A) | m ≤ |w| ≤ n} = A. Applying Lemma 5.2 to H and the complement of S (computed with the usual DFA construction), we obtain a UCFG B such that {w ∈ L(B) | m ≤ |w| ≤ n} = I \ A. Next, applying Lemma 5.3 to H and A, we obtain |I| and |A|. Then we can proceed exactly as in Theorem 3.4, using Lemma 5.4 to sample from {w ∈ L(A) | m ≤ |w| ≤ n} = A and {w ∈ L(B) | m ≤ |w| ≤ n} = I \ A.
While context-free grammars are most likely to be useful as hard specifications, when used as soft specifications instead there is still a polynomial-time improvisation scheme. However, the algorithm is significantly more involved than the one above, because we must sample from the complement of a context-free language and cannot directly use the sampling algorithm for UCFGs. THEOREM 5.6. There is a polynomial-time improvisation scheme for CI(DFA,UCFG).
PROOF. Applying length restriction as in Theorem 4.4 to H, we obtain a DFA I such that L(I) = I. Applying Lemma 5.2 to I and S, we obtain a UCFG A such that L(A) = A. Then we can apply Lemma 4.2 to I and Lemma 5.3 to A to compute |I| and |A|. If we can uniformly sample from ∆ = L(I) ∩ L(A) = L(I) \ L(A) = I \ A, we can then proceed exactly as in Theorem 3.4.
We will build up a word from ∆ incrementally, starting from the empty word. Suppose we have generated the prefix σ so far. For each symbol a ∈ Σ, let ∆ σa ⊆ ∆ contain all words starting with the prefix σa, i.e. ∆ σa = {w ∈ ∆ | ∃z ∈ Σ * : w = σaz}. Construct a DFA P σa accepting all words that start with the prefix σa (clearly we can take P σa to have size polynomial in |Σ| and n). Then ∆ σa = ∆ ∩ L(P σa ) = ∆ ∪ L(P σa ) = L(I) ∪ L(A) ∪ L(P σa ) = Σ ≤n \ (L(I) ∪ L(A) ∪ L(P σa )), since L(I) ⊆ Σ ≤n . Letting D be the complement of the product of I and P σa , we have L(D) = L(I) ∪ L(P σa ) and so ∆ σa = Σ ≤n \ (L(A) ∪ L(D)). Let D ′ be the product of D and a DFA accepting all words of length at most n, so that L(D ′ ) = L(D) ∩ Σ ≤n . Applying Lemma 5.2 to A and P σa , we can find a UCFG A σa such that L(A σa ) = L(A) ∩ L(P σa ). Then we have All words in L(A σa ) and L(D ′ ) have length at most n, so using Lemmas 5.3 and 4.2 respectively we can count the sizes of these languages in polynomial time. Since |Σ ≤n | = n i=0 |Σ| i = (|Σ| n+1 − 1)/(|Σ| − 1), we can then compute |∆ σa | by the formula above. Now let ∆ σ consist of all words in ∆ that start with the prefix σ. Observe that the sets ∆ σa form a partition Π σ of ∆ σ , unless σ ∈ ∆ in which case we need to also add the set {σ} to Π σ . Select one of the sets in Π σ randomly, with probability proportional to its size. If we pick {σ}, then we stop and return σ as our random sample. Otherwise we picked ∆ σa for some a ∈ Σ, so we append a to σ and continue.
Since the procedure of Theorem 3.4 only samples from I \A = ∆ when it is nonempty, in the first iteration ∆ σ = ∆ is nonempty and so one of the sets in Π σ must be nonempty. Since we assign a set in Π σ probability zero if it is empty, we will not select such a set, and so by induction ∆ σ is nonempty at every iteration. We must terminate after at most n iterations, since σ gets longer in every iteration and all words in ∆ have length at most n. We prove by induction on n−|σ| that if ∆ σ is nonempty, our procedure starting from σ generates a uniform random sample from ∆ σ . In the base case |σ| = n, we have ∆ σ = {σ}, since no word in ∆ has length greater than n but ∆ σ is nonempty. Therefore ∆ σa = ∅ for all a ∈ Σ, so the procedure will return σ, and this is indeed a uniform random sample from ∆ σ . For |σ| < n, if σ ∈ ∆ σ then the probability of returning σ is the probability of picking the set {σ} from Π σ , which is 1/ S∈Πσ |S| = 1/|∆ σ |. Any other w ∈ ∆ σ has length at least |σ| + 1 and so can be written w = σaw ′ for some a ∈ Σ and w ′ ∈ Σ * . Now to return w, our procedure must first pick the set ∆ σa from Π σ , and then return w in a later iteration. By the induction hypothesis, this happens with probability (|∆ σa |/ S∈Πσ |S|) · (1/|∆ σa |) = 1/|∆ σ |. So all words in ∆ σ are returned with uniform probability, and by induction this holds for all σ. In particular it holds in the first iteration when σ is the empty word, in which case we sample uniformly from ∆ σ = ∆ as desired.
This allows us to uniformly sample from I \ A and so finish the implementation of the procedure in Theorem 3.4. All of the operations we perform are polynomial-time, and the sampling procedure needs only polynomially-many iterations, so this yields a polynomial-time improvisation scheme.
The results above show that there are polynomial-time improvisation schemes for CI instances where one specification is a UCFG and the other is a DFA. However, when both the hard and soft specifications are grammars (even unambiguous ones), the complexity jumps all the way up to #P.
To prove this, we introduce an intermediate problem that captures the essentially hard part of solving CI problems with two grammar specifications.
Definition 5.8. #UCFG-INT is the problem of computing, given two UCFGs G 1 and G 2 over an alphabet Σ and n ∈ N in unary, the number of words in L(G 1 )∩L(G 2 )∩Σ ≤n .
Without the length bound, checking emptiness of the intersection of two CFGs is undecidable, as shown by Bar-Hillel et al. [1961]. We use a similar proof (closer to that of Floyd [1962]) to establish the complexity of the bounded version.
PROOF. All the words in L(G 1 ) ∩ L(G 2 ) ∩ Σ n have length polynomial in the size of the input, and checking whether a word is in the set can be done in polynomial time. So #UCFG-INT ∈ #P.
To show hardness, we give a reduction to #UCFG-INT from #BOUNDED-PCP, the counting version of the bounded Post correspondence problem. Recall that BOUNDED-PCP instances are ordinary PCP instances together with a bound m ∈ N in unary on the total number of tiles that may be used in a solution. In the usual construction simulating a Turing machine M with PCP tiles (see for example Hopcroft et al. [2001]), an accepting computation history for M leads to a PCP solution using a number of tiles linear in the size of the history. So the problem of checking whether M accepts a word in at most a number of steps given in unary reduces to BOUNDED-PCP, and thus the latter is NP-complete (as noted in a slightly different form by Constable et al. [1974]). Furthermore, this reduction is almost parsimonious: the computation history uniquely determines the PCP solution until the accepting state is reached, when (at least in the reduction given in Hopcroft et al. [2001]) the accepting state can "consume" tape symbols on either side of it in any order. However, we can easily modify the construction so that the symbols are consumed in a canonical order. In the terminology of Hopcroft et al. [2001], we replace the "type-4" tiles with tiles of the form (qX, q) and (Xq#, q#) for all accepting states q and tape symbols X. This forces tape symbols to be consumed from the right of q first, and only allows consumption from the left once there are no tape symbols to the right (so that q is adjacent to the # marking the end of the element of the history). Now there is a one-to-one correspondence between accepting computation histories of M and solutions to the BOUNDED-PCP instance, so the counting problem #BOUNDED-PCP is #P-complete.
Given an instance P of #BOUNDED-PCP with tiles (x 1 , y 1 ), . . . , (x k , y k ) over an alphabet Σ ′ and a bound m, we construct grammars X and Y along the lines of Bar-Hillel et al. [1961] and Floyd [1962]. The grammars use an alphabet Σ consisting of Σ ′ together with additional symbols t 1 , . . . , t k , and have nonterminal symbols X i and Y i respectively for 1 ≤ i ≤ m. Their start symbols are X m and Y m respectively, and

Control Improvisation
A:17 they have the following productions: An easy induction shows that the words derivable from X i (respectively, Y i ) correspond to nonempty sequences of at most i tiles. Thus there is a one-to-one correspondence between words in L(X) ∩ L(Y ) and solutions of P. Furthermore, both grammars are unambiguous, since the sequence of t i symbols uniquely determines the derivation tree. Finally, all words in L(X) have length at most n = m(1 + max(|x 1 |, . . . , |x k |)), so |L(X)∩L(Y )| = |L(X)∩L(Y )∩Σ ≤n |. Therefore (X, Y, 1 n ) is a #UCFG-INT instance with the same number of solutions as P. This reduction clearly can be done in polynomial time, so #UCFG-INT is #P-hard. Now we may complete the hardness proof for CI(UCFG,UCFG).

SYMBOLIC SPECIFICATIONS
In this section we discuss an important class of specifications given by existentiallyquantified Boolean formulas. We begin by defining the class and outline how it includes a widely-used succinct encoding of large finite-state automata. Then we show that although the CI problem is #P-hard with these specifications, it can be solved approximately using only an NP oracle. This means that some CI problems with very large automata can still be solved in practice using SAT solvers.
The specifications we will consider are Boolean formulas with auxiliary variables, where a word w (encoded in binary) is in the language iff the formula is satisfiable after plugging in w.
Definition 6.1. Fixing an alphabet Σ = {0, 1} k and a length n ∈ N, a symbolic specification is a Boolean formula φ(w, a) where w is a vector of nk variables and a is a vector of zero or more variables. The language of φ consists of all w ∈ Σ n such that ∃a φ(w, a) is true. The class of symbolic specifications is denoted SYMB.
Remark 6.2. The restriction that all words in the language of any symbolic specification have a fixed length n is for later convenience when intersecting two specifications. We can always pad shorter words out to length n with a dummy symbol added to the alphabet, altering the formula φ as appropriate.
Symbolic specifications arise in the analysis of transition systems, and in practice can be useful even for DFAs in situations where there is insufficient memory to store full transition tables. This is not uncommon in practice, because specifications are often built up as the conjunction of many small pieces. To use our earlier improvisation scheme for DFAs, we would need to explicitly construct the product of these au-tomata, which could be exponentially large. An implicit representation of the product by Boolean formulas, in contrast, will have linear size.
In bounded model checking [Biere et al. 1999], DFAs and NFAs can be represented by formulas as follows: Definition 6.3. A symbolic automaton is a transition system over states S ⊆ {0, 1} m and inputs Σ ⊆ {0, 1} k represented by: -a formula init(x) which is true iff x ∈ {0, 1} m is an initial state, -a formula acc(x) which is true iff x ∈ {0, 1} m is an accepting state, and -a formula δ(x, c, y) which is true iff there is a transition from x ∈ {0, 1} m to y ∈ {0, 1} m on input c ∈ {0, 1} k .
A symbolic automaton accepts words in Σ * according to the usual definition for NFAs.
Given a symbolic automaton D and a length bound n ∈ N, it is straightforward to generate a symbolic specification φ such that L(φ) = L(D)∩Σ n . The auxiliary variables of φ encode accepting paths of length n for a given word (see Biere et al. [1999] for details), and existentially quantifying them yields a formula whose models correspond exactly to accepting words of length n. So for the rest of the section we focus on symbolic specifications, but our results apply to symbolic automata in particular.
Since symbolic specifications can be arbitrary Boolean formulas, checking feasibility of CI problems involving them is obviously #P-hard. In the other direction, deciding membership of a word in a symbolic specification can be done with an NP oracle, so by Theorem 3.5 there is a polynomial-time improvisation scheme relative to a #P oracle (indeed, this holds even if we extend the definition of symbolic specification to allow a larger but bounded number of quantifiers). However, this scheme is not much use in practice, since #P-complete problems are still very difficult to solve. Instead, given the recent dramatic progress in SAT solvers, one can ask what is possible using only an NP oracle. As feasibility checking is #P-hard, by Toda's theorem an NP oracle does not let us solve the CI problem exactly unless PH collapses. However, we will show that an NP oracle does suffice to approximately solve the CI problem with symbolic specifications.
When discussing approximate solutions to a CI instance C, it will be useful to refer to improvisers for different values of ǫ, λ, and ρ than those required by C. Thus we may speak of an (ǫ, λ, ρ)-improvising distribution, (ǫ, λ, ρ)-feasibility, and so forth, and these have the obvious definitions.
Our method for solving CI problems with symbolic automata does not use the generic procedure of Theorem 3.4, since it depends on comparing the sizes of I and A and breaks down if these are only estimated (also, SYMB is not closed under differences). However, we still depend on techniques for uniform sampling, in this case approximate sampling of solutions to Boolean formulas using an NP oracle [Jerrum et al. 1986;Bellare et al. 2000;Chakraborty et al. 2014].
LEMMA 6.4. There is a probabilistic algorithm with an NP oracle that given a symbolic specification φ and any τ > 0, returns a random sample from L(φ) that is uniform up to a factor of 1 + τ in expected time polynomial in |φ| and 1/τ relative to the oracle.
PROOF. By our definition above, words in the language of φ are assignments to the w variables of φ(w, a) that can be extended to a complete satisfying assignment. For an arbitrary formula φ, counting the number of such words is exactly the problem #NSAT introduced by Valiant [1979] and also called projected model counting (since it counts models projected onto a subset of variables). Sampling from L(φ) is therefore equivalent to (approximate) uniform sampling of the models of φ(w, a) projected onto the variables w. This can be done with the algorithm of Chakraborty et al. [2014], which will run in the time required relative to an NP oracle. Unfortunately for technical reasons the algorithm works only for τ > 6.84. For general τ , we can modify the algorithm of Bellare et al. [2000] to do projection sampling (the modification is as described in Chakraborty et al. [2014]: apply the hash function only to the w variables, and when enumerating solutions using the NP oracle block all solutions that agree on the w variables with the solutions already enumerated). This algorithm has a constant probability of failing by returning ⊥ instead of a sample. If that happens we simply retry until the algorithm succeeds, and this only increases the expected runtime by a constant factor. We note that the algorithm of Bellare et al. [2000] actually samples exactly uniformly at random, and so would allow us to get somewhat better performance in theory, but with current SAT solvers the algorithm does not scale (unlike the algorithm of Chakraborty et al. [2014]). Now we are ready to describe our approximate improvisation algorithm. The algorithm avoids complementing S (needed above to count and sample from I \ A), and in fact does not require counting at all. In exchange, for a desired ǫ the algorithm may not return an improviser achieving the best possible λ and ρ, but the suboptimality is bounded.
PROOF. Conjoin H and S (renaming any shared auxiliary variables) to produce a symbolic specification A such that L(A) = L(H) ∩ L(S) = A. We build a probabilistic algorithm G NP that approximately samples uniformly from A with probability 1−ǫ and from I with probability ǫ. By Lemma 6.4, we can do this with tolerance τ in polynomial expected time relative to the NP oracle.
Therefore, it is possible to approximately solve the control improvisation problem when the specifications 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 having to loosen the randomness requirement somewhat.

MULTIPLE SOFT CONSTRAINTS
In this section, we discuss a generalized problem, multi-constraint control improvisation (MCI) where multiple soft constraints are allowed. We introduced an earlier form of this extension in Akkaya et al. [2016], but did not theoretically analyze it. Here we give a complete definition and a partial analysis. First, the conditions under which an instance is feasible seem to be much more complex, and we do not have a simple form for them. However, we can give an EXPTIME algorithm to decide feasibility, in fact an exponential-time improvisation scheme. Second, we show that even with DFA specifications, checking feasibility with multiple soft constraints is #P-hard.
Observe that the definition of control improvisation we have used so far effectively permits multiple hard constraints: requiring that several specifications H 1 , . . . , H k should all hold with probability 1 is equivalent to requiring that a single product specification H hold with probability 1. This property does not hold for soft constraints: requiring that both Pr[w ∈ A 1 ] ≥ 1/2 and Pr[w ∈ A 2 ] ≥ 1/2 is not in general equivalent to Pr[w ∈ A] ≥ p for any property A and probability p. Furthermore, there are situations such as the lighting control application of Akkaya et al. [2016] where the natural formalization of the problem uses multiple soft constraints. In this sense the asymmetry of the CI definition may be limiting.
The generalized definition we propose extends the basic one in a straightforward way: the soft specification S and corresponding error probability ǫ are replaced by several specifications S 1 , . . . , S k and error probabilities ǫ 1 , . . . , ǫ k .
Definition 7.1. Fix a hard specification H, soft specifications S 1 , . . . , S k , and length bounds m, n ∈ N. An improvisation is any word w ∈ L(H) such that m ≤ |w| ≤ n, and we write I for the set of all improvisations. An improvisation w ∈ I is i-admissible if w ∈ L(S i ), and we write A i for the set of all i-admissible improvisations.
Definition 7.3. Given C = (H, S 1 , . . . , S k , m, n, ǫ 1 , . . . , ǫ k , λ, ρ), the multi-constraint control improvisation (MCI) problem is to decide whether C is feasible, and if so to generate an improviser for C. The size |C| of an MCI instance is measured as for CI instances.
Definition 7.4. If A and B are classes of specifications, MCI(A,B) is the class of MCI instances C = (H, S 1 , . . . , S k , m, n, ǫ 1 , . . . , ǫ k , λ, ρ) where H ∈ A and S i ∈ B for all i ∈ [k]. When discussing decision problems, we use the same notation for the feasibility problem associated with the class (i.e. given C ∈ MCI(A,B), decide whether it is feasible).
Remark 7.5. Note that while the MCI definition treats the multiple soft constraints conjunctively (i.e. every constraint must hold), if the type of specification used supports Boolean operations then other types of soft constraint can be brought to this form. For example, the requirement Pr[w ∈ A 1 ] < 3/4 =⇒ Pr[w ∈ A 2 ∧ w ∈ A 3 ] ≥ 1/5 can be rewritten Pr[w ∈ A 1 ] ≥ 1/4 ∨ Pr[w ∈ (A 2 ∩ A 3 )] ≥ 1/5, and then each disjunct tested for feasibility separately. In general, we can reduce Boolean combinations of specifications inside probabilities to single specifications and write the resulting constraint in disjunctive normal form. Each disjunct is then an MCI instance (ignoring the very minor issue of strict vs. non-strict inequalities), and the original problem with a complex soft constraint is feasible iff one of the disjuncts is. This transformation could of course blow up the size of the problem exponentially -the point is that slightly more complex soft constraints can be handled within the MCI framework.
As was mentioned above, we do not know of a simple generalization of Theorem 3.1 giving necessary and sufficient conditions for the feasibility of an MCI instance. THEOREM 7.7. MCI(DFA,DFA) is #P-hard.
PROOF. We give a reduction from #SAT to MCI(DFA,DFA) similar to that used by Kannan et al. [1995] to prove hardness of counting the language of an NFA. Suppose we are given a formula F in conjunctive normal form, i.e. F = c 1 ∧ · · · ∧ c k where each c i is a disjunction of variables and their negations. If F has n variables V , putting them in some order we can view assignments to V as words in Σ n where Σ = {0, 1}. Then for each c i we can build a DFA D i accepting assignments that satisfy c i . We have one state for each v ∈ V , and start from the first variable under the order. If in state v we read a 1 and v occurs positively in c i , or we read a 0 and v occurs negatively, then the assignment satisfies c i and we transition to a chain of states that ensure we accept iff the word has length exactly n. Otherwise c i is not yet satisfied, so we move to the state for the next variable in the order. If we are already at the last variable, then c i is not satisfied by the assignment and we reject. Clearly, each D i has size polynomial in |F |, and the intersection ∩ i L(D i ) contains precisely the satisfying assignments of F . Now we proceed along similar lines to Theorem 4.5. For any N ∈ N, consider the MCI instance C N = (T , D 1 , . . . , D k , n, n, 0, . . . , 0, 0, 1/N ) where T is the trivial DFA accepting all of Σ * . For this instance we have I = Σ n and A i = L(D i ) for every i ∈ {1, . . . , k}. Since ǫ i = 0 for every i, an improvising distribution for C N must assign probability zero to all words not in ∩ i L(D i ). Therefore since no word can be assigned probability greater than ρ, if an improvising distribution exists then | ∩ i L(D i )| ≥ 1/ρ = N . Conversely, if | ∩ i L(D i )| ≥ N then a uniform distribution on ∩ i L(D i ) is clearly an improvising distribution for C N . So C N is feasible iff | ∩ i L(D i )| ≥ N . Since | ∩ i L(D i )| ≤ |Σ| n = 2 n , by binary search we can determine | ∩ i L(D i )| with polynomially-many MCI(DFA,DFA) queries, and thereby count the satisfying assignments of F .
Note that there is a gap between our upper and lower bounds for MCI(DFA,DFA): it is #P-hard, but our earlier algorithm puts it only in EXPTIME. A P #P algorithm, or more plausibly a PSPACE algorithm, would be very interesting. A multi-constraint version of Theorem 3.1 giving relatively simple conditions for feasibility would be helpful here.

CONCLUSION
In this paper, we introduced control improvisation, the problem of creating improvisers that randomly generate words subject to hard and soft specifications. We gave precise conditions for when improvisers exist, and investigated the complexity of finding improvisers for several major classes of automata and grammars. In particular, we showed that the control improvisation problem for DFAs, as well as for DFAs and unambiguous CFGs, can be solved in polynomial time. For NFAs and general CFGs, on the other hand, polynomial-time improvisation schemes are unlikely to exist, and would imply P = P #P . These results are summarized in Table I. We also studied the case where the specifications are presented symbolically instead of as explicit automata, and showed that the control improvisation problem can still be solved approximately using SAT solvers. Finally, we explored a generalized form of the problem allowing multiple soft constraints, and gave evidence suggesting that it is substantially more difficult than the basic problem: even for DFA specifications it is #P-hard, and we give only an EXPTIME algorithm.
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. There are also several clear directions for extending the problem definition other than allowing multiple soft constraints. For example, it would be useful in robotics applications for improvisations to be infinite words, with specifications given in linear temporal logic. We are also studying online or reactive ex- tensions where improvisations are generated incrementally in response to a possibly adversarial environment: this is useful in musical applications as well as in robotics.
A third type of extension would allow soft specifications to be different kinds of quantitative constraints. In a robotics application, for example, we might want to bound the average length of generated trajectories or the density with which they cover some region. Finally, we are also investigating further applications of control improvisation, particularly in the areas of testing, security, and privacy.

APPENDIX
For completeness, we prove results on counting and sampling from the language of a DFA in the form we need. The technique is classical, essentially that of Hickey and Cohen [1983]. PROOF. 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 ∞. Otherwise 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 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. LEMMA 4.3. There is a probabilistic algorithm that given a DFA D with finite language, returns a uniform random sample from L(D) in polynomial expected time.
PROOF. Prune D and compute the path counts p v as in Lemma 4.2 (since D has finite language, after pruning it is a DAG, as above). To every edge (u, v) in 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 ∈ 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 ) · (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(D). Since all probabilities are rational with denominators bounded by |Σ| |D| , this walk can be performed by a probabilistic algorithm S of size polynomial in |D|, with expected time bounded by a fixed polynomial in |D|. Then S returns a uniform sample from L(D), and it can be constructed in time polynomial in |D|.