文章基本信息

标题：Control Improvisation
本地全文：下载
作者：Daniel J. Fremont ; Alexandre Donz{\'e ; Sanjit A. Seshia 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：45
页码：463-474
DOI：10.4230/LIPIcs.FSTTCS.2015.463
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：finite automata; random sampling; Boolean satisfiability; testing; computational music; control theory