Decision Procedure for A Theory of String Sequences
Denghang Hu, Taolue Chen, Philipp Rümmer, Fu Song, Zhilin Wu · 2025
Read Decision Procedure for A Theory of String Sequences by Denghang Hu, Taolue Chen, Philipp Rümmer, Fu Song, Zhilin Wu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00948.txt.
Description
Denghang Hu leads five authors in total, with Taolue Chen, Philipp Rummer, Fu Song, and Zhilin Wu, in giving a decision procedure for a theory of string sequences. SMT solvers support sequences for modeling arrays and lists, and strings are intimately related, yet operations such as regex matching, splitting, and joining are typically not directly supported.
Hu and his co-authors propose a theory of string sequences and study its satisfiability. The theory is undecidable in general, but decidability returns for the straight-line fragment. They encode each string sequence as a string and each operation as a string operation, computing pre-images with automata inside the OSTRICH framework. Their tool performs well on benchmarks from JavaScript programs and templates.
Catalog record
| CREATOR | Denghang Hu, Taolue Chen, Philipp Rümmer, Fu Song, Zhilin Wu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-00948