Document Open Access Logo

Uniformization Problems for Synchronizations of Automatic Relations on Words

Author Sarah Winter

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.142.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Sarah Winter
  • RWTH Aachen University, Germany

Funding

Supported by the project (LO 1174/3-1) of the German Research Foundation (DFG).

Cite As Get BibTex

Sarah Winter. Uniformization Problems for Synchronizations of Automatic Relations on Words. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 142:1-142:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.142

Abstract

A uniformization of a binary relation is a function that is contained in the relation and has the same domain as the relation. The synthesis problem asks for effective uniformization for classes of relations and functions that can be implemented in a specific way.
We consider the synthesis problem for automatic relations over finite words (also called regular or synchronized rational relations) by functions implemented by specific classes of sequential transducers.
It is known that the problem "Given an automatic relation, does it have a uniformization by a subsequential transducer?" is decidable in the two variants where the uniformization can either be implemented by an arbitrary subsequential transducer or it has to be implemented by a synchronous transducer. We introduce a new variant of this problem in which the allowed input/output behavior of the subsequential transducer is specified by a set of synchronizations and prove decidability for a specific class of synchronizations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • automatic relation
  • uniformization
  • synchronization
  • transducer

Metrics

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

Related Versions

References

  1. Jean Berstel. Transductions and context-free languages http://www-igm.univ-mlv.fr/~berstel/, 2009.
  2. J. Richard Büchi and Lawrence H. Landweber. Solving sequential conditions by finite-state strategies. Transactions of the American Mathematical Society, 138:295-311, 1969. URL: http://dx.doi.org/10.1090/S0002-9947-1969-0280205-0.
  3. 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
  4. Alonzo Church. Logic, arithmetic and automata. In Proceedings of the International Congress of Mathematicians, pages 23-35, 1962. Google Scholar
  5. R. Diestel. Graph Theory, 2nd Edition, volume 173 of Graduate Texts in Mathematics. Springer, 2000. Google Scholar
  6. Diego Figueira and Leonid Libkin. Synchronizing relations on words. Theory Comput. Syst., 57(2):287-318, 2015. Google Scholar
  7. Emmanuel Filiot, Ismaël Jecker, Christof Löding, and Sarah Winter. On equivalence and uniformisation problems for finite transducers. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 125:1-125:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.125.
  8. Christiane Frougny and Jacques Sakarovitch. Synchronized rational relations of finite and infinite words. Theor. Comput. Sci., 108(1):45-82, 1993. URL: http://dx.doi.org/10.1016/0304-3975(93)90230-Q.
  9. Michael Holtmann, Łukasz Kaiser, and Wolfgang Thomas. Degrees of lookahead in regular infinite games. In Foundations of Software Science and Computational Structures, volume 6014 of Lecture Notes in Computer Science, pages 252-266. Springer, 2010. URL: http://dx.doi.org//10.1007/978-3-642-12032-9_18.
  10. Frederick A. Hosch and Lawrence H. Landweber. Finite delay solutions for sequential conditions. In ICALP, pages 45-60, 1972. Google Scholar
  11. J. Howard Johnson. Uniformizing rational relations for natural language applications using weighted determinization. In Proceedings of the 15th International Conference on Implementation and Application of Automata, CIAA'10, pages 173-180, Berlin, Heidelberg, 2011. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=1964285.1964304.
  12. M. Nivat. Transductions des langages de Chomsky. Ann. de l'Inst. Fourier, 18:339-456, 1968. in french. Google Scholar
  13. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Google Scholar
  14. 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
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