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

CREATORDenghang Hu, Taolue Chen, Philipp Rümmer, Fu Song, Zhilin Wu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-00948

Browse the full library · About the Tower of Babel