Control Improvisation

Daniel J. Fremont, Alexandre Donzé, Sanjit A. Seshia, and David Wessel. Control Improvisation. ArXiv e-prints, November 2014.

Download

[HTML] 

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 exhibition of a specified amount of randomness. This problem has proved useful, for example, in generating musical improvisations that satisfy rhythmic and melodic constraints, where admissibility was 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 SAT solvers can be used to approximately solve some of the intractable cases.

BibTeX

@article{fremont-arxiv14,
  author    = {Daniel J. Fremont and
               Alexandre Donz{\'{e}} and
               Sanjit A. Seshia and
               David Wessel},
  title     = {Control Improvisation},
   journal = {ArXiv e-prints},
   archivePrefix = "arXiv",
   eprint = {1411.0698},
  month = "November",
  year      = {2014},
  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 exhibition of a specified amount of randomness. This problem has proved useful, for example, in generating musical improvisations that satisfy rhythmic and melodic constraints, where admissibility was 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 SAT solvers can be used to approximately solve some of the intractable cases.},
}