Weight-Reducing Hennie Machines and Their Descriptional Complexity

被引：0

作者：

Prusa, Daniel ^{[1
]}

机构：

[1] Czech Tech Univ, Fac Elect Engn, Prague 12135 2, Czech Republic

来源：

LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS (LATA 2014) | 2014年 / 8370卷

关键词：

Finite automata; two-way automata; Hennie machine; descriptional complexity; AUTOMATA; 2-WAY;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a constructive variant of the Hennie machine. It is demonstrated how it can facilitate the design of finite-state machines. We focus on the deterministic version of the model and study its descriptional complexity. The model's succinctness is compared with common devices that include the nondeterministic finite automaton, two-way finite automaton and pebble automaton.

引用

页码：553 / 564

页数：12

共 15 条

[1] STATE-COMPLEXITY OF FINITE-STATE DEVICES, STATE COMPRESSIBILITY AND INCOMPRESSIBILITY [J].

BIRGET, JC .

MATHEMATICAL SYSTEMS THEORY, 1993, 26 (03) :237-269

[2]

Durak Berke, 2007, Journal of Automata, Languages and Combinatorics, V12, P97

[3] Complexity results for two-way and multi-pebble automata and their logics [J].

Globerman, N ;

Harel, D .

THEORETICAL COMPUTER SCIENCE, 1996, 169 (02) :161-184

[4]

Goldstine J, 2002, J UNIVERS COMPUT SCI, V8, P193

[5] COMPUTATIONAL COMPLEXITY OF ONE-TAPE TURING MACHINE COMPUTATIONS [J].

HARTMANIS, J .

JOURNAL OF THE ACM, 1968, 15 (02) :325-+

[6] ONE-TAPE OFF-LINE TURING MACHINE COMPUTATIONS [J].

HENNIE, FC .

INFORMATION AND CONTROL, 1965, 8 (06) :553-&

[7]

Kari J., 2001, STACS 2001. 18th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings (Lecture Notes in Computer Science Vol.2010), P396

[8]

Meyer A. R., 1971, Conference record 1971 12th annual symposium on switching and automata theory, P188

[9]

Papadimitriou C. H., 1994, Computational Complexity

[10]

Prusa D, 2012, LECT NOTES COMPUT SC, V7410, P251, DOI 10.1007/978-3-642-31653-1_23

← 1 2 →