Language classes defined by time-bounded relativised cellular automata
Mahajan, Meena ; Krithivasan, Kamala
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 27 (1993), p. 403-432 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1993-01-01
@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},
     volume = {27},
     year = {1993},
     pages = {403-432},
     mrnumber = {1252605},
     zbl = {0803.68076},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1993__27_5_403_0}
}

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) pp. 403-432. http://gdmltest.u-ga.fr/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