论文标题
关于协调表选择性替代系统的复杂性
On the Complexity of Coordinated Table Selective Substitution Systems
论文作者
论文摘要
我们研究图灵机（TMS）和交替的图灵机（ATM）使用的计算资源，以接受由两个组件的协调表选择性替代系统生成的语言。我们证明，通过实时（RL; 0s）系统生成的语言类别，这是一种生成无lambda标记的标记为标有petri网络语言的替代设备，可以被O（log n）空间和O（nlog n）时间的非确定tms接受。因此，NSPACE（log n）中包括这种适当的培养皿网语言（也称为L语言）。由（RL; rb） - 系统产生的语言类别的语言类别仅由一个符号组成，而RB-Grammar的非末端字母组成，RB-Grammar的非末端字母由两个符号组成，可以由O（log n）时间和空间中的ATM接受。因此，u_e* - 均匀的NC1中包含了一个只有一个控制状态的单方面计算机生成的单方面语言的适当子类，因此在太空中（log n）。
We investigate computational resources used by Turing machines (TMs) and alternating Turing machines (ATMs) to accept languages generated by coordinated table selective substitution systems with two components. We prove that the class of languages generated by real-time (RL; 0S)-systems, an alternative device to generate lambda-free labeled marked Petri nets languages, can be accepted by nondeterministic TMs in O(log n) space and O(nlog n) time. Consequently, this proper sub-class of Petri nets languages (known also as L-languages) is included in NSPACE(log n). The class of languages generated by (RL; RB)-systems for which the nonterminal alphabet of the RL-grammar is composed of only one symbol and the nonterminal alphabet of the RB-grammar is composed of two symbols, can be accepted by ATMs in O(log n) time and space. Consequently, this proper subclass of one-counter languages generated by one-counter machines with only one control state is included in U_E*-uniform NC1, hence in SPACE(log n).
