From Nondeterministic to Multi-Head Deterministic Finite-State Transducers (Track B: Automata, Logic, Semantics, and Theory of Programming)
Every nondeterministic finite-state automaton is equivalent to a deterministic finite-state automaton. This result does not extend to finite-state transducers - finite-state automata equipped with a one-way output tape. There is a strict hierarchy of functions accepted by one-way deterministic finite-state transducers (1DFTs), one-way nondeterministic finite-state transducers (1NFTs), and two-way nondeterministic finite-state transducers (2NFTs), whereas the two-way deterministic finite-state transducers (2DFTs) accept the same family of functions as their nondeterministic counterparts (2NFTs).
We define multi-head one-way deterministic finite-state transducers (mh-1DFTs) as a natural extension of 1DFTs. These transducers have multiple one-way reading heads that move asynchronously over the input word. Our main result is that mh-1DFTs can deterministically express any function defined by a one-way nondeterministic finite-state transducer. Of independent interest, we formulate the all-suffix regular matching problem, which is the problem of deciding for each suffix of an input word whether it belongs to a regular language. As part of our proof, we show that an mh-1DFT can solve all-suffix regular matching, which has applications, e.g., in runtime verification.
Formal languages
Nondeterminism
Multi-head automata
Finite transducers
Theory of computation~Transducers
127:1-127:14
Track B: Automata, Logic, Semantics, and Theory of Programming
This research is supported by the Swiss National Science Foundation grant "Big Data Monitoring" (167162).
Martin
Raszyk
Martin Raszyk
Department of Computer Science, ETH Zürich, Universitätstrasse 6, 8092, Switzerland
David
Basin
David Basin
Department of Computer Science, ETH Zürich, Universitätstrasse 6, 8092, Switzerland
Dmitriy
Traytel
Dmitriy Traytel
Department of Computer Science, ETH Zürich, Universitätstrasse 6, 8092, Switzerland
10.4230/LIPIcs.ICALP.2019.127
Eugene Asarin, Paul Caspi, and Oded Maler. Timed regular expressions. J. ACM, 49(2):172-206, 2002.
David Basin, Bhargav Bhatt, Srđan Krstić, and Dmitriy Traytel. Almost Event-Rate Independent Monitoring. Form. Meth. Sys. Des., 2019 (published online February 2019).
Patricia Bouyer, Fabrice Chevalier, and Nicolas Markey. On the expressiveness of TPTL and MTL. Inf. Comput., 208(2):97-116, 2010.
Joost Engelfriet and Hendrik Jan Hoogeboom. Two-Way Finite State Transducers and Monadic Second-Order Logic. In Jirí Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, ICALP 1999, volume 1644 of LNCS, pages 311-320. Springer, 1999.
Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, and Frédéric Servais. From Two-Way to One-Way Finite State Transducers. In LICS 2013, pages 468-477. IEEE Computer Society, 2013.
Markus Holzer, Martin Kutrib, and Andreas Malcher. Complexity of multi-head finite automata: Origins and directions. Theor. Comput. Sci., 412(1-2):83-96, 2011.
Michael O. Rabin and Dana S. Scott. Finite Automata and Their Decision Problems. IBM Journal of Research and Development, 3(2):114-125, 1959.
Martin Raszyk, David Basin, Srđan Krstić, and Dmitriy Traytel. Multi-head monitoring of metric temporal logic. In Yu-Fang Chen, Chih-Hong Cheng, and Javier Esparza, editors, ATVA 2019, LNCS. Springer, 2019. To appear. URL: http://people.inf.ethz.ch/trayteld/papers/atva19-hydra/hydra.pdf.
http://people.inf.ethz.ch/trayteld/papers/atva19-hydra/hydra.pdf
Ivan Hal Sudborough. On Tape-Bounded Complexity Classes and Multihead Finite Automata. J. Comput. Syst. Sci., 10(1):62-76, 1975.
Andrew Chi-Chih Yao and Ronald L. Rivest. k+1 Heads Are Better than k. J. ACM, 25(2):337-340, 1978.
Martin Raszyk, David Basin, and Dmitriy Traytel
Creative Commons Attribution 3.0 Unported license
https://creativecommons.org/licenses/by/3.0/legalcode