Document Open Access Logo

Pebble Transducers with Unary Output

Author Gaëtan Douéneau-Tabot

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.40.pdf
  • Filesize: 0.83 MB
  • 17 pages

Document Identifiers

Author Details

Gaëtan Douéneau-Tabot
  • IRIF, Université de Paris, France

Funding

  • Douéneau-Tabot, Gaëtan: Funded by the French Ministry of Defence (DGA IP).

Acknowledgements

The author is grateful to Olivier Carton for discussing about this work. He also thanks the reviewers for their helpful comments and remarks.

Cite As Get BibTex

Gaëtan Douéneau-Tabot. Pebble Transducers with Unary Output. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.40

Abstract

Bojańczyk recently initiated an intensive study of deterministic pebble transducers, which are two-way automata that can drop marks (named "pebbles") on their input word, and produce an output word. They describe functions from words to words. Two natural restrictions of this definition have been investigated: marble transducers by Douéneau-Tabot et al., and comparison-free pebble transducers (that we rename here "blind transducers") by Nguyên et al.
Here, we study the decidability of membership problems between the classes of functions computed by pebble, marble and blind transducers that produce a unary output. First, we show that pebble and marble transducers have the same expressive power when the outputs are unary (which is false over non-unary outputs). Then, we characterize 1-pebble transducers with unary output that describe a function computable by a blind transducer, and show that the membership problem is decidable. These results can be interpreted in terms of automated simplification of programs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Transducers
Keywords
  • polyregular functions
  • pebble transducers
  • marble transducers
  • streaming string transducers
  • factorization forests

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Mikołaj Bojańczyk. Factorization forests. In International Conference on Developments in Language Theory, pages 1-17. Springer, 2009. Google Scholar
  2. Mikołaj Bojańczyk. Transducers with origin information. In International Colloquium on Automata, Languages, and Programming, pages 26-37. Springer, 2014. Google Scholar
  3. Mikolaj Bojańczyk. Polyregular functions. arXiv preprint, 2018. URL: http://arxiv.org/abs/1810.08760.
  4. Mikolaj Bojańczyk, Sandra Kiefer, and Nathan Lhote. String-to-string interpretations with polynomial-size output. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, pages 106:1-106:14, 2019. Google Scholar
  5. Michal P Chytil and Vojtěch Jákl. Serial composition of 2-way finite-state transducers and simple programs on strings. In 4th International Colloquium on Automata, Languages, and Programming, ICALP 1977, pages 135-147. Springer, 1977. Google Scholar
  6. Gaëtan Douéneau-Tabot, Emmanuel Filiot, and Paul Gastin. Register transducers are marble transducers. In 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, 2020. Google Scholar
  7. Joost Engelfriet and Hendrik Jan Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Transactions on Computational Logic (TOCL), 2(2):216-254, 2001. Google Scholar
  8. Emmanuel Filiot and Pierre-Alain Reynier. Copyful streaming string transducers. In International Workshop on Reachability Problems, pages 75-86. Springer, 2017. Google Scholar
  9. Eitan M Gurari. The equivalence problem for deterministic two-way sequential transducers is decidable. SIAM Journal on Computing, 11(3):448-452, 1982. Google Scholar
  10. Nathan Lhote. Pebble minimization of polyregular functions. In 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS. IEEE, 2020. Google Scholar
  11. Lê Thành Dung Nguyên, Camille Noûs, and Pierre Pradic. Comparison-free polyregular functions. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, 2021. Google Scholar
  12. John C Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3(2):198-200, 1959. Google Scholar
  13. Imre Simon. Factorization forests of finite height. Theoretical Computer Science, 72(1):65-94, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact