Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.114
URN: urn:nbn:de:0030-drops-73984
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7398/
Bojanczyk, Mikolaj ; Daviaud, Laure ; Guillon, Bruno ; Penelle, Vincent
Which Classes of Origin Graphs Are Generated by Transducers
| pdf-format: |
|
Abstract
We study various models of transducers equipped with origin information. We consider the semantics of these models as particular graphs, called origin graphs, and we characterise the families of such graphs recognised by streaming string transducers.
BibTeX - Entry
@InProceedings{bojanczyk_et_al:LIPIcs:2017:7398,
author = {Mikolaj Bojanczyk and Laure Daviaud and Bruno Guillon and Vincent Penelle},
title = {{Which Classes of Origin Graphs Are Generated by Transducers}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {114:1--114:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-041-5},
ISSN = {1868-8969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7398},
URN = {urn:nbn:de:0030-drops-73984},
doi = {10.4230/LIPIcs.ICALP.2017.114},
annote = {Keywords: Streaming String Transducers, Origin Semantics, String-to-String Transductions, MSO Definability}
}
| Keywords: | Streaming String Transducers, Origin Semantics, String-to-String Transductions, MSO Definability | |
| Seminar: | 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 07.07.2017 |
