@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}, mrnumber = {1252605}, zbl = {0803.68076}, 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 SP - 403 EP - 432 VL - 27 IS - 5 PB - EDP-Sciences UR - http://www.numdam.org/item/ITA_1993__27_5_403_0/ 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 %U http://www.numdam.org/item/ITA_1993__27_5_403_0/ %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, Tome 27 (1993) no. 5, pp. 403-432. http://www.numdam.org/item/ITA_1993__27_5_403_0/
[BC84] On real-time and linear-time cellular automata, R.A.I.R.O. Informatique théorique, 1984, 18, pp. 307-325. | Numdam | MR | Zbl
and ,[BDG88] Structural Complexity I, volume 11 of EATCS Monograph Series, Springer-Verlag, Berlin, 1988. | MR | Zbl
and ,[BDG90] Structural Complexity II, volume 22 of EATCS Monograph Series, Springer-Verlag, Berlin, 1990. | MR | Zbl
, and ,[Boo74] Tally languages and complexity classes, Information and Control, 1974, 26, pp. 186-193. | MR | Zbl
,[CC84] On real-time cellular automata and trellis automata, Acta Informatica, 1984, 21, pp. 393-409. | MR | Zbl
and ,[CGS84] Systolic trellis automata Part I. International J. of Computer Mathematics, 1984, 15, pp. 195-212. | MR | Zbl
, and ,[CIV88] On the power of one-way communication. J. of the ACM, 1988, 35, pp. 697-726. | MR
, and ,[Dye80] One-way bounded cellular automata, Information and Control, 1980, 44, pp. 261-281. | MR | Zbl
,[IJ87] On one-way cellular arrays, SIAM J. of Computing, 1987, 16 pp. 1135-1154. | MR | Zbl
and ,[IJ88] Relating the power of cellular arrays to their closure properties, Theoretical Computer Science, 1988, 57, p. 225-238. | MR | Zbl
and ,[IPK85] Some results concerning linear iterative (systolic) arrays, J. of Parallel and Distributed Computing, 1985, 2, pp. 182-218.
, and ,[Mah92] Studies in Language Classes Defined by Different Types of Time-Varying Cellular Automata, Ph. D. Thesis, Indian Institute of Technology, Madras, India, 1992.
,[MK91] 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
and ,[MK92] Some results on time-varying and relativised cellular automata, International J. of Computer Mathematics, 1992, 43, pp.21-38. | Zbl
and ,[Smi71] Cellular automata complexity trade-offs, Information and Control, 1971, 18, pp. 466-482. | MR | Zbl
,[Smi72] Real-time language recognition by one-dimensional cellular automata, J. of Computer and System Sciences, 1972, 6, pp. 233-253. | MR | Zbl
,