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.STACS.2019.2
URN: urn:nbn:de:0030-drops-102410
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10241/
Muscholl, Anca ;
Puppis, Gabriele
The Many Facets of String Transducers (Invited Talk)
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 |
|
Collection: |
|
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
12.03.2019 |
