@COMMENT This file was generated by bib2html.pl version 0.94
@COMMENT written by Patrick Riley
@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.},
}