---
_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'
...