ALTERNATING PUSHDOWN AND STACK AUTOMATA

被引：69
作者：
LADNER, RE
LIPTON, RJ
STOCKMEYER, LJ
机构：
[1] PRINCETON UNIV,DEPT ELECT ENGN & COMP SCI,PRINCETON,NJ 08544
[2] IBM CORP,THOMAS J WATSON RES CTR,DEPT MATH SCI,YORKTOWN HTS,NY 10598
来源：
SIAM JOURNAL ON COMPUTING | 1984年 / 13卷 / 01期
关键词：
D O I：
10.1137/0213010
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
引用
收藏
页码：135 / 155
页数：21
相关论文
共 19 条
[1]  
BERMAN L, 1980, THEOR COMPUT SCI, V11, P71, DOI 10.1016/0304-3975(80)90037-7
[2]   ALTERNATION [J].
CHANDRA, AK ;
KOZEN, DC ;
STOCKMEYER, LJ .
JOURNAL OF THE ACM, 1981, 28 (01) :114-133
[3]   CHARACTERIZATIONS OF PUSHDOWN MACHINES IN TERMS OF TIME-BOUNDED COMPUTERS [J].
COOK, SA .
JOURNAL OF THE ACM, 1971, 18 (01) :4-&
[4]   PROPOSITIONAL DYNAMIC LOGIC OF REGULAR PROGRAMS [J].
FISCHER, MJ ;
LADNER, RE .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1979, 18 (02) :194-211
[5]   COMPUTING A PERFECT STRATEGY FOR NXN CHESS REQUIRES TIME EXPONENTIAL IN N [J].
FRAENKEL, AS ;
LICHTENSTEIN, D .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1981, 31 (02) :199-214
[6]   STACK AUTOMATA AND COMPILING [J].
GINSBURG, S ;
GREIBACH, SA ;
HARRISON, MA .
JOURNAL OF THE ACM, 1967, 14 (01) :172-&
[7]   2-WAY PUSHDOWN AUTOMATA [J].
GRAY, JN ;
HARRISON, MA ;
IBARRA, OH .
INFORMATION AND CONTROL, 1967, 11 (1-2) :30-&
[8]   PATH-SYSTEMS - CONSTRUCTIONS, SOLUTIONS AND APPLICATIONS [J].
GURARI, EM ;
IBARRA, OH .
SIAM JOURNAL ON COMPUTING, 1980, 9 (02) :348-374
[9]  
GURARI EM, 1982, MATH SYST THEORY, V15, P211
[10]  
HOPCROFT J, 1967, JCSS, V1, P166
12