One-Dimensional Cellular Automaton Transducers

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

Abstrakty

EN

The parallel models of cellular automata and iterative arrays are investigated towards their ability to compute transductions, that is, to transform inputs into outputs. The families of transductions computed are classified with regard to the time allowed to process the input and the output, respectively. The time complexities of real-time and linear-time are of particular interest. First, the computational capabilities of iterative array transducers are investigated and proper inclusions between real-time and linear-time can be obtained. Then, iterative array transducers and cellular automaton transducers are considered, that is, sequential input/output mode is compared to parallel input/output mode. Here, the result is that the parallel mode is not weaker than the sequential one, but with regard to certain time complexities the parallel mode is even more powerful than the sequential one. In the second part of the paper, cellular automaton transducers and iterative array transducers are compared with the conventional sequential transducer models, namely, finite state transducers and pushdown transducers. It turns out that unambiguous finite state transducers and deterministic pushdown transducers can be simulated by both parallel models, but cellular automaton transducers achieve a faster simulation than iterative array transducers.

Słowa kluczowe

EN

cellular automata; finite state transducer; iterative arrays; pushdown transducers; transduction

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 126, nr 2-3
• Strony: 201--224
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Kutrib M.

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

autor

Malcher A.

• Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany

Bibliografia

• [1] Aho, A. V., Ullman, J. D.: The theory of parsing, translation, and compiling, vol. I: Parsing, Prentice-Hall Inc., Englewood Cliffs, New Jersey, USA, 1972.
• [2] Berstel, J.: Transductions and Context-Free-Languages, Teubner, Stuttgart, 1979.
• [3] Buchholz, T., Kutrib, M.: Some relations between massively parallel arrays, Parallel Comput., 23(11), 1997, 1643-1662.
• [4] Choffrut, C., Culik II, K.: On Real-Time Cellular Automata and Trellis Automata, Acta Inform., 21, 1984, 393-407.
• [5] Cole, S. N.: Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines, IEEE Trans. Comput., C-18(4), 1969, 349-365.
• [6] Culik II, K., Yu, S.: Iterative Tree Automata, Theoret. Comput. Sci., 32, 1984, 227-247.
• [7] Grandjean, A., Richard, G., Terrier, V.: Linear functional classes over cellular sutomata, 18th Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2012), EPTCS 90, 2012, 177-193.
• [8] Harrison, M. A.: Introduction to Formal Language Theory, Addison-Wesley, Reading, 1978.
• [9] Ibarra, O. H., Jiang, T., Wang, H., Parallel parsing on a one-way linear array of finite-state machines, Theoret. Comput. Sci., 85, 1991, 53-74.
• [10] Kutrib, M.: Automata Arrays and Context-Free Languages, in: Where Mathematics, Computer Science and Biology Meet (C. Martin-Vide, V. Mitrana, Eds.), Kluwer Academic Publishers, 2001, 139-148.
• [11] Kutrib, M.: Cellular Automata - A Computational Point of View, in: New Developments in Formal Languages and Applications (G. Bel-Enguix, M. D. Jimenez-Lopez, C. Martin-Vide, Eds.), chapter 6, Springer, 2008, 183-227.
• [12] Kutrib, M.: Cellular Automata and Language Theory, in: Encyclopedia of Complexity and System Science (R. Meyers, Ed.), Springer, 2009, 800-823.
• [13] Malcher, A.: On the Descriptional Complexity of Iterative Arrays, IEICE Trans. Inf. Syst., E87-D(3), 2004, 721-725.
• [14] Smith III, A. R.: Cellular Automata and Formal Languages, 11th Ann. IEEE Symposium on Switching and Automata Theory, IEEE, 1970.
• [15] Smith III, A. R.: Real-Time Language Recognition by One-Dimensional Cellular Automata, J. Comput. System Sci., 6, 1972, 233-253.
• [16] Weber, A., Klemm, R.: Economy of Description for Single-Valued Transducers, Inform. Comput., 118,1995, 327-340.
• [17] Yu, S.: Regular Languages, in: Handbook of Formal Languages (G. Rozenberg, A. Salomaa, Eds.), vol. 1, chapter 2, Springer, Berlin, 1997,41-110.