Two-dimensional cellular automata recognizer

Authors
Terrier, V
Citation
V. Terrier, Two-dimensional cellular automata recognizer, THEOR COMP, 218(2), 1999, pp. 325-346
Citations number
10
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
218
Issue
2
Year of publication
1999
Pages
325 - 346
Database
ISI
SICI code
0304-3975(19990506)218:2<325:TCAR>2.0.ZU;2-N
Abstract
We are investigating cellular automata on two-dimensional array as language recognizer. Linear acceleration for Moore and Von Neumann neighborhood is presented. Relationships with one-dimensional CAs and Turing machines are c onsidered. Some limitations of the power capabilities of real-time recognit ion are shown. (C) 1999 Published by Elsevier Science B.V. All rights reser ved.