Control Improvisation

Daniel J. Fremont, Alexandre Donzé, Sanjit A. Seshia, and David Wessel. Control Improvisation. In 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), pp. 463–474, LIPIcs 45, December 2015.

Download

[pdf] 

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

BibTeX

@inproceedings{fremont-fsttcs15,
  author    = {Daniel J. Fremont and
               Alexandre Donz{\'{e}} and
               Sanjit A. Seshia and
               David Wessel},
  title     = {Control Improvisation},
  booktitle = {35th {IARCS} Annual Conference on Foundation of Software Technology
               and Theoretical Computer Science (FSTTCS)}, 
  pages     = {463--474},
  Year = {2015},
  Month = {December},
  series    = {LIPIcs},
  volume    = {45},
  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 Boolean satisfiability (SAT) solvers can 
be used to approximately solve some of the intractable cases.},
}