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