LIPIcs.ICALP.2018.142.pdf
- Filesize: 0.52 MB
- 13 pages
Document
Uniformization Problems for Synchronizations of Automatic Relations on Words
Author
-
Part of:
Volume:
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-07-04
Cite AsGet 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
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)
0PDF Downloads
References
- Jean Berstel. Transductions and context-free languages http://www-igm.univ-mlv.fr/~berstel/, 2009.
- 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.
-
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.
-
Alonzo Church. Logic, arithmetic and automata. In Proceedings of the International Congress of Mathematicians, pages 23-35, 1962.
-
R. Diestel. Graph Theory, 2nd Edition, volume 173 of Graduate Texts in Mathematics. Springer, 2000.
-
Diego Figueira and Leonid Libkin. Synchronizing relations on words. Theory Comput. Syst., 57(2):287-318, 2015.
- 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.
- 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.
- 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.
-
Frederick A. Hosch and Lawrence H. Landweber. Finite delay solutions for sequential conditions. In ICALP, pages 45-60, 1972.
- 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.
-
M. Nivat. Transductions des langages de Chomsky. Ann. de l'Inst. Fourier, 18:339-456, 1968. in french.
-
Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009.
-
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.