Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Uniform continuity of relations and nondeterministic cellular automata
Furusawa H. Theoretical Computer Science673  19-29,2017.Type:Article
Date Reviewed: Oct 19 2017

Cellular automata are computational structures that can be applied for modeling a wide range of systems in different areas of science. Usually they are characterized by local rules operating on individual cells and their neighborhoods. This paper is concerned with global characterizations. In particular, it extends earlier results to cover the remaining open case, a global characterization of non-deterministic cellular automata with infinite alphabets.

The paper starts with a short introduction stating the already-known results on global characterizations of deterministic and non-deterministic automata, followed by the first technical section fixing some basic concepts and definitions of relational algebra and “uniform spaces,”--a set together with a set of relations on that set with certain closure properties. The following section introduces notions of continuity for relations and uniform spaces together with some technical properties needed in the remainder of the paper.

The main technical part of the paper defines nondeterministic cellular automata and certain relations on their set of configurations. Special properties of these relations are also introduced and some techniques for proving these properties are stated and proven. With the help of this technical apparatus, the global characterization of non-deterministic cellular automata is finally proven. The paper ends with a very short conclusion.

The whole paper currently seems to me to be about a rather technical topic that is mathematically very interesting and beautiful. A few terms from topology are used in the paper and assumed to be known, so some readers might need to look some of them up. On the whole, the paper is very detailed and carefully written.

Reviewer:  Markus Wolf Review #: CR145599 (1712-0813)
Bookmark and Share
 
Automata (F.1.1 ... )
 
 
Alternation And Nondeterminism (F.1.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Automata": Date
The congruence theory of closure properties of regular tree languages
Tirri S. Theoretical Computer Science 76(2-3): 261-271, 2001. Type: Article
Jun 1 1991
Distribution and synchronized automata
Petit A. Theoretical Computer Science 76(2-3): 285-308, 2001. Type: Article
Feb 1 1992
Efficient simulation of finite automata by neural nets
Alon N., Dewdney A., Ott T. Journal of the ACM 38(2): 495-514, 1991. Type: Article
Dec 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy