论文标题
非确定迭代均匀有限状态传感器的计算和描述能力
Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers
论文作者
论文摘要
迭代的均匀有限状态换能器（IUFST）运行相同的长度传递转导，首先是在输入字符串上进行扫描，然后在先前扫描的输出上迭代扫描。 IUFST通过在扫描结束时以接收状态停止来接受输入字符串。我们考虑此设备的确定性（IUFST）和非确定性（Niufst）版本。我们表明，不断的扫描有限的IUFST和Niufsts接受全部和唯一的普通语言。我们研究了消除非确定性的状态复杂性以及对恒定扫描有限的Niufst的扫描，即有限状态自动机的经典模型的恒定扫描有限的IUFST和NIUFST的描述能力，以及几种可确定性问题的计算复杂性。然后，我们专注于非恒定扫描有限的设备，证明存在适当的无限非规范语言层次结构，具体取决于确定性和非确定性情况下的扫描复杂性。尽管Niufstss是“单向”设备，但我们表明它们表征了上下文敏感语言类别，即复杂性类别DSPACE（LIN）。最后，我们表明，非确定设备比其确定性变体更强大，对于至少对数的跨性别扫描数量而言。
An iterated uniform finite-state transducer (IUFST) runs the same length-preserving transduction, starting with a sweep on the input string and then iteratively sweeping on the output of the previous sweep. The IUFST accepts the input string by halting in an accepting state at the end of a sweep. We consider both the deterministic (IUFST) and nondeterministic (NIUFST) version of this device. We show that constant sweep bounded IUFSTs and NIUFSTs accept all and only regular languages. We study the state complexity of removing nondeterminism as well as sweeps on constant sweep bounded NIUFSTs, the descriptional power of constant sweep bounded IUFSTs and NIUFSTs with respect to classical models of finite-state automata, and the computational complexity of several decidability questions. Then, we focus on non-constant sweep bounded devices, proving the existence of a proper infinite nonregular language hierarchy depending on the sweep complexity both in the deterministic and nondeterministic case. Though NIUFSTss are "one-way" devices we show that they characterize the class of context-sensitive languages, that is, the complexity class DSpace(lin). Finally, we show that the nondeterministic devices are more powerful than their deterministic variant for a sublinear number of sweeps that is at least logarithmic.
