ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA

被引：13

作者：

Kutrib, Martin ^{[2
]}

Messerschmidt, Hartmut ^{[3
]}

Otto, Friedrich ^{[1
]}

机构：

[1] Univ Kassel, Fachbereich Elektrotech Informat, D-34109 Kassel, Germany

[2] Univ Giessen, Inst Informat, D-35392 Giessen, Germany

[3] Technol Zentrum Informat, D-28359 Bremen, Germany

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2010年 / 21卷 / 05期

关键词：

Two-pushdown automaton; restarting automaton; stateless device; CHURCH-ROSSER LANGUAGES; CONTEXT-SENSITIVE LANGUAGES;

D O I：

10.1142/S0129054110007556

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Restarting automata and two-pushdown automata are investigated that have a single internal state only. As such an automaton must always stay in the same state, this state is of no importance for the behaviour of the automaton. Accordingly, these automata are called stateless. We consider various types of stateless two-pushdown automata and restarting automata. We investigate their expressive power, comparing them in particular to each other and to the corresponding types of automata with states.

引用

页码：781 / 798

页数：18

共 16 条

[1]

Autebert J.-M., 1997, Handbook of formal languages, V1, P111, DOI [10.1007/978-3-642-59136-5_3, DOI 10.1007/978-3-642-59136-5_3]

[2] Growing context-sensitive languages and Church-Rosser languages [J].

Buntrock, G ;

Otto, F .

INFORMATION AND COMPUTATION, 1998, 141 (01) :1-36

[3]

HARRISON M, 1978, INTRO FORMAL LANGUAG

[4]

Holzer M, 2005, LECT NOTES COMPUT SC, V3623, P305, DOI 10.1007/11537311_27

[5]

Hopcroft J., 1979, Introduction to automata theory, languages, and computation

[6] On stateless multihead automata:: Hierarchies and the emptiness problem [J].

Ibarra, Oscar H. ;

Karhumaki, Juhani ;

Okhotin, Alexander .

LATIN 2008: THEORETICAL INFORMATICS, 2008, 4957 :94-+

[7]

JANCAR P, 1995, LNCS, V965, P283

[8] Lower bound technique for length-reducing automata [J].

Jurdziniski, Tomasz ;

Lorys, Krzysztof .

INFORMATION AND COMPUTATION, 2007, 205 (09) :1387-1412

[9]

Jurdzinski T, 2002, LECT NOTES COMPUT SC, V2380, P147

[10]

McNaughton R., 1974, Mathematical Systems Theory, V8, P60, DOI 10.1007/BF01761708

← 1 2 →