Document Open Access Logo

On Synthesis of Resynchronizers for Transducers

Authors Sougata Bose, Shankara Narayanan Krishna, Anca Muscholl, Vincent Penelle, Gabriele Puppis

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.69.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Sougata Bose
  • LaBRI, University of Bordeaux, France
Shankara Narayanan Krishna
  • Department of Computer Science & Engineering IIT Bombay, India
Anca Muscholl
  • LaBRI, University of Bordeaux, France
Vincent Penelle
  • LaBRI, University of Bordeaux, France
Gabriele Puppis
  • CNRS, LaBRI, University of Bordeaux, France

Funding

DeLTA project (ANR-16-CE40-0007)

Cite AsGet BibTex

Sougata Bose, Shankara Narayanan Krishna, Anca Muscholl, Vincent Penelle, and Gabriele Puppis. On Synthesis of Resynchronizers for Transducers. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.69

Abstract

We study two formalisms that allow to compare transducers over words under origin semantics: rational and regular resynchronizers, and show that the former are captured by the latter. We then consider some instances of the following synthesis problem: given transducers T_1,T_2, construct a rational (resp. regular) resynchronizer R, if it exists, such that T_1 is contained in R(T_2) under the origin semantics. We show that synthesis of rational resynchronizers is decidable for functional, and even finite-valued, one-way transducers, and undecidable for relational one-way transducers. In the two-way setting, synthesis of regular resynchronizers is shown to be decidable for unambiguous two-way transducers. For larger classes of two-way transducers, the decidability status is open.

Subject Classification

ACM Subject Classification
  • Theory of computation → Transducers
Keywords
  • String transducers
  • resynchronizers
  • synthesis

Metrics

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

Related Versions

References

  1. Rajeev Alur and Pavel Cerný. Expressiveness of streaming string transducer. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'10), volume 8 of LIPIcs, pages 1-12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. Google Scholar
  2. Marie-Pierre Béal, Olivier Carton, Christophe Prieur, and Jacques Sakarovitch. Squaring transducers: an efficient procedure for deciding functionality and sequentiality. Theor. Comput. Sci., 292:45-63, 2003. Google Scholar
  3. Meera Blattner and Tom Head. Single-valued a-transducers. J. Comput. and System Sci., 15:310-327, 1977. Google Scholar
  4. Mikolaj Bojańczyk. Transducers with origin information. In International Colloquium on Automata, Languages and Programming (ICALP'14), number 8572 in LNCS, pages 26-37. Springer, 2014. Google Scholar
  5. Mikolaj Bojańczyk, Laure Daviaud, Bruno Guillon, and Vincent Penelle. Which Classes of Origin Graphs Are Generated by Transducers? In International Colloquium on Automata, Languages and Programming (ICALP'17), volume 80 of LIPIcs, pages 114:1-114:13, 2017. Google Scholar
  6. Sougata Bose, Anca Muscholl, Vincent Penelle, and Gabriele Puppis. Origin-Equivalence of Two-Way Word Transducers Is in PSPACE. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'18), volume 122 of LIPIcs, pages 1-18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  7. Michaël Cadilhac, Alain Finkel, and Pierre McKenzie. Unambiguous constrained Automata. Int. J. Found. Comput. Sci., 24(7):1099-1116, 2013. URL: https://doi.org/10.1142/S0129054113400339.
  8. Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012. Google Scholar
  9. Calvin C. Elgot and Jorge E. Mezei. On Relations Defined by Generalized Finite Automata. IBM Journal of Research and Development, 9(1):47-68, 1965. URL: https://doi.org/10.1147/rd.91.0047.
  10. Emmanuel Filiot, Ismaël Jecker, Christof Löding, and Sarah Winter. On Equivalence and Uniformisation Problems for Finite Transducers. In International Colloquium on Automata, Languages and Programming (ICALP'16), volume 55 of LIPIcs, pages 125:1-125:14, 2016. Google Scholar
  11. Patrick C. Fischer and Arnold L. Rosenberg. Multi-tape one-way nonwriting automata. J. Comput. and System Sci., 2:88-101, 1968. Google Scholar
  12. T. V. Griffiths. The unsolvability of the equivalence problem for lambda-free nondeterministic generalized machines. J. ACM, 15(3):409-413, 1968. Google Scholar
  13. Piotr Hofman. Personal communication. Google Scholar
  14. Oscar H. Ibarra. The unsolvability of the equivalence problem for e-free NGSM’s with unary input (output) alphabet and applications. SIAM J. of Comput., 7(4):524-532, 1978. Google Scholar
  15. Andreas Weber. Decomposing a k-Valued Transducer into k Unambiguous Ones. ITA, 30(5):379-413, 1996. 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 Imprint Privacy Contact