Language classes defined by time-bounded relativised cellular automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993) no. 5, pp. 403-432.
@article{ITA_1993__27_5_403_0,
     author = {Mahajan, Meena and Krithivasan, Kamala},
     title = {Language classes defined by time-bounded relativised cellular automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {403--432},
     publisher = {EDP-Sciences},
     volume = {27},
     number = {5},
     year = {1993},
     zbl = {0803.68076},
     mrnumber = {1252605},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1993__27_5_403_0/}
}
TY  - JOUR
AU  - Mahajan, Meena
AU  - Krithivasan, Kamala
TI  - Language classes defined by time-bounded relativised cellular automata
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1993
DA  - 1993///
SP  - 403
EP  - 432
VL  - 27
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1993__27_5_403_0/
UR  - https://zbmath.org/?q=an%3A0803.68076
UR  - https://www.ams.org/mathscinet-getitem?mr=1252605
LA  - en
ID  - ITA_1993__27_5_403_0
ER  - 
Mahajan, Meena; Krithivasan, Kamala. Language classes defined by time-bounded relativised cellular automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993) no. 5, pp. 403-432. http://www.numdam.org/item/ITA_1993__27_5_403_0/

[BC84] W. Bucher and K. Culik Ii, On real-time and linear-time cellular automata, R.A.I.R.O. Informatique théorique, 1984, 18, pp. 307-325. | Numdam | MR 775835 | Zbl 0547.68050

[BDG88] J. L. Balcázar J. Díaz and J. Gabarró, Structural Complexity I, volume 11 of EATCS Monograph Series, Springer-Verlag, Berlin, 1988. | MR 1047862 | Zbl 0638.68040

[BDG90] J. L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity II, volume 22 of EATCS Monograph Series, Springer-Verlag, Berlin, 1990. | MR 1056474 | Zbl 0746.68032

[Boo74] R. V. Book, Tally languages and complexity classes, Information and Control, 1974, 26, pp. 186-193. | MR 345446 | Zbl 0287.68029

[CC84] C. Choffrut and K. Culik Ii, On real-time cellular automata and trellis automata, Acta Informatica, 1984, 21, pp. 393-409. | MR 767316 | Zbl 0534.68039

[CGS84] K. Culik Ii, J. Gruska and A. Salomaa, Systolic trellis automata Part I. International J. of Computer Mathematics, 1984, 15, pp. 195-212. | MR 754266 | Zbl 0571.68041

[CIV88] J. H. Chang, O. H. Ibarra and A. Vergis, On the power of one-way communication. J. of the ACM, 1988, 35, pp. 697-726. | MR 963168

[Dye80] C. Dyer, One-way bounded cellular automata, Information and Control, 1980, 44, pp. 261-281. | MR 574487 | Zbl 0442.68082

[IJ87] O. H. Ibarra and T. Jiang, On one-way cellular arrays, SIAM J. of Computing, 1987, 16 pp. 1135-1154. | MR 917045 | Zbl 0646.68070

[IJ88] O. H. Ibarra and T. Jiang, Relating the power of cellular arrays to their closure properties, Theoretical Computer Science, 1988, 57, p. 225-238. | MR 960105 | Zbl 0646.68071

[IPK85] O. H. Ibarra, M. Palis and S. M. Kim, Some results concerning linear iterative (systolic) arrays, J. of Parallel and Distributed Computing, 1985, 2, pp. 182-218.

[Mah92] M. Mahajan, Studies in Language Classes Defined by Different Types of Time-Varying Cellular Automata, Ph. D. Thesis, Indian Institute of Technology, Madras, India, 1992.

[MK91] M. Mahajan and K. Krithivasan, Relativised cellular automata and complexity classes. In Proceedings of the 11th International FST Conference, New Delhi, December 1991, LNCS 560, pp. 172-185. | MR 1245502 | Zbl 0925.68328

[MK92] M. Mahajan and K. Krithivasan, Some results on time-varying and relativised cellular automata, International J. of Computer Mathematics, 1992, 43, pp.21-38. | Zbl 0761.68068

[Smi71] A. R. Smith Iii, Cellular automata complexity trade-offs, Information and Control, 1971, 18, pp. 466-482. | MR 307853 | Zbl 0222.94057

[Smi72] A. R. Smith Iii, Real-time language recognition by one-dimensional cellular automata, J. of Computer and System Sciences, 1972, 6, pp. 233-253. | MR 309383 | Zbl 0268.68044