THE REACHABILITY PROBLEM FOR FINITE CELLULAR-AUTOMATA

Authors
CLEMENTI A IMPAGLIAZZO R
Citation
A. Clementi et R. Impagliazzo, THE REACHABILITY PROBLEM FOR FINITE CELLULAR-AUTOMATA, Information processing letters, 53(1), 1995, pp. 27-31
Citations number
16
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
53
Issue
1
Year of publication
1995
Pages
27 - 31
Database
ISI
SICI code
0020-0190(1995)53:1<27:TRPFFC>2.0.ZU;2-#
Abstract
We investigate the complexity of the Configuration REachability Proble m (CREP) for two classes of finite weakly predictable cellular automat a: the invertible and the additive ones. In both cases we prove that C REP belongs to the ''Arthur-Merlin'' class CoAM[2] (1).