Cellular Devices and Unary Languages

• Autorzy: Klein A. , Kutrib M.
• Języki publikacji: EN

Abstrakty

EN

Devices of interconnected parallel acting sequential automata are investigated from a language theoretic point of view. Starting with the well-known result that each unary language accepted by a deterministic one-way cellular automaton (OCA) in real time has to be a regular language, we will answer the three natural questions `How much time do we have to provide?' `How much power do we have to plug in the single cells (i.e., how complex has a single cell to be)?' and `How can we modify the mode of operation (i.e., how much nondeterminism do we have to add)?' in order to accept non-regular unary languages. We show the surprising result that for classes of generalized interacting automata parallelism does not yield to more computational capacity than obtained by a single sequential cell. Moreover, it is proved that there exists a unary complexity class in between the real-time and linear-time OCA languages, and that there is a gap between the unary real-time OCA languages and that class. Regarding nondeterminism as limited resource it is shown that a slight increase of the degree of nondeterminism as well as adding two-way communication reduces the time complexity from linear time to real time. Furthermore, by adding a wee bit nondeterminism an infinite hierarchy of unary language families dependent on the degree of nondeterminism is derived.

Słowa kluczowe

EN

cellular automata; unary formal languages; limited nondeterminism; generalized sequential machines; parallel computing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 78, nr 3
• Strony: 343--368
• Opis fizyczny: bibliogr. 29 poz., wykr.

Twórcy

autor

Klein A.

autor

Kutrib M.

• Institute of Informatics, University of Giessen, Arndstr. 2, D-35392 Giessen, Germany,

Bibliografia

• [1] Book, R. V.: Tally languages and complexity classes, Information and Control, 26, 1974, 186-193.
• [2] Book, R. V.: Context-sensitive tally languages, Bulletin of the European Association for Theoretical Computer Science, 15, 1981, 31-34.
• [3] Buchholz, Th., Klein, A., Kutrib, M.: On interacting automata with limited nondeterminism, Fundamenta Informaticae, 52, 2002, 15-38.
• [4] Buchholz, Th., Kutrib, M.: On the power of one-way bounded cellular time computers, Developments in Language Theory (S. Bozapalidis, Ed.), Aristotle University of Thessaloniki, Thessaloniki, Greece, 1997, 365-375.
• [5] Buchholz, Th., Kutrib,M.: Some relations between massively parallel arrays, Parallel Computing, 23, 1997, 1643-1662.
• [6] Buchholz, Th., Kutrib,M.: On time computability of functions in one-way cellular automata, Acta Informatica, 35, 1998, 329-352.
• [7] Choffrut, C., ˇCulik II, K.: On real-time cellular automata and trellis automata, Acta Informatica, 21, 1984, 393-407.
• [8] Chrobak,M.: Finite automata and unary languages, Theoretical Computer Science, 47, 1986, 149-158.
• [9] Cole, S. N.: Real-time computation by n-dimensional iterative arrays of finite-state machines, IEEE Transactions on Computers, C-18, 1969, 349-365.
• [10] Dyer, C. R.: One-way bounded cellular automata, Information and Control, 44, 1980, 261-281.
• [11] Geidmanis, D., Kan¸eps, J., Apsītis, K., Taimin¸a, D., Calude, E.: Tally languages accepted by alternating multitape finite automata, Computing and Combinatorics (T. Jiang, D. T. Lee, Eds.), LNCS 1276, Springer-Verlag, Berlin, 1997, 422-430.
• [12] Ginsburg, S., Greibach, S.: Abstract families of languages, Memoirs of the American Mathematical Society, 87, 1969, 1-32.
• [13] Ginsburg, S., Greibach, S. A., Harrison, M. A.: One-way stack automata, Journal of the ACM, 14, 1967, 389-418.
• [14] Ginsburg, S., Greibach, S. A., Harrison, M. A.: Stack automata and compiling, Journal of the ACM, 14, 1967, 172-201.
• [15] Ginsburg, S., Rice, H. G.: Two families of languages related to ALGOL, Journal of the ACM, 9, 1962, 350-371.
• [16] Hemachandra, L. A., Rubinstein, R. S.: Separating complexity classes with tally oracles, Theoretical Computer Science, 92, 1992, 309-318.
• [17] Ibarra, O. H., Jiang, T.: Relating the power of cellular arrays to their closure properties, Theoretical Computer Science, 57, 1988, 225-238.
• [18] Ibarra, O. H., Kim, S. M., Moran, S.: Sequential machine characterizations of trellis and cellular automata and applications, SIAM Journal on Computing, 14, 1985, 426-447.
• [19] Ibarra, O. H., Palis, M. A.: Some results concerning linear iterative (systolic) arrays, Journal of Parallel and Distributed Computing, 2, 1985, 182-218.
• [20] Kasami, T., Fuji, M.: Some results on capabilities of one-dimensional iterative logical networks, Electronics and Communications in Japan, 51-C, 1968, 167-176.
• [21] Krithivasan, K., Mahajan,M.: Nondeterministic, probabilistic and alternating computations on cellular array models, Theoretical Computer Science, 143, 1995, 23-49.
• [22] Kutrib, M.: Pushdown cellular automata, Theoretical Computer Science, 215, 1999, 239-261.
• [23] Mazoyer, J., Terrier, V.: Signals in one-dimensional cellular automata, Theoretical Computer Science, 217, 1999, 53-80.
• [24] Seidel, S. R.: Language Recognition and the Synchronization of Cellular Automata, Technical Report 79-02, Department of Computer Science, University of Iowa, Iowa City, 1979.
• [25] Smith III, A. R.: Real-time language recognition by one-dimensional cellular automata, Journal of Computer and System Sciences, 6, 1972, 233-253.
• [26] Terrier, V.: Language recognizable in real time by cellular automata, Complex Systems, 8, 1994, 325-336.
• [27] Terrier, V.: On real time one-way cellular array, Theoretical Computer Science, 141, 1995, 331-335.
• [28] Terrier, V.: Language not recognizable in real time by one-way cellular automata, Theoretical Computer Science, 156, 1996, 281-287.
• [29] Umeo, H., Morita, K., Sugata, K.: Deterministic one-way simulation of two-way real-time cellular automata and its related problems, Information Processing Letters, 14, 1982, 158-161.