Document Open Access Logo

Control Improvisation

Authors Daniel J. Fremont, Alexandre Donzé, Sanjit A. Seshia, David Wessel

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.463.pdf
  • Filesize: 499 kB
  • 12 pages

Document Identifiers

Author Details

Daniel J. Fremont
Alexandre Donzé
Sanjit A. Seshia
David Wessel

Cite As Get BibTex

Daniel J. Fremont, Alexandre Donzé, Sanjit A. Seshia, and David Wessel. Control Improvisation. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 463-474, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.FSTTCS.2015.463

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.

Subject Classification

Keywords
  • finite automata
  • random sampling
  • Boolean satisfiability
  • testing
  • computational music
  • control theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Gérard Assayag, Georges Bloch, Marc Chemillier, Benjamin Lévy, and Shlomo Dubnov. OMax. http://repmus.ircam.fr/omax/home, 2012.
  2. Gérard Assayag and Shlomo Dubnov. Using factor oracles for machine improvisation. Soft Comput., 8(9):604-610, 2004. Google Scholar
  3. Mihir Bellare, Oded Goldreich, and Erez Petrank. Uniform generation of NP-witnesses using an NP-oracle. Information and Computation, 163(2):510-526, 2000. Google Scholar
  4. Armin Biere, Alessandro Cimatti, Edmund M. Clarke, and Yunshan Zhu. Symbolic model checking without BDDs. In 5th International Conference on Tools and Algorithms for Construction and Analysis of Systems, pages 193-207, 1999. Google Scholar
  5. Christos G. Cassandras and Stéphane Lafortune. Introduction to Discrete Event Systems. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006. Google Scholar
  6. Supratik Chakraborty, Kuldeep S. Meel, and Moshe Y. Vardi. Balancing scalability and uniformity in SAT witness generator. In 51st Design Automation Conference, pages 1-6. ACM, 2014. Google Scholar
  7. Loek Cleophas, Gerard Zwaan, and Bruce W. Watson. Constructing factor oracles. In In Proceedings of the 3rd Prague Stringology Conference, 2003. Google Scholar
  8. Anne Condon and Richard J. Lipton. On the complexity of space bounded interactive proofs. In 30th Annual Symposium on Foundations of Computer Science, pages 462-467. IEEE, 1989. Google Scholar
  9. Alain Denise, Marie-Claude Gaudel, Sandrine-Dominique Gouraud, Richard Lassaigne, and Sylvain Peyronnet. Uniform random sampling of traces in very large models. In 1st International Workshop on Random Testing, pages 10-19. ACM, 2006. Google Scholar
  10. Alexandre Donzé, Rafael Valle, Ilge Akkaya, Sophie Libkind, Sanjit A. Seshia, and David Wessel. Machine improvisation with formal specifications. In Proceedings of the 40th International Computer Music Conference (ICMC), September 2014. Google Scholar
  11. Daniel J. Fremont, Alexandre Donzé, Sanjit A. Seshia, and David Wessel. Control improvisation. arXiv preprint arXiv:1411.0698, 2015. Google Scholar
  12. Andrew D. Gordon, Thomas A. Henzinger, Aditya V. Nori, and Sriram K. Rajamani. Probabilistic programming. In International Conference on Software Engineering (ICSE Future of Software Engineering). IEEE, May 2014. Google Scholar
  13. Timothy Hickey and Jacques Cohen. Uniform random generation of strings in a context-free language. SIAM Journal on Computing, 12(4):645-655, 1983. Google Scholar
  14. Sampath Kannan, Z. Sweedyk, and Steve Mahaney. Counting and random generation of strings in regular languages. In Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 551-557. SIAM, 1995. Google Scholar
  15. Stéphane Lafortune. Personal Communication, 2015. Google Scholar
  16. Edward A. Lee. Personal Communication, 2013. Google Scholar
  17. Masakazu Nasu and Namio Honda. Mappings induced by PGSM-mappings and some recursively unsolvable problems of finite probabilistic automata. Information and Control, 15(3):250-273, 1969. Google Scholar
  18. Michael O. Rabin. Probabilistic automata. Information and Control, 6(3):230-245, 1963. Google Scholar
  19. R. Rowe. Machine Musicianship. MIT Press, 2001. Google Scholar
  20. Michael Sutton, Adam Greene, and Pedram Amini. Fuzzing: Brute Force Vulnerability Discovery. Addison-Wesley, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact