| 半图厄过程字问题的计算复杂性 |
| |
| 引用本文： | 张立昂.半图厄过程字问题的计算复杂性[J].计算机学报,1994,17(5):338-346. |
| |
| 作者姓名： | 张立昂 |
| |
| 作者单位： | 北京大学计算机科学与技术系 |
| |
| 摘 要： | 本文研究了几种加限制的半圈厄过程的字问题的计算复杂性。主要结果是：１．字母表只含一个符号的半圈厄过程的字问题是ＮＰ完全的；２．对于任一固定的字母表只含一个符号的半图厄过程，它的字问题属于Ｐ；３．单调的半图厄过程的字问题是ＰＳＰＡＣＥ完全的；４．限制派生长度的字问题是ＮＥＸＰＴＩＭＥ完全的。
|
| 关 键 词： | 计算复杂性 半圈厄过程 字问题 |
THE COMPLEXITY OF THE WORD PROBLEMS FOR SEMI-THUE PROCESSES |
| |
| Zhang Li''ang.THE COMPLEXITY OF THE WORD PROBLEMS FOR SEMI-THUE PROCESSES[J].Chinese Journal of Computers,1994,17(5):338-346. |
| |
| Authors: | Zhang Li'ang |
| |
| Abstract: | In this paper several restricted word problems for semi-Thue processes are studied.The main results are:1.The word problems for semi-Thue processes whose alphabets consist of just one symbol are NP-Complete.2.For any given semi-Thue process whose alphabet consists of just one symbol,the word problem is in p.3.The word problems for monotone semi-Thue processes are PSPACE-complete.4.The word problems with bounded length of derivations are NEXPTIME-complete. |
| |
| Keywords: | Computational complexity semi-Thue process NP PSPACE NEXPTIME |
| 本文献已被 CNKI 维普 等数据库收录！ |
