论文标题
配备辅助数据结构和常规可相关性问题的自动机
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems
论文作者
论文摘要
我们考虑一般计算模型：单向和双向有限自动机，以及对数空间图灵机，所有这些都配备了辅助数据结构（ADS）。广告的定义基于与广告的工作协议的语言。我们描述了基于自动机的模型与``气球自动机''的连接，这是霍普罗夫特和乌尔曼在1967年提出的广告的另一种一般形式化。 该定义确定了使用广告的单向自动机的非空置问题，通过配备了相同广告的非确定日志空间图灵机识别的语言，以及适用于ADS协议语言的常规可实现问题（NRR）。 NRR问题是验证输入上的常规语言是否与协议语言具有非空交集。这些问题（和语言）的计算复杂性与日志空间降低相同。
We consider general computational models: one-way and two-way finite automata, and logarithmic space Turing machines, all equipped with an auxiliary data structure (ADS). The definition of an ADS is based on the language of protocols of work with the ADS. We describe the connection of automata-based models with ``Balloon automata'' that are another general formalization of automata equipped with an ADS presented by Hopcroft and Ullman in 1967. This definition establishes the connection between the non-emptiness problem for one-way automata with ADS, languages recognizable by nondeterministic log-space Turing machines equipped with the same ADS, and a regular realizability problem (NRR) for the language of ADS' protocols. The NRR problem is to verify whether the regular language on the input has a non-empty intersection with the language of protocols. The computational complexity of these problems (and languages) is the same up to log-space reductions.
