REVERSAL-BOUNDED MULTICOUNTER MACHINES AND THEIR DECISION PROBLEMS

被引：300
作者：
IBARRA, OH
机构：
来源：
JOURNAL OF THE ACM | 1978年 / 25卷 / 01期
关键词：
D O I：
10.1145/322047.322058
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
引用
收藏
页码：116 / 133
页数：18
相关论文
共 28 条
[1]   REVERSAL-BOUNDED MULTIPUSHDOWN MACHINES [J].
BAKER, BS ;
BOOK, RV .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 8 (03) :315-332
[2]  
Bar-Hillel Yehoshua, 1961, SPRACHTYPOLOGIE UNIV, V14, P143
[3]  
Bird M., 1973, Journal of Computer and System Sciences, V7, P218, DOI 10.1016/S0022-0000(73)80045-5
[4]  
Davis M., 1958, COMPUTABILITY UNSOLV
[5]   ON RELATIONS DEFINED BY GENERALIZED FINITE AUTOMATA [J].
ELGOT, CC ;
MEZEI, JE .
IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1965, 9 (01) :47-&
[6]   RS-MACHINES WITH ALMOST BLANK TAPE [J].
ELGOT, CC ;
RUTLEDGE, JD .
JOURNAL OF THE ACM, 1964, 11 (03) :313-&
[7]  
Fischer P. C., 1968, Mathematical Systems Theory, V2, DOI 10.1007/BF01694011
[8]  
Friedman E. P., 1976, Theoretical Computer Science, V1, P297, DOI 10.1016/0304-3975(76)90074-8
[9]   BOUNDED ALGOL-LIKE LANGUAGES [J].
GINSBURG, S ;
SPANIER, EH .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1964, 113 (02) :333-+
[10]   DETERMINISTIC CONTEXT FREE LANGUAGES [J].
GINSBURG, S ;
GREIBACH, S .
INFORMATION AND CONTROL, 1966, 9 (06) :620-&
123