On partially blind multihead finite automata

被引：7

作者：

Lbarra, OH ^{[1
]}

Ravikumar, B

机构：

[1] Univ Calif Santa Barbara, Dept Comp Sci, Santa Barbara, CA 93106 USA

[2] Sonoma State Univ, Dept Comp Sci, Rohnert Pk, CA 94928 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2006年 / 356卷 / 1-2期

基金：

美国国家科学基金会;

关键词：

blind head; finite automaton; probabilistic automaton; counter machine; semilinear language;

D O I：

10.1016/j.tcs.2006.01.030

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This work is concerned with 1-way multihead finite automata (FA), both deterministic, and nondeterministic, in which the symbol under only one head controls its move. We call such a FA a partially blind multihead FA. We show some results regarding the decision problems and closure properties of blind multihead DFA and NFA. We also compare these devices with 1-way NFA augmented by reversal bounded counters. Finally, we also present some results regarding the simulation of a partially blind DFA and NFA by a probabilistic finite automaton. (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：190 / 199

页数：10

共 18 条

[1]

ALUR R, 1998, 6 ACM S FDN SOFTW EN, P175

[2]

[Anonymous], 1981, LECT NOTES COMPUTER

[3] REVERSAL-BOUNDED MULTIPUSHDOWN MACHINES [J].

BAKER, BS ;

BOOK, RV .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 8 (03) :315-332

[4] ON A COMPLEXITY HIERARCHY BETWEEN L AND NL [J].

CHO, S ;

HUYNH, DT .

INFORMATION PROCESSING LETTERS, 1988, 29 (04) :177-182

[5]

Dang Z, 2004, LECT NOTES COMPUT SC, V3328, P198

[6]

DWORK C, 1989, P 30 ANN S FOUND COM, P480

[7]

Greibach S. A., 1978, Theoretical Computer Science, V7, P311, DOI 10.1016/0304-3975(78)90020-8

[8]

Greibach S. A., 1976, Theoretical Computer Science, V1, P269, DOI 10.1016/0304-3975(76)90072-4

[9] MULTI-TAPE AND MULTI-HEAD PUSHDOWN AUTOMATA [J].

HARRISON, MA ;

IBARRA, OH .

INFORMATION AND CONTROL, 1968, 13 (05) :433-&

[10]

Hopcroft J., 1979, INTRO AUTOMATA FORMA

← 1 2 →