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

Citation
Daniel J. Fremont, Alexandre Donze, Sanjit Seshia, David Wessel. "Control Improvisation". Talk or presentation, 14, October, 2015; Poster presented at the 2015 TerraSwarm Annual Meeting.

Abstract
We formalize and analyze a new automata-theoretic problem termed control improvisation, which captures the elements common to many problems involving random generation of variations on a reference sequence. 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. This problem has proved useful, for example, in 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, and how our techniques can be generalized from automata to context-free grammars.

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/649.html"><i>Control
  Improvisation</i></a>, Talk or presentation, 
  14, October, 2015; Poster presented at the <a
  href="http://terraswarm.org/conferences/15/annual"
  >2015 TerraSwarm Annual Meeting</a>.

• Plain text

  Daniel J. Fremont, Alexandre Donze, Sanjit Seshia, David
  Wessel. "Control Improvisation". Talk or
  presentation,  14, October, 2015; Poster presented at the
  <a
  href="http://terraswarm.org/conferences/15/annual"
  >2015 TerraSwarm Annual Meeting</a>.

• BibTeX

  @presentation{FremontDonzeSeshiaWessel15_ControlImprovisation,
      author = {Daniel J. Fremont and Alexandre Donze and Sanjit
                Seshia and David Wessel},
      title = {Control Improvisation},
      day = {14},
      month = {October},
      year = {2015},
      note = {Poster presented at the <a
                href="http://terraswarm.org/conferences/15/annual"
                >2015 TerraSwarm Annual Meeting</a>.},
      abstract = {We formalize and analyze a new automata-theoretic
                problem termed control improvisation, which
                captures the elements common to many problems
                involving random generation of variations on a
                reference sequence. 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. This problem has proved
                useful, for example, in 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,
                and how our techniques can be generalized from
                automata to context-free grammars.},
      URL = {http://terraswarm.org/pubs/649.html}
  }
  

Posted by Daniel J. Fremont on 9 Oct 2015.
Groups: tools