@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Sanjit Seshia's publication pages at http://www.eecs.berkeley.edu/~sseshia
@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.},
}