论文标题
从有限评估的非确定性传感器到确定性的两-tape automata
From Finite-Valued Nondeterministic Transducers to Deterministic Two-Tape Automata
论文作者
论文摘要
问题是否等于NP是否围绕着Turing Machines的主动生产和仅验证之间的差异。在本文中，我们研究了有限传感器和自动机的类似问题。每个非确定有限传感器都定义了一个二进制关系，将每个输入单词与传感器可以在给定输入上成功产生的所有输出单词相关联。有限值的传感器是该关系与每个输入单词相关联的输出单词数量的有限上限。我们表征有限的价值，功能性和明确的非确定性传感器，它们的关系可以通过确定性的两-tape自动机进行验证，显示如何存在，如果存在一个自动机，并证明了标准的不确定性。
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.
