Control Improvisation
Daniel J. Fremont, Alexandre Donze, Sanjit Seshia, David Wessel

Citation
Daniel J. Fremont, Alexandre Donze, Sanjit Seshia, David Wessel. "Control Improvisation". Proc. FSTTCS, December, 2015.

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 SAT solvers can be used to approximately solve some of the intractable cases.

Electronic downloads


Internal. This publication has been marked by the author for TerraSwarm-only distribution, so electronic downloads are not available without logging in.
Citation formats  
  • HTML
    Daniel J. Fremont, Alexandre Donze, Sanjit Seshia, David
    Wessel. <a
    href="http://www.terraswarm.org/pubs/465.html"
    >Control Improvisation</a>, Proc. FSTTCS, December,
    2015.
  • Plain text
    Daniel J. Fremont, Alexandre Donze, Sanjit Seshia, David
    Wessel. "Control Improvisation". Proc. FSTTCS,
    December, 2015.
  • BibTeX
    @inproceedings{FremontDonzeSeshiaWessel15_ControlImprovisation,
        author = {Daniel J. Fremont and Alexandre Donze and Sanjit
                  Seshia and David Wessel},
        title = {Control Improvisation},
        booktitle = {Proc. FSTTCS},
        month = {December},
        year = {2015},
        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 SAT solvers can be used to
                  approximately solve some of the intractable cases.},
        URL = {http://terraswarm.org/pubs/465.html}
    }
    

Posted by Daniel J. Fremont on 21 Nov 2014.
Groups: tools

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.