2026-07-23T05:42:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4861 2024-03-06T10:35:27Z ddc:004 open_access

Lipschitz Robustness of Finite-state Transducers Henzinger, Thomas A. Otop, Jan Samanta, Roopsha Robustness Transducers Weighted Automata We investigate the problem of checking if a finite-state transducer is robust to uncertainty in its input. Our notion of robustness is based on the analytic notion of Lipschitz continuity - a transducer is K-(Lipschitz) robust if the perturbation in its output is at most K times the perturbation in its input. We quantify input and output perturbation using similarity functions. We show that K-robustness is undecidable even for deterministic transducers. We identify a class of functional transducers, which admits a polynomial time automata-theoretic decision procedure for K-robustness. This class includes Mealy machines and functional letter-to-letter transducers. We also study K-robustness of nondeterministic transducers. Since a nondeterministic transducer generates a set of output words for each input word, we quantify output perturbation using set-similarity functions. We show that K-robustness of nondeterministic transducers is undecidable, even for letter-to-letter transducers. We identify a class of set-similarity functions which admit decidable K-robustness of letter-to-letter transducers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas A. Henzinger and Jan Otop and Roopsha Samanta 2014 Is Part Of LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2014.431 urn:nbn:de:0030-drops-48614 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.431 eng https://creativecommons.org/licenses/by/3.0/legalcode