A Universal Cellular Automaton on the Ternary Heptagrid

被引：14

作者：

Margenstern, Maurice ^{[1
]}

Song, Yu ^{[1
]}

机构：

[1] Univ Metz, Lab Informat Theor & Appl, Dept Informat, EA 3097,IUT Metz, F-57045 Metz, France

来源：

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE | 2008年 / 223卷

关键词：

Cellular automata; hyperbolic plane; tessellations; universality;

D O I：

10.1016/j.entcs.2008.12.038

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we construct the first weakly universal cellular automaton on the ternary heptagrid. It requires six states only. It provides a universal automaton with less states than in the case of the pentagrid where the best result is nine states, a result also recently established by the authors.

引用

页码：167 / 185

页数：19

共 11 条

[1] A universal cellular automaton in the hyperbolic plane [J].

Herrmann, F ;

Margenstern, M .

THEORETICAL COMPUTER SCIENCE, 2003, 296 (02) :327-364

[2]

Margenstern M, 2003, LECT NOTES COMPUT SC, V2731, P48

[3] NP problems are tractable in the space of cellular automata in the hyperbolic plane [J].

Margenstern, M ;

Morita, K .

THEORETICAL COMPUTER SCIENCE, 2001, 259 (1-2) :99-128

[4]

Margenstern M., 2003, ASTC 2003

[5]

Margenstern M, 2007, CELLULAR AUTOMATA HY, V1

[6]

Margenstern M., 2001, COMPUTER SCI J MOLDO, V9, P1

[7]

Margenstern M., 2007, ACMC 2007

[8]

Margenstern M, 2000, J UNIVERS COMPUT SCI, V6, P1226, DOI DOI 10.3217/JUCS-006-12-1226

[9]

Margenstern M., 2008, P AUTOMATA 2008 JUN, P35

[10]

Margenstern M, 2006, J CELL AUTOM, V1, P1

← 1 2 →