COMPUTATIONAL COMPLEXITY OF LINEAR PCGSs

Liming CAI

首页> 外文期刊>Computers and Artificial Intelligence >COMPUTATIONAL COMPLEXITY OF LINEAR PCGSs

【24h】

COMPUTATIONAL COMPLEXITY OF LINEAR PCGSs

机译：线性PCGS的计算复杂度

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

The computational complexity is investigated for Parallel Communicating Grammar Systems (PCGSs) whose components are linear grammars. It is shown that languages generated by linear PCGSs can be recognized by O(log n) space-bounded Turing machines. Based on the complexity characterization, the generative power of linear PCGSs is analyzed with respect to context-free and context-sensitive grammars.

机译：研究了并行通信语法系统（PCGS）的计算复杂性，该系统的组成部分是线性语法。结果表明，线性PCGS生成的语言可以被O（log n）限界图灵机识别。基于复杂度表征，针对上下文无关和上下文敏感语法分析了线性PCGS的生成能力。

著录项

来源
《Computers and Artificial Intelligence》 |1996年第3期|p.199-210|共12页
作者
Liming CAI;
展开▼
作者单位

Department of Mathematics East Carolina University Greenville, NC 27858, U.S.A.;

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类计算技术、计算机技术;
关键词
parallel communicating grammar systems; turing machines; space complexity; chomsky hierarchy;

机译：并行通信语法系统;图灵机;空间复杂度;乔姆斯基层次;

相似文献

外文文献
中文文献
专利

1. On the computation of the linear complexity and the k-error linear complexity of binary sequences with period a power of two [J] . Salagean A. IEEE Transactions on Information Theory . 2005,第3期

机译：关于周期为2的幂的二进制序列的线性复杂度和k-误差线性复杂度的计算
2. State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis [J] . Yamakami Tomoyuki Theoretical computer science . 2019,第期

机译：具有参数化程度有界图连接，子线性空间计算和线性空间假设的状态复杂性特征
3. An efficient synthesis approach for electromagnetic near- and far-field contoured patterns using alternative narrow-beam field functions transformed from the radiations of linearly excited array antennas with least computational complexity [J] . Hsi-Tseng Chou Radio Science . 2015,第5期

机译：一种有效的合成方法，它使用从线性激发阵列天线的辐射转换而来的可替代窄波束场函数，以最小的计算复杂度来对电磁近场和远场轮廓模式进行合成
4. On the Computation of the Linear Complexity and the k-Error Linear Complexity of Binary Sequences with Period a Power of Two [C] . Ana Salagean International Conference on Sequences and Their Applications . 2005

机译：关于两个频率的线性复杂性和k误差线性复杂性的两个
5. GEOMETRIC METHODS IN COMPUTATIONAL COMPLEXITY (DECISIONS TREES, NP-COMPLETENESS, LINEAR PROGRAMMING) [D] . KOLINEK, MARTIN 1985

机译：计算复杂性的几何方法（决策树，NP完全性，线性规划）
6. Predicting perceived visual complexity of abstract patterns using computational measures: The influence of mirror symmetry on complexity perception [O] . Andreas Gartus, Helmut Leder 2011

机译：使用计算量度预测抽象图案的视觉复杂度：镜面对称性对复杂度感知的影响
7. On the computation of the linear complexity and the k-error linear complexity of binary sequences with period a power of two [O] . Salagean A.M. 2005

机译：关于周期为2的幂的二进制序列的线性复杂度和k-误差线性复杂度的计算
8. Computational Complexity of Bosons in Linear Networks. [R] . White, A. 2017

机译：线性网络中玻色子的计算复杂性。

COMPUTATIONAL COMPLEXITY OF LINEAR PCGSs

摘要

著录项

相似文献

相关主题

期刊订阅