Formally Verified Linear-Time Invertible Lexing
This paper presents ZipLex, a formally verified framework in Scala that achieves linear-time invertible lexical analysis with longest-match semantics by combining a novel token sequence abstraction with verified data structures like zippers and memoization, demonstrating performance comparable to unverified tools while providing rigorous proofs of correctness and invertibility.