DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2016.114

Minimizing Resources of Sweeping and Streaming String Transducers

Authors: Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract

We consider minimization problems for natural parameters of word transducers: the number of passes performed by two-way transducers and the number of registers used by streaming transducers. We show how to compute in ExpSpace the minimum number of passes needed to implement a transduction given as sweeping transducer, and we provide effective constructions of transducers of (worst-case optimal) doubly exponential size. We then consider streaming transducers where concatenations of registers are forbidden in the register updates. Based on a correspondence between the number of passes of sweeping transducers and the number of registers of equivalent concatenation-free streaming transducers, we derive a minimization procedure for the number of registers of concatenation-free streaming transducers.

Cite as

Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. Minimizing Resources of Sweeping and Streaming String Transducers. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 114:1-114:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{baschenis_et_al:LIPIcs.ICALP.2016.114,
  author =	{Baschenis, F\'{e}lix and Gauwin, Olivier and Muscholl, Anca and Puppis, Gabriele},
  title =	{{Minimizing Resources of Sweeping and Streaming String Transducers}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{114:1--114:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.114},
  URN =		{urn:nbn:de:0030-drops-62496},
  doi =		{10.4230/LIPIcs.ICALP.2016.114},
  annote =	{Keywords: word transducers, streaming, 2-way, sweeping transducers, minimization}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2015.178

One-way Definability of Sweeping Transducer

Authors: Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract

Two-way finite-state transducers on words are strictly more expressive than one-way transducers. It has been shown recently how to decide if a two-way functional transducer has an equivalent one-way transducer, and the complexity of the algorithm is non-elementary. We propose an alternative and simpler characterization for sweeping functional transducers, namely, for transducers that can only reverse their head direction at the extremities of the input. Our algorithm works in 2EXPSPACE and, in the positive case, produces an equivalent one-way transducer of doubly exponential size. We also show that the bound on the size of the transducer is tight, and that the one-way definability problem is undecidable for (sweeping) non-functional transducers.

Cite as

Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. One-way Definability of Sweeping Transducer. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 178-191, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{baschenis_et_al:LIPIcs.FSTTCS.2015.178,
  author =	{Baschenis, F\'{e}lix and Gauwin, Olivier and Muscholl, Anca and Puppis, Gabriele},
  title =	{{One-way Definability of Sweeping Transducer}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{178--191},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.178},
  URN =		{urn:nbn:de:0030-drops-56297},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.178},
  annote =	{Keywords: Regular word transductions, sweeping transducers, one-way definability}
}

Search Results

Documents authored by Baschenis, Félix

Minimizing Resources of Sweeping and Streaming String Transducers

Abstract

Cite as

One-way Definability of Sweeping Transducer

Abstract

Cite as

Thanks for your feedback!

Could not send message