--- _id: '1870' abstract: - lang: eng text: 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. alternative_title: - LIPIcs author: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Jan full_name: Otop, Jan id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87 last_name: Otop - first_name: Roopsha full_name: Samanta, Roopsha id: 3D2AAC08-F248-11E8-B48F-1D18A9856A87 last_name: Samanta citation: ama: 'Henzinger TA, Otop J, Samanta R. Lipschitz robustness of finite-state transducers. In: Leibniz International Proceedings in Informatics, LIPIcs. Vol 29. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2014:431-443. doi:10.4230/LIPIcs.FSTTCS.2014.431' apa: 'Henzinger, T. A., Otop, J., & Samanta, R. (2014). Lipschitz robustness of finite-state transducers. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 29, pp. 431–443). Delhi, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2014.431' chicago: Henzinger, Thomas A, Jan Otop, and Roopsha Samanta. “Lipschitz Robustness of Finite-State Transducers.” In Leibniz International Proceedings in Informatics, LIPIcs, 29:431–43. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. https://doi.org/10.4230/LIPIcs.FSTTCS.2014.431. ieee: T. A. Henzinger, J. Otop, and R. Samanta, “Lipschitz robustness of finite-state transducers,” in Leibniz International Proceedings in Informatics, LIPIcs, Delhi, India, 2014, vol. 29, pp. 431–443. ista: 'Henzinger TA, Otop J, Samanta R. 2014. Lipschitz robustness of finite-state transducers. Leibniz International Proceedings in Informatics, LIPIcs. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 29, 431–443.' mla: Henzinger, Thomas A., et al. “Lipschitz Robustness of Finite-State Transducers.” Leibniz International Proceedings in Informatics, LIPIcs, vol. 29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 431–43, doi:10.4230/LIPIcs.FSTTCS.2014.431. short: T.A. Henzinger, J. Otop, R. Samanta, in:, Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 431–443. conference: end_date: 2014-12-17 location: Delhi, India name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science' start_date: 2014-12-15 date_created: 2018-12-11T11:54:27Z date_published: 2014-12-01T00:00:00Z date_updated: 2021-01-12T06:53:45Z day: '01' ddc: - '004' department: - _id: ToHe doi: 10.4230/LIPIcs.FSTTCS.2014.431 file: - access_level: open_access checksum: 7b1aff1710a8bffb7080ec07f62d9a17 content_type: application/pdf creator: system date_created: 2018-12-12T10:09:11Z date_updated: 2020-07-14T12:45:19Z file_id: '4734' file_name: IST-2017-804-v1+1_37.pdf file_size: 562151 relation: main_file file_date_updated: 2020-07-14T12:45:19Z has_accepted_license: '1' intvolume: ' 29' language: - iso: eng license: https://creativecommons.org/licenses/by/4.0/ month: '12' oa: 1 oa_version: Published Version page: 431 - 443 publication: Leibniz International Proceedings in Informatics, LIPIcs publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '5227' pubrep_id: '804' quality_controlled: '1' status: public title: Lipschitz robustness of finite-state transducers tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87 volume: 29 year: '2014' ...