Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Pushdown cellular automata
Kutrib M. Theoretical Computer Science215 (1/2):239-261,1999.Type:Article
Date Reviewed: Jan 1 2000

Kutrib introduces a new computing model called pushdown cellularautomata, which is obtained by replacing finite automata in traditionalcellular automata with pushdown automata. Natural restrictions of thismodel, called real-time and linear-time pushdown cellular automata,respectively, are also introduced. The main results contained in thepaper are two fundamental language-theoretic properties of theseautomata, namely, computational power and closure properties. The formerproperty is shown by proving inclusion and incomparability relationsamong the classes of languages for the automata defined in this paperand other known classes of languages defined by traditional cellularautomata and sequential automata. The operations considered for thelatter property include union, intersection, complementation,(erasing-free) morphisms, inverse morphisms, substitutions, andreversals; these are some of the most fundamental language-theoreticoperations. The paper is well written and should interest theoreticiansof formal languages and automata.

Reviewer:  Changwook Kim Review #: CR127463 (00010022)
Bookmark and Share
 
Unbounded-Action Devices (F.1.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Unbounded-Action Devices": Date
An efficient solution of the firing mob problem
Karel I., Dube S. Theoretical Computer Science 91(1): 57-69, 1991. Type: Article
Nov 1 1992
Real-time, pseudo real-time, and linear-time ITA
Karel I., Yu S. Theoretical Computer Science 47(1): 15-26, 1986. Type: Article
May 1 1988
Cellular automata machines: a new environment for modeling
Toffoli T. (ed), Margolus N., MIT Press, Cambridge, MA, 1987. Type: Book (9789780262200608)
Jan 1 1988
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