A separation of determinism, Las Vegas and nondeterminism for picture recognition

被引：6

作者：

Duris, P ^{[1
]}

Hromkovic, J ^{[1
]}

Inoue, K ^{[1
]}

机构：

[1] Rhein Westfal TH Aachen, Dept Comp Sci 1, D-52056 Aachen, Germany

来源：

15TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS | 2000年

关键词：

D O I：

10.1109/CCC.2000.856752

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The investigation of the computational power of randomized computations is one of the central tasks of current complexity and algorithm theory: In this paper for the first time a "strong" separation between the power of determinism, Las Vegas randomization, and nondeterminism for a computing model is proved. The computing model considered here are finite automata with two-dimensional input rapes (i.e., finite automata recognizing picture languages). Moreover, a hierarchy on the degree of nondeterminism of two-dimensional finite automata is established.

引用

页码：214 / 228

页数：15

共 28 条

[1]

ABELSON H, 1978, P 19 IEEE S FDN COMP, P151

[2]

AHO AV, 1983, P 15 ANN ACM S THEOR, P133, DOI [DOI 10.1145/800061.808742, 10.1145/800061.808742.]

[3]

[Anonymous], 1997, COMMUNICATION COMPLE

[4]

BABI L, 1979, 7910 U MONTR DEP MAT

[5] CLASSES OF BOUNDED NONDETERMINISM [J].

DIAZ, J ;

TORAN, J .

MATHEMATICAL SYSTEMS THEORY, 1990, 23 (01) :21-32

[6] EXACT LOWER TIME-BOUNDS FOR COMPUTING BOOLEAN FUNCTIONS ON CREW PRAMS [J].

DIETZFELBINGER, M ;

KUTYLOWSKI, M ;

REISCHUK, R .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 48 (02) :231-254

[7]

Duris P, 1997, LECT NOTES COMPUT SC, V1200, P117, DOI 10.1007/BFb0023453

[8] COMPUTATIONAL COMPLEXITY OF PROBABILISTIC TURING MACHINES [J].

GILL, J .

SIAM JOURNAL ON COMPUTING, 1977, 6 (04) :675-695

[9] ON THE RELATION BETWEEN AMBIGUITY AND NONDETERMINISM IN FINITE AUTOMATA [J].

GOLDSTINE, J ;

LEUNG, H ;

WOTSCHKE, D .

INFORMATION AND COMPUTATION, 1992, 100 (02) :261-270

[10] ON MEASURING NONDETERMINISM IN REGULAR LANGUAGES [J].

GOLDSTINE, J ;

KINTALA, CMR ;

WOTSCHKE, D .

INFORMATION AND COMPUTATION, 1990, 86 (02) :179-194

← 1 2 3 →