2026-07-23T17:37:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10703 2024-03-06T10:46:30Z ddc:004 open_access

From Nondeterministic to Multi-Head Deterministic Finite-State Transducers (Track B: Automata, Logic, Semantics, and Theory of Programming) Raszyk, Martin Basin, David Traytel, Dmitriy Formal languages Nondeterminism Multi-head automata Finite transducers 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Raszyk and David Basin and Dmitriy Traytel 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.127 urn:nbn:de:0030-drops-107037 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.127 eng https://creativecommons.org/licenses/by/3.0/legalcode