  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 #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.
