Untwisting two-way transducers in elementary time
Article No.: 78, Pages 1 - 12
Abstract
Functional transductions realized by two-way transducers (equivalently, by streaming transducers and by MSO transductions) are the natural and standard notion of "regular" mappings from words to words. It was shown recently (LICS'13) that it is decidable if such a transduction can be implemented by some one-way transducer, but the given algorithm has non-elementary complexity. We provide an algorithm of different flavor solving the above question, that has double exponential space complexity. We further apply our technique to decide whether the transduction realized by a two-way transducer can be implemented by a sweeping transducer, with either known or unknown number of passes.
References
[1]
A. Aho, J. Hopcroft, and J. Ullman. A general theory of translation. Math. Syst. Theory, 3(3):193--221, 1969.
[2]
R. Alur and P. Cerný. Expressiveness of streaming string transducers. In FSTTCS, volume 8 of LIPIcs, pages 1--12. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2010.
[3]
F. Baschenis, O. Gauwin, A. Muscholl, and G. Puppis. One-way definability of sweeping transducer. In FSTTCS, volume 45 of LIPIcs, pages 178--191. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.
[4]
F. Baschenis, O. Gauwin, A. Muscholl, and G. Puppis. Minimizing resources of sweeping and streaming string transducers. In ICALP, volume 55 of LIPIcs, pages 114:1--114:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Full version available at https://hal.archives-ouvertes.fr/hal-01274992.
[5]
F. Baschenis, O. Gauwin, A. Muscholl, and G. Puppis. Untwisting two-way transducers in elementary time, 2017. Full version available at https://arxiv.org/abs/1701.02502.
[6]
J. Birget. Two-way automaton computations. RAIRO - Theoretical Informatics and Applications, 24(1):47--66, 1990.
[7]
O. Carton and L. Dartois. Aperiodic two-way transducers and FO-transductions. In CSL, volume 41 of LIPIcs, pages 160--174. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
[8]
C. Choffrut and B. Guillon. An algebraic characterization of unary two-way transducers. In MFCS, volume 8634 of LNCS, pages 196--207. Springer, 2014.
[9]
T. Colcombet. Factorisation forests for infinite words. In FCT, volume 4639 of LNCS, pages 226--237. Springer, 2007.
[10]
L. Daviaud, P. Reynier, and J. Talbot. A generalised twinning property for minimisation of cost register automata. In LICS, pages 857--866. ACM, 2016.
[11]
S. Eilenberg. Automata, Langages and Machines. Academic Press, 1976.
[12]
J. Engelfriet and H. J. Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Logic, 2(2):216--254, 2001.
[13]
E. Filiot, O. Gauwin, and N. Lhote. First-order definability of rational transductions: An algebraic approach. In LICS, pages 387--396. ACM, 2016.
[14]
E. Filiot, O. Gauwin, P. Reynier, and F. Servais. From two-way to one-way finite state transducers. In LICS, pages 468--477. IEEE Computer Society, 2013.
[15]
E. Filiot, S. N. Krishna, and A. Trivedi. First-order definable string transformations. In FSTTCS, volume 29 of LIPIcs, pages 147--159. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014.
[16]
N. Fine and H. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16:109--114, 1965.
[17]
B. Guillon. Sweeping weakens two-way transducers even with a unary output alphabet. In NCMA, volume 318 of [email protected], pages 91--108. Österreichische Computer Gesellschaft, 2015.
[18]
J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
[19]
J. Kortelainen. On the system of word equations x<sub>0</sub>u<sup>i</sup><sub>1</sub>x<sub>1</sub>u<sup>i</sup><sub>2</sub>x<sub>2</sub> . . . u<sup>i</sup><sub>m</sub>x<sub>m</sub> = y<sub>0</sub>v<sup>i</sup><sub>1</sub> y<sub>1</sub>v<sup>i</sup><sub>2</sub> y<sub>2</sub> . . . v<sup>i</sup><sub>m</sub> y<sub>m</sub> (i = 0, 1, 2, ...) in a free monoid. Journal of Automata, Languages and Combinatorics, 3(1):43--57, 1998.
[20]
M. Rabin and D. Scott. Finite automata and their decision problems. IBM J. Res. Dev., 3(2):114--125, 1959.
[21]
A. Saarela. Systems of word equations, polynomials and linear algebra: a new approach. European Journal of Combinatorics, 47(5):1--14, 2015.
[22]
M. Schützenberger. A remark on finite transducers. Information and Control, 4(2--3):185--196, 1961.
[23]
J. Shepherdson. The reduction of two-way automata to one-way automata. IBM J. Res. Dev., 3(2):198--200, 1959.
[24]
I. Simon. Factorization forests of finite height. Theoretical Computer Science, 72(1):65--94, 1990.
Recommendations
From Two-Way to One-Way Finite State Transducers
LICS '13: Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer ScienceAny two-way finite state automaton is equivalent to some one-way finite state automaton. This well-known result, shown by Rabin and Scott and independently by Shepherd son, states that two-way finite state automata (even non-deterministic) characterize ...
Two-Way Visibly Pushdown Automata and Transducers
LICS '16: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer ScienceAutomata-logic connections are pillars of the theory of regular languages. Such connections are harder to obtain for transducers, but important results have been obtained recently for word-to-word transformations, showing that the three following models ...
MSO definable string transductions and two-way finite-state transducers
We extend a classic result of Büchi, Elgot, and Trakhtenbrot: MSO definable string transductions i.e., string-to-string functions that are definable by an interpretation using monadic second-order (MSO) logic, are exactly those realized by deterministic ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
Publisher
IEEE Press
Publication History
Published: 20 June 2017
Check for updates
Qualifiers
- Research-article
Conference
LICS '17
Sponsor:
LICS '17: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science
June 20 - 23, 2017
Reykjavík, Iceland
Acceptance Rates
Overall Acceptance Rate 215 of 622 submissions, 35%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 17Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)1
Reflects downloads up to 25 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in