TY - GEN
T1 - Which classes of origin graphs are generated by transducers?
AU - Bojanczyk, Mikołaj
AU - Daviaud, Laure
AU - Guillon, Bruno
AU - Penelle, Vincent
N1 - Funding Information:
This paper is part of lipa, a project funded by the European Research Council (erc) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 683080).
Publisher Copyright:
© Mikołaj Bojanczyk, Laure Daviaud, Bruno Guillon, and Vincent Penelle;.
PY - 2017/7/1
Y1 - 2017/7/1
N2 - 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.
AB - 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.
KW - MSO definability
KW - Origin semantics
KW - Streaming string transducers
KW - String-to-string transductions
UR - http://www.scopus.com/inward/record.url?scp=85027262498&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2017.114
DO - 10.4230/LIPIcs.ICALP.2017.114
M3 - Conference contribution
AN - SCOPUS:85027262498
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
A2 - Muscholl, Anca
A2 - Indyk, Piotr
A2 - Kuhn, Fabian
A2 - Chatzigiannakis, Ioannis
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
Y2 - 10 July 2017 through 14 July 2017
ER -