License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.120
URN: urn:nbn:de:0030-drops-164613
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16461/
Go to the corresponding LIPIcs Volume Portal

Douéneau-Tabot, Gaëtan

Hiding Pebbles When the Output Alphabet Is Unary

pdf-format:
LIPIcs-ICALP-2022-120.pdf (0.8 MB)

Abstract

Pebble transducers are nested two-way transducers which can drop marks (named "pebbles") on their input word. Blind transducers have been introduced by Nguyên et al. as a subclass of pebble transducers, which can nest two-way transducers but cannot drop pebbles on their input.
In this paper, we study the classes of functions computed by pebble and blind transducers, when the output alphabet is unary. Our main result shows how to decide if a function computed by a pebble transducer can be computed by a blind transducer. We also provide characterizations of these classes in terms of Cauchy and Hadamard products, in the spirit of rational series. Furthermore, pumping-like characterizations of the functions computed by blind transducers are given.

BibTeX - Entry

@InProceedings{doueneautabot:LIPIcs.ICALP.2022.120,
  author =	{Dou\'{e}neau-Tabot, Ga\"{e}tan},
  title =	{{Hiding Pebbles When the Output Alphabet Is Unary}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{120:1--120:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16461},
  URN =		{urn:nbn:de:0030-drops-164613},
  doi =		{10.4230/LIPIcs.ICALP.2022.120},
  annote =	{Keywords: polyregular functions, pebble transducers, rational series, factorization forests, Cauchy product, Hadamard product}
}

Keywords: polyregular functions, pebble transducers, rational series, factorization forests, Cauchy product, Hadamard product
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

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