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 proceedingConference 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 languageEnglish
Title of host publication44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
EditorsAnca Muscholl, Piotr Indyk, Fabian Kuhn, Ioannis Chatzigiannakis
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770415
DOIs
Publication statusPublished - 1 Jul 2017
Externally publishedYes
Event44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 - Warsaw, Poland
Duration: 10 Jul 201714 Jul 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume80
ISSN (Print)1868-8969

Conference

Conference44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
Country/TerritoryPoland
CityWarsaw
Period10/07/1714/07/17

Keywords

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

Cite this