2026-07-22T03:56:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16461 2024-03-06T10:57:32Z ddc:004 open_access

Hiding Pebbles When the Output Alphabet Is Unary Douéneau-Tabot, Gaëtan polyregular functions pebble transducers rational series factorization forests Cauchy product Hadamard product 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gaëtan Douéneau-Tabot 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.120 urn:nbn:de:0030-drops-164613 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.120 eng https://creativecommons.org/licenses/by/4.0/legalcode