2026-08-19T03:39:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5659 2024-03-06T10:36:46Z ddc:004 open_access

Control Improvisation Fremont, Daniel J. Donzé, Alexandre Seshia, Sanjit A. Wessel, David finite automata random sampling Boolean satisfiability testing computational music control theory 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel J. Fremont and Alexandre Donzé and Sanjit A. Seshia and David Wessel 2015 Is Part Of LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2015.463 urn:nbn:de:0030-drops-56596 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.463 eng https://creativecommons.org/licenses/by/3.0/legalcode