License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.431
URN: urn:nbn:de:0030-drops-48614
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4861/
Go to the corresponding LIPIcs Volume Portal

Henzinger, Thomas A. ; Otop, Jan ; Samanta, Roopsha

Lipschitz Robustness of Finite-state Transducers

pdf-format:
37.pdf (0.5 MB)

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

BibTeX - Entry

@InProceedings{henzinger_et_al:LIPIcs:2014:4861,
  author =	{Thomas A. Henzinger and Jan Otop and Roopsha Samanta},
  title =	{{Lipschitz Robustness of Finite-state Transducers}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{431--443},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4861},
  URN =		{urn:nbn:de:0030-drops-48614},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.431},
  annote =	{Keywords: Robustness, Transducers, Weighted Automata}
}

Keywords: Robustness, Transducers, Weighted Automata
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI