Pushing the Limit of 1-Minimality of Language-Agnostic Program Reduction
summary
Vulcan is a language-agnostic postprocessor built on Perses that repeatedly applies three auxiliary reducers—identifier replacement, subtree replacement guided by the grammar, and local exhaustive enumeration—to break 1-minimal local minima. The prototype shrinks a Perses result from 116 to 56 tokens in an example, yields on average ~35% smaller C outputs (33.6% C, 21.6% Rust, 31.3% SMT-LIBv2 reported), can further trim C-Reduce outputs ≈10%, and trades time for size (≈2.5× slower overall, up to 7–8.5× on small suites).
AI-written summary · about
chapters (14)
- 0:00Program reduction intro
- 1:04How reduction works
- 2:32One-minimality limits in Perses
- 5:19Beyond one-minimality
- 6:00Vulcan framework
- 7:03Identifier replacement reducer
- 8:30Subtree replacement reducer
- 9:32Local exhaustive enumeration
- 10:57Evaluation results
- 12:44Vulcan trade-offs
- 13:05Q&A session part one
- 14:09Q&A session part two
- 15:15Q&A session part three
- 16:00Q&A session part four
related talks
15mBoosting Program Reduction with the Missing Piece of Syntax-Guided Transformations
41mCan you make that smaller? An introduction to test-case reduction
20mSemantic Reification: A New Paradigm for Random Program Generation
41mRelational Interpreters, Program Synthesis, and Barliman
56mThe Rational Programmer, An Investigative Method for Programming Language Prag...
15mGrammar-Based Testing for Little Languages: An Experience Report with Student Compilers
18mOptimizing Input Minimization in Kernel Fuzzing
34mWeak Versions of Extended Resolution