Which classes of origin graphs are generated by transducers?

Mikołaj Bojanczyk; Laure Daviaud; Bruno Guillon; Vincent Penelle

doi:10.4230/LIPIcs.ICALP.2017.114

Which classes of origin graphs are generated by transducers?

Mikołaj Bojanczyk, Laure Daviaud, Bruno Guillon, Vincent Penelle

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

16 Citations (Scopus)

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.

Original language	English
Title of host publication	44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
Editors	Anca Muscholl, Piotr Indyk, Fabian Kuhn, Ioannis Chatzigiannakis
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959770415
DOIs	https://doi.org/10.4230/LIPIcs.ICALP.2017.114
Publication status	Published - 1 Jul 2017
Externally published	Yes
Event	44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 - Warsaw, Poland Duration: 10 Jul 2017 → 14 Jul 2017

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	80
ISSN (Print)	1868-8969

Conference

Conference	44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
Country/Territory	Poland
City	Warsaw
Period	10/07/17 → 14/07/17

Keywords

MSO definability
Origin semantics
Streaming string transducers
String-to-string transductions

Access to Document

10.4230/LIPIcs.ICALP.2017.114Licence: CC BY

Cite this

Bojanczyk, M., Daviaud, L., Guillon, B., & Penelle, V. (2017). Which classes of origin graphs are generated by transducers? In A. Muscholl, P. Indyk, F. Kuhn, & I. Chatzigiannakis (Eds.), 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 [114] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 80). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2017.114

Bojanczyk, Mikołaj ; Daviaud, Laure ; Guillon, Bruno ; Penelle, Vincent. / Which classes of origin graphs are generated by transducers?. 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. editor / Anca Muscholl ; Piotr Indyk ; Fabian Kuhn ; Ioannis Chatzigiannakis. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{a87c4f466e20444f81f0929f236c7099,

title = "Which classes of origin graphs are generated by transducers?",

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

keywords = "MSO definability, Origin semantics, Streaming string transducers, String-to-string transductions",

author = "Miko{\l}aj Bojanczyk and Laure Daviaud and Bruno Guillon and Vincent Penelle",

note = "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: {\textcopyright} Miko{\l}aj Bojanczyk, Laure Daviaud, Bruno Guillon, and Vincent Penelle;.; 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 ; Conference date: 10-07-2017 Through 14-07-2017",

year = "2017",

month = jul,

day = "1",

doi = "10.4230/LIPIcs.ICALP.2017.114",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Anca Muscholl and Piotr Indyk and Fabian Kuhn and Ioannis Chatzigiannakis",

booktitle = "44th International Colloquium on Automata, Languages, and Programming, ICALP 2017",

}

Bojanczyk, M, Daviaud, L, Guillon, B & Penelle, V 2017, Which classes of origin graphs are generated by transducers? in A Muscholl, P Indyk, F Kuhn & I Chatzigiannakis (eds), 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017., 114, Leibniz International Proceedings in Informatics, LIPIcs, vol. 80, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Warsaw, Poland, 10/07/17. https://doi.org/10.4230/LIPIcs.ICALP.2017.114

Which classes of origin graphs are generated by transducers? / Bojanczyk, Mikołaj; Daviaud, Laure; Guillon, Bruno; Penelle, Vincent.

44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. ed. / Anca Muscholl; Piotr Indyk; Fabian Kuhn; Ioannis Chatzigiannakis. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. 114 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 80).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution