Solving Not-Substring with Flat Abstraction
summary
Proposes a concrete CEGAR-based method using flat abstraction that encodes non-substring into linear integer (Presburger) constraints and implements it in a prototype STR prototype tool. STR runs two engines in parallel, using Ostrich for UNSAT while the flattening engine reduces to Presburger and only answers SAT. Evaluation on benchmarks (biopython, django, thefuck, LeetCode, PyEx, CVC4-str, etc.) shows competitive results versus Z3 and CVC4 and slightly better performance on many sets.
AI-written summary · about