@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
@inproceedings{fremont-fsttcs15,
  author    = {Daniel J. Fremont and
               Alexandre Donz{\'{e}} and
               Sanjit A. Seshia and
               David Wessel},
  title     = {Control Improvisation},
  booktitle = {35th {IARCS} Annual Conference on Foundation of Software Technology
               and Theoretical Computer Science (FSTTCS)}, 
  pages     = {463--474},
  Year = {2015},
  Month = {December},
  series    = {LIPIcs},
  volume    = {45},
  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 #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.},
}