Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Muscholl, Anca; Puppis, Gabriele https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-102410
URL:

;

The Many Facets of String Transducers (Invited Talk)

pdf-format:


Abstract

Regular word transductions extend the robust notion of regular languages from a qualitative to a quantitative reasoning. They were already considered in early papers of formal language theory, but turned out to be much more challenging. The last decade brought considerable research around various transducer models, aiming to achieve similar robustness as for automata and languages. In this paper we survey some older and more recent results on string transducers. We present classical connections between automata, logic and algebra extended to transducers, some genuine definability questions, and review approaches to the equivalence problem.

BibTeX - Entry

@InProceedings{muscholl_et_al:LIPIcs:2019:10241,
  author =	{Anca Muscholl and Gabriele Puppis},
  title =	{{The Many Facets of String Transducers (Invited Talk)}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{2:1--2:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10241},
  doi =		{10.4230/LIPIcs.STACS.2019.2},
  annote =	{Keywords: String transducers, complexity}
}

Keywords: String transducers, complexity
Seminar: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue date: 2019
Date of publication: 12.03.2019


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