Skip to main content
eScholarship
Open Access Publications from the University of California

Control improvisation

  • Author(s): Fremont, DJ
  • Donzé, A
  • Seshia, SA
  • Wessel, D
  • et al.

Published Web Location

http://www.eecs.berkeley.edu/~sseshia/pubdir/fsttcs15.pdf
No data is associated with this publication.
Abstract

© Daniel J. Fremont, Alexandre Donzé, Sanjit A. Seshia, and David Wessel;. 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.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item