COMPUTATIONS AND DECIDABILITY OF ITERATIVE ARRAYS WITH RESTRICTED COMMUNICATION
Abstract
Iterative arrays (IAs) are linear arrays of interconnected interacting finite state machines, where one distinguished one is equipped with a one-way read-only input tape. We investigate IAs operating in real time whose inter-cell communication is bounded by a constant number of bits not depending on the number of states. Their capabilities are considered in terms of syntactical pattern recognition. It is known [17] that such devices can recognize rather complicated sets of unary patterns with a minimum amount of communication, namely one-bit communication. Some examples are the sets {a2n | n ≥ 1}, {an2 | n ≥ 1}, and {ap | p is prime}. Here, we consider non-unary patterns and it turns out that the non-unary case is quite different. We present several real-time constructions for certain non-unary syntactical patterns. For example, the sets {anbn | n ≥ 1}, {anbncn | n ≥ 1}, {an(bn)m | n, m ≥ 1}, and {anbamb(ba)n·m | n, m ≥ 1} are recognized in real time by IAs. Moreover, it is shown that real-time one-bit IAs can, in some sense, add and multiply integer numbers. Furthermore, decidability questions of communication restricted IAs are dealt with. Due to the constructions provided, undecidability results can be derived. It turns out that emptiness is still not even semidecidable for one-bit IAs despite their restricted communication. Moreover, also the questions of finiteness, infiniteness, inclusion, and equivalence are non-semidecidable.
References
T. Buchholz , A. Klein and M. Kutrib , Iterative arrays with a wee bit alternation, Fundamentals of Computation Theory (FCT 1999)1684,LNCS (1999) pp. 173–184. Google ScholarT. Buchholz , A. Klein and M. Kutrib , Iterative arrays with small time bounds, Mathematical Foundations of Computer Science (MFCS 1998)1893,LNCS (2000) pp. 243–252. Google ScholarT. Buchholz , A. Klein and M. Kutrib , Words, Languages and Combinatorics III (World Scientific Publishing, 2003) pp. 73–87. Link, Google Scholar- IEEE Trans. Comput. C 36, 64 (1987). Google Scholar
- IEEE Trans. Comput. C 18, 349 (1969). ISI, Google Scholar
- J. ACM 15, 680 (1968), DOI: 10.1145/321479.321490. Crossref, ISI, Google Scholar
- J. ACM 12, 388 (1965), DOI: 10.1145/321281.321290. Crossref, ISI, Google Scholar
- Proc. Symposia in Applied Mathematics 19, 42 (1967). Crossref, ISI, Google Scholar
- J. ACM 25, 116 (1978), DOI: 10.1145/322047.322058. Crossref, ISI, Google Scholar
C. Iwamoto , On time-constructible functions in one-dimensional cellular automata, Fundamentals of Computation Theory (FCT 1999)1684,LNCS (1999) pp. 317–326. Google Scholar- , Encyclopedia of Complexity and System Science , ed.
R. Meyers ( Springer ) . Google Scholar M. Kutrib and A. Malcher , Fast cellular automata with restricted inter-cell communication: Computational capacity, Theoretical Computer Science (IFIP TCS 2006)209,IFIP (2006) pp. 151–164. Google Scholar- IEICE Trans. Inf. Syst. E 87-D, 721 (2004). Google Scholar
-
H. Rogers , Theory of Recursive Functions and Effective Computability ( McGraw-Hill , New York , 1967 ) . Google Scholar - S. R. Seidel, Language recognition and the synchronization of cellular automata, Technical Report 79-02, Department of Computer Science, University of Iowa, 1979 . Google Scholar
- Fund. Inform. 52, 257 (2002). ISI, Google Scholar
- Fund. Inform. 58, 421 (2003). ISI, Google Scholar
T. Worsch , Linear time language recognition on cellular automata with restricted communication, Theoretical Informatics (LATIN 2000)1776,LNCS (2000) pp. 417–426. Google Scholar


