2026-08-10T23:00:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7398 2024-03-06T10:40:31Z ddc:004 open_access

Which Classes of Origin Graphs Are Generated by Transducers Bojanczyk, Mikolaj Daviaud, Laure Guillon, Bruno Penelle, Vincent Streaming String Transducers Origin Semantics String-to-String Transductions MSO Definability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikolaj Bojanczyk and Laure Daviaud and Bruno Guillon and Vincent Penelle 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.114 urn:nbn:de:0030-drops-73984 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.114 eng https://creativecommons.org/licenses/by/3.0/legalcode