FINITE-AUTOMATON APERIODICITY IS PSPACE-COMPLETE

被引：44

作者：

CHO, S

HUYNH, DT

机构：

[1] Computer Science Program, University of Texas at Dallas, Richardson

来源：

THEORETICAL COMPUTER SCIENCE | 1991年 / 88卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0304-3975(91)90075-D

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we solve an open problem raised by Stern (1985) - "Is finite-automation aperiodicity PSPACE-complete?" - by providing an affirmative answer. We also characterize the exact complexity of two other problems considered by Stern: (1) dot-depth-one language recognition and (2) piecewise testable language recognition. We show that these two problems are logspace-complete for NL (the class of languages accepted by nondeterministic logspace-bounded Turing machines.

引用

页码：99 / 116

页数：18

共 9 条

[1]

CHO S, 1988, UTDCS2288 U TEX TECH

[2]

HARDY GH, 1954, INTRO THEORY NUMBERS, P343

[3]

Hopcroft J. E., 1979, INTRO AUTOMATA THEOR

[4] NONDETERMINISTIC SPACE IS CLOSED UNDER COMPLEMENTATION [J].

IMMERMAN, N .

SIAM JOURNAL ON COMPUTING, 1988, 17 (05) :935-938

[5]

Kozen D., 1977, 18th Annual Symposium on Foundations of Computer Science, P254, DOI 10.1109/SFCS.1977.16

[6]

Savitch W.J., 1970, J COMPUT SYST SCI, V4, P177, DOI [10.1016/S0022-0000(70)80006-X, DOI 10.1016/S0022-0000(70)80006-X]

[7] ON FINITE MONOIDS HAVING ONLY TRIVIAL SUBGROUPS [J].

SCHUTZENBERGER, MP .

INFORMATION AND CONTROL, 1965, 8 (02) :190-+

[8]

Simon I., 1975, Automata Theory and Formal Language 2nd GI Conference, P214

[9] COMPLEXITY OF SOME PROBLEMS FROM THE THEORY OF AUTOMATA [J].

STERN, J .

INFORMATION AND CONTROL, 1985, 66 (03) :163-176

← 1 →