Document Open Access Logo

On Equivalence and Uniformisation Problems for Finite Transducers

Authors Emmanuel Filiot, Ismaël Jecker, Christof Löding, Sarah Winter

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.125.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Emmanuel Filiot
Ismaël Jecker
Christof Löding
Sarah Winter

Cite As Get BibTex

Emmanuel Filiot, Ismaël Jecker, Christof Löding, and Sarah Winter. On Equivalence and Uniformisation Problems for Finite Transducers. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 125:1-125:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.125

Abstract

Transductions are binary relations of finite words. For rational transductions, i.e., transductions defined by finite transducers, the inclusion, equivalence and sequential uniformisation problems are known to be undecidable. In this paper, we investigate stronger variants of inclusion, equivalence and sequential uniformisation, based on a general notion of transducer resynchronisation, and show their decidability. We also investigate the classes of finite-valued rational transductions and deterministic rational transductions, which are known to have a decidable equivalence problem. We show that sequential uniformisation is also decidable for them.

Subject Classification

Keywords
  • Transducers
  • Equivalence
  • Uniformisation

Metrics

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

References

  1. Marie-Pierre Béal, Olivier Carton, Christophe Prieur, and Jacques Sakarovitch. Squaring transducers: an efficient procedure for deciding functionality and sequentiality. Theoretical Computer Science, 292(1):45-63, 2003. Google Scholar
  2. Jean Berstel. Transductions and Context-free Languages. Teubner-Verlag, December 2009. URL: http://www-igm.univ-mlv.fr/~berstel/.
  3. Malcolm Bird. The equivalence problem for deterministic two-tape automata. J. Comput. Syst. Sci., 7(2):218-236, 1973. URL: http://dx.doi.org/10.1016/S0022-0000(73)80045-5.
  4. Roderick Bloem, Barbara Jobstmann, Nir Piterman, Amir Pnueli, and Yaniv Sa'ar. Synthesis of reactive(1) designs. J. Comput. Syst. Sci., 78(3):911-938, 2012. URL: http://dx.doi.org/10.1016/j.jcss.2011.08.007.
  5. Mikolaj Bojanczyk. Transducers with origin information. ICALP, abs/1309.6124, 2013. Google Scholar
  6. Arnaud Carayol and Christof Löding. Uniformization in Automata Theory. In Proceedings of the 14th Congress of Logic, Methodology and Philosophy of Science Nancy, July 19-26, 2011, pages 153-178. London: College Publications, 2014. Google Scholar
  7. Olivier Carton, Christian Choffrut, and Serge Grigorieff. Decision problems among the main subfamilies of rational relations. ITA, 40(2):255-275, 2006. URL: http://dx.doi.org/10.1051/ita:2006005.
  8. Rodrigo de Souza. On the decidability of the equivalence for k-valued transducers. In Developments in Language Theory, 12th International Conference, DLT 2008, Kyoto, Japan, September 16-19, 2008. Proceedings, pages 252-263, 2008. Google Scholar
  9. Rodrigo de Souza and Nami Kobayashi. A combinatorial study of k-valued rational relations. Journal of Automata, Languages and Combinatorics, 13(3/4):207-231, 2008. Google Scholar
  10. Samuel Eilenberg. Automata, Languages, and Machines. Academic Press, 1974. Google Scholar
  11. Diego Figueira and Leonid Libkin. Synchronizing relations on words. Theory Comput. Syst., 57(2):287-318, 2015. Google Scholar
  12. Emmanuel Filiot, Ismaël Jecker, Christof Löding, and Sarah Winter. On equivalence and uniformisation problems for finite transducers. CoRR, abs/1602.08565, 2016. URL: http://arxiv.org/abs/1602.08565.
  13. Emmanuel Filiot, Naiyong Jin, and Jean-François Raskin. Antichains and compositional algorithms for LTL synthesis. Formal Methods in System Design, 39(3):261-296, 2011. Google Scholar
  14. Patrick C. Fischer and Arnold L. Rosenberg. Multitape one-way nonwriting automata. Journal of Computer and System Sciences, 2(1):88-101, 1968. URL: http://dx.doi.org/10.1016/S0022-0000(68)80006-6.
  15. Emily P. Friedman and Sheila A. Greibach. A polynomial time algorithm for deciding the equivalence problem for 2-tape deterministic finite state acceptors. SIAM J. Comput., 11(1):166-183, 1982. URL: http://dx.doi.org/10.1137/0211013.
  16. Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors. Automata, Logics, and Infinite Games, volume 2500 of LNCS. Springer, 2002. Google Scholar
  17. Timothy V. Griffiths. The unsolvability of the equivalence problem for lambda-free nondeterministic generalized machines. Journal of the ACM, 15(3):409-413, 1968. Google Scholar
  18. Eitan M. Gurari and Oscar H. Ibarra. A note on finite-valued and finitely ambiguous transducers. Theory of Computing Systems, 16(1):61-66, 1983. Google Scholar
  19. Oscar H. Ibarra. The unsolvability of the equivalence problem for ε-free NGSM’s with unary input (output) alphabet and applications. SIAM Journal on Computing, 7(4):524-532, November 1978. Google Scholar
  20. Karel Culik II and Juhani Karhumäki. The equivalence of finite valued transducers (on HDT0L languages) is decidable. TCS: Theoretical Computer Science, 47, 1986. Google Scholar
  21. J. H. Johnson. Do rational equivalence relations have regular cross-sections? In Lecture Notes in Computer Science, volume 194 of LNCS, pages 300-309. Springer, 1985. Google Scholar
  22. Julius Richard Büchi and Lawrence H. Landweber. Solving sequential conditions finite-state strategies. Trans. Ameri. Math. Soc., 138:295-311, 1969. Google Scholar
  23. Kojiro Kobayashi. Classification of formal languages by functional binary transductions. Information and Control, 15(1):95-109, July 1969. Google Scholar
  24. Orna Kupferman, Nir Piterman, and Moshe Y. Vardi. Safraless compositional synthesis. In Computer Aided Verification, 18th International Conference, CAV 2006, volume 4144 of Lecture Notes in Computer Science, pages 31-44. Springer, 2006. Google Scholar
  25. Sylvain Lombardy and Jacques Sakarovitch. Sequential? Theor. Comput. Sci., 356(1-2):224-244, 2006. Google Scholar
  26. Maurice Nivat. Transductions des langages de Chomsky. Ann. de l'Inst. Fourier, 18:339-456, 1968. in french. Google Scholar
  27. Maryse Pelletier and Jacques Sakarovitch. On the representation of finite deterministic 2-tape automata. TCS: Theoretical Computer Science, 225, 1999. Google Scholar
  28. Amir Pnueli and Roni Rosner. On the synthesis of a reactive module. In ACM Symposium on Principles of Programming Languages (POPL). ACM, 1989. Google Scholar
  29. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Google Scholar
  30. Jacques Sakarovitch and Rodrigo de Souza. Lexicographic decomposition of k-valued transducers. Theory of Computing Systems, 47(3):758-785, 2010. Google Scholar
  31. Wolfgang Thomas. Church’s problem and a tour through automata theory. In Pillars of Computer Science, Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, volume 4800 of Lecture Notes in Computer Science, pages 635-655. Springer, 2008. Google Scholar
  32. Andreas Weber. A decomposition theorem for finite-valued tranducers and an application to the equivalence problem. In 13th International Symposium on Mathematical Foundations of Computer Science, MFCS 1988, pages 552-562, 1988. Google Scholar
  33. Andreas Weber. On the valuedness of finite transducers. Acta Informatica, 27(8):749-780, 1989. Google Scholar
  34. Andreas Weber and Reinhard Klemm. Economy of description for single-valued transducers. Information and Computation, 118(2):327-340, 1995. 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