Language classes defined by time-bounded relativised cellular automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 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  - 
%0 Journal Article
%A Mahajan, Meena
%A Krithivasan, Kamala
%T Language classes defined by time-bounded relativised cellular automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1993
%P 403-432
%V 27
%N 5
%I EDP-Sciences
%G en
%F 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, Volume 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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

[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

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

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

[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 | Zbl

[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 | Zbl

[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

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

[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 | Zbl