## 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

### 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.}, }