World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue on Cellular Automata Theory and ApplicationsNo Access

COMPUTATIONS AND DECIDABILITY OF ITERATIVE ARRAYS WITH RESTRICTED COMMUNICATION

    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 Scholar
    • T. 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 Scholar
    • T. Buchholz, A. Klein and M. Kutrib, Words, Languages and Combinatorics III (World Scientific Publishing, 2003) pp. 73–87. LinkGoogle Scholar
    • J. H. Chang, O. H. Ibarra and M. A. Palis, IEEE Trans. Comput. C 36, 64 (1987). Google Scholar
    • S. N. Cole, IEEE Trans. Comput. C 18, 349 (1969). ISIGoogle Scholar
    • D. F. Cudia and W. E. Singletary, J. ACM 15, 680 (1968), DOI: 10.1145/321479.321490. Crossref, ISIGoogle Scholar
    • P. C. Fischer, J. ACM 12, 388 (1965), DOI: 10.1145/321281.321290. Crossref, ISIGoogle Scholar
    • J. Hartmanis, Proc. Symposia in Applied Mathematics 19, 42 (1967). Crossref, ISIGoogle Scholar
    • O. H. Ibarra, J. ACM 25, 116 (1978), DOI: 10.1145/322047.322058. Crossref, ISIGoogle Scholar
    • C. Iwamotoet al., On time-constructible functions in one-dimensional cellular automata, Fundamentals of Computation Theory (FCT 1999)1684, LNCS (1999) pp. 317–326. Google Scholar
    • M.   Kutrib , 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
    • A. Malcher, 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
    • H. Umeo and N. Kamikawa, Fund. Inform. 52, 257 (2002). ISIGoogle Scholar
    • H. Umeo and N. Kamikawa, Fund. Inform. 58, 421 (2003). ISIGoogle 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