From Finite-Valued Nondeterministic Transducers to Deterministic Two-Tape Automata
Abstract
The question whether P equals NP revolves around the discrepancy between active production and mere verification by Turing machines. In this paper, we examine the analogous problem for finite transducers and automata. Every nondeterministic finite transducer defines a binary relation associating each input word with all output words that the transducer can successfully produce on the given input. Finite-valued transducers are those for which there is a finite upper bound on the number of output words that the relation associates with every input word. We characterize finite-valued, functional, and unambiguous nondeterministic transducers whose relations can be verified by a deterministic two-tape automaton, show how to construct such an automaton if one exists, and prove the undecidability of the criterion.
Authors 3
-
Affiliation as printed
Department of Computer Science RWTH Aachen , Germany
-
Affiliation as printed
Department of Computer Science ETH Zürich , Switzerland
-
Affiliation as printed
Department of Computer Science ETH Zürich , Switzerland
Cited by 0 stored of 0
No patents citing this paper on Lens.org (checked 2026-10-06).