Accepting runs in a two-way finite automaton

被引：2

作者：

Ibarra, Oscar H. ^{[1
]}

Dang, Zhe ^{[2
,3
]}

Li, Qin ^{[2
]}

机构：

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

[2] Anhui Univ Technol, Sch Comp, Maanshan, Anhui, Peoples R China

[3] Washington State Univ, Sch Elect Engn & Comp Sci, Pullman, WA 99164 USA

来源：

INFORMATION AND COMPUTATION | 2018年 / 260卷

关键词：

Two-way automata; Accepting run; Sampling; DECISION-PROBLEMS; MULTICOUNTER MACHINES;

D O I：

10.1016/j.ic.2018.03.002

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An accepting run in a two-way finite automaton M is a sequence of states that M enters during some accepting computation. The set of all such runs is denoted by L-run,L-M. We study the complexity of L-run,(M) when Mis a 2NFA (2DFA). We also look at the complexity of "position sampling" (the sequence of states that Menters in specified positions of some accepted input) in a 2NFA. In particular, we give some language properties of sampled runs of 2NFAs augmented with restricted unbounded storage. (C) 2018 Published by Elsevier Inc.

引用

页码：1 / 8

页数：8

共 12 条

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

BAKER, BS ;

BOOK, RV .

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

[2]

Cewei Cui, 2013, Language and Automata Theory and Applications. 7th International Conference, LATA 2013. Proceedings, P226, DOI 10.1007/978-3-642-37064-9_21

[3]

Dang Z., 2014, EMERGENCE COMPLEXITY, V12

[4] 1-WAY STACK AUTOMATA [J].

GINSBURG, S ;

GREIBACH, SA ;

HARRISON, MA .

JOURNAL OF THE ACM, 1967, 14 (02) :389-&

[5] DETERMINISTIC CONTEXT FREE LANGUAGES [J].

GINSBURG, S ;

GREIBACH, S .

INFORMATION AND CONTROL, 1966, 9 (06) :620-&

[6] THE COMPLEXITY OF DECISION-PROBLEMS FOR FINITE-TURN MULTICOUNTER MACHINES [J].

GURARI, EM ;

IBARRA, OH .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1981, 22 (02) :220-229

[7] Some decision problems concerning semilinearity and commutation [J].

Harju, T ;

Ibarra, O ;

Karhumäki, J ;

Salomaa, A .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2002, 65 (02) :278-294

[8] NEW DECIDABILITY RESULTS CONCERNING 2-WAY COUNTER MACHINES [J].

IBARRA, OH ;

JIANG, T ;

TRAN, N ;

WANG, H .

SIAM JOURNAL ON COMPUTING, 1995, 24 (01) :123-137

[9] REVERSAL-BOUNDED MULTICOUNTER MACHINES AND THEIR DECISION PROBLEMS [J].

IBARRA, OH .

JOURNAL OF THE ACM, 1978, 25 (01) :116-133

[10]

Ibarra OH, 2014, LECT NOTES COMPUT SC, V8614, P5, DOI 10.1007/978-3-319-09704-6_2

← 1 2 →