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

CREATORShuanglong Kan, Anthony W. Lin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-07203

Browse the full library · About the Tower of Babel