查看: 2607|回复: 1

[书籍资源] An Introduction to CELLULAR AUTOMATA

字体大小: 正常放大

WSHXPY

62 主题	17 听众	5897 积分

升级 17.94%

TA的每日心情

	奋斗 2017-9-16 20:51

签到天数: 164 天

[LV.7]常住居民III

超级版主

自我介绍: 来自哈工大,喜欢数学建模

群组: 2015美赛优秀论文解析

群组: 2014第三期英语写作

群组: 数学中国_哈工大群

群组: 数学建模

群组: 2016研赛备战群组

电梯直达

1^#

发表于 2015-2-5 20:12 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

本帖最后由 WSHXPY 于 2015-2-5 20:13 编辑

An Introduction to CELLULAR AUTOMATA

By H′el`ene Vivien

The order of the book is from the simple to the more complex, introducing a question as soon as we have the frame to put it and the means to solve it.
Chapter 1 starts with the ﬁnite linear c.a’s. They are precisely the required framework for introducing the Firing Squad Synchronization Problem, and giv-ing the ﬁrst and simplest solution, that of Minsky.
Chapter 2 presents Mazoyer’s solution which is elegant and sophisticated. The needed display of technics also introduces to the abstract notions to be devel-oped in later chapters.
Chapter 3 clariﬁes some important notions related to semi-inﬁnite linear c.a’s : inputs and outputs, computing a function, recognizing a language. It also gives fundamental examples of language recognition.
It is then possible to relate c.a’s with Turing machines, which is done in Chapter 4, which ends with Atrubin’s real time algorithm to multipliy two integer numbers. Semi-inﬁnite linear c.a’s are the required framework for many developments in the next chapters.
Chapter 5 gives a precise deﬁnition of a signal. Diﬀerent notions then appear, those of waves and networks of signals, with the beautiful example of Fischer’s c.a for recognizing prime numbers, and the gap theorem for waves.
In chapter 6, slowing down is studied. It may seem absurd at ﬁrst view. But we shall see that it is useful, next to speeding up, for intelligently driving our c.a's. This incidentally leads us to build a c.a which computes particular word morphisms.
Chapter 7 is an exhaustive study of speeding up, for recognizers and for syn-chronizers.
Chapter 8 is devoted to the study of the family of synchronization times. The richness of this family allows for ﬂexible use of the synchronization process.
Chapter 9 introduces the geometrical c.a’s, i.e. c.a’s the states of which are geo-metrical pieces. Numerous examples give new and elegant methods for speeding up.
Chapter 10 is a general study of n-dimensional c.a’s and of the languages that they recognize. It is based on Cole [6].
In the last three chapters, communication delays are introduced. They consid-erably complexify the behavior of c.a’s, in particular their synchronization.
Chapter 11 considers a line of two automata. Solutions for synchronizing these two automata are presented, and they are proved to be almost optimal.
Chapter 12 considers a ﬁnite line of automata. A c.a synchronizing such a line is presented, which mimics Minsky’s method of chapter 1.
In chapter 13 we ﬁrst give the general deﬁnition of a network, without or with communication delays. We show how automata placed at the nodes of the net-work may solve graph problems. We then use this possibility to transform the network into a ﬁctive line. Applying the result of the preceding chapter to this line, we obtain a c.a for synchronizing the network.