【24h】

On the Complexity of Szilard Languages of Matrix Grammars

机译:矩阵文法的Szilard语言的复杂性

获取原文
获取原文并翻译 | 示例

摘要

We investigate computational resources used by alternating Turing machines (ATMs) to accept Szilard languages (SZLs) of context-free matrix grammars (MGs). The main goal is to relate these languages to parallel complexity classes such as NC1 and NC2. We prove that unrestricted and leftmost-1 SZLs of context-free MGs, without appearance checking, can be accepted by ATMs in logarithmic time and space. Hence, these classes of languages belong to NC1 (under ALOGTIME reduction). Unrestricted SZLs of context-free MGs with appearance checking can be accepted by ATMs in logarithmic space and square logarithmic time. Consequently, this class is contained in NC2. We conclude with some results on SZLs of MGs with phrase-structure rules.
机译:我们调查交替图灵机(ATM)用来接受上下文无关矩阵语法(MG)的Szilard语言(SZL)的计算资源。主要目标是将这些语言与并行复杂度类(例如NC1和NC2)相关联。我们证明了无条件的MG的不受限制且最左边的1个SZL,无需进行外观检查,就可以在对数时空上被ATM接受。因此,这些类的语言属于NC1(在ALOGTIME减少之下)。带有外观检查的上下文无关MG的不受限制的SZL可以被ATM在对数空间和平方对数时间内接受。因此,此类包含在NC2中。我们以具有短语结构规则的MG的SZL得出一些结论。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号