Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Equivalence of Extended Symbolic Finite Transducers

Loris D'Antoni and Margus Veanes

Abstract

Symbolic Finite Transducers augment classic transducers with symbolic alphabets represented as parametric theories. Such extension enables succinctness and the use of potentially infinite alphabets while preserving closure and decidability properties. Extended Symbolic Finite Transducers further extend these objects by allowing transitions to read consecutive input elements in a single step. While when the alphabet is finite this extension does not add expressiveness, it does so when the alphabet is symbolic. We show how such increase in expressiveness causes decision problems such as equivalence to become undecidable and closure properties such as composition to stop holding. We also investigate how the automata counterpart, Extended Symbolic Finite Automata, differs from Symbolic Finite Automata. We then introduce the subclass of Cartesian Extended Symbolic Finite Transducers in which guards are limited to conjunctions of unary predicates. Our main result is an equivalence algorithm for such subclass in the single-valued case. Finally, we model real world problems with Cartesian Extended Symbolic Finite Transducers and use the equivalence algorithm to prove their correctness.

Details

Publication typeInproceedings
Published in25th International Conference on Computer Aided Verification (CAV'13)
SeriesLNCS
PublisherSpringer

Previous versions

Loris D'Antoni and Margus Veanes. Equivalence of Extended Symbolic Finite Transducers, Microsoft Research, January 2013.

> Publications > Equivalence of Extended Symbolic Finite Transducers