Certified Symbolic Finite Transducers: Formalization and Applications to String Analysis
Shuanglong Kan, Anthony W. Lin · 2025
Read Certified Symbolic Finite Transducers: Formalization and Applications to String Analysis by Shuanglong Kan, Anthony W. Lin (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-2504-07203.txt.
Description
Shuanglong Kan and Anthony Lin formalize symbolic finite transducers inside a proof assistant, with machine-checked proofs. Their twenty twenty-five paper builds on automata theory, the base of regular expressions in languages like Python and JavaScript. Transducers both read and transform strings, a step beyond plain automata.
Symbolic versions label moves with formulas, so alphabets can be endless. Past certified work covered symbolic automata but not transducers. The team closes that gap with a formal model fit for real use. String analysis tools, from sanitizers to parsers, can then rest on proven rules. The work serves both theory and the safety of everyday text code.
Catalog record
| CREATOR | Shuanglong Kan, Anthony W. Lin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-07203