License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7398/
Go to the corresponding LIPIcs Volume Portal

Bojanczyk, Mikolaj ; Daviaud, Laure ; Guillon, Bruno ; Penelle, Vincent

Which Classes of Origin Graphs Are Generated by Transducers

pdf-format:
LIPIcs-ICALP-2017-114.pdf (8 MB)

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
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI