--- res: bibo_abstract: - 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 setsimilarity 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.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Thomas A foaf_name: Henzinger, Thomas A foaf_surname: Henzinger foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87 orcid: 0000−0002−2985−7724 - foaf_Person: foaf_givenName: Jan foaf_name: Otop, Jan foaf_surname: Otop foaf_workInfoHomepage: http://www.librecat.org/personId=2FC5DA74-F248-11E8-B48F-1D18A9856A87 - foaf_Person: foaf_givenName: Roopsha foaf_name: Samanta, Roopsha foaf_surname: Samanta foaf_workInfoHomepage: http://www.librecat.org/personId=3D2AAC08-F248-11E8-B48F-1D18A9856A87 bibo_doi: 10.4230/LIPIcs.FSTTCS.2014.431 bibo_volume: 29 dct_date: 2014^xs_gYear dct_language: eng dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@ dct_title: Lipschitz robustness of finite-state transducers@ ...