# Language classes defined by time-bounded relativised cellular automata

Meena Mahajan; Kamala Krithivasan

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1993)

- Volume: 27, Issue: 5, page 403-432
- ISSN: 0988-3754

## Access Full Article

top## How to cite

topMahajan, Meena, and Krithivasan, Kamala. "Language classes defined by time-bounded relativised cellular automata." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 27.5 (1993): 403-432. <http://eudml.org/doc/92459>.

@article{Mahajan1993,

author = {Mahajan, Meena, Krithivasan, Kamala},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {language recognisers; relativised complexity classes; cellular automata; linear-time; real-time; tally languages; oracles; hierarchy},

language = {eng},

number = {5},

pages = {403-432},

publisher = {EDP-Sciences},

title = {Language classes defined by time-bounded relativised cellular automata},

url = {http://eudml.org/doc/92459},

volume = {27},

year = {1993},

}

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

PB - EDP-Sciences

VL - 27

IS - 5

SP - 403

EP - 432

LA - eng

KW - language recognisers; relativised complexity classes; cellular automata; linear-time; real-time; tally languages; oracles; hierarchy

UR - http://eudml.org/doc/92459

ER -

## References

top- [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. Zbl0547.68050MR775835
- [BDG88] J. L. BALCÁZAR J. DÍAZ and J. GABARRÓ, Structural Complexity I, volume 11 of EATCS Monograph Series, Springer-Verlag, Berlin, 1988. Zbl0638.68040MR1047862
- [BDG90] J. L. BALCÁZAR, J. DÍAZ and J. GABARRÓ, Structural Complexity II, volume 22 of EATCS Monograph Series, Springer-Verlag, Berlin, 1990. Zbl0746.68032MR1056474
- [Boo74] R. V. BOOK, Tally languages and complexity classes, Information and Control, 1974, 26, pp. 186-193. Zbl0287.68029MR345446
- [CC84] C. CHOFFRUT and K. CULIK II, On real-time cellular automata and trellis automata, Acta Informatica, 1984, 21, pp. 393-409. Zbl0534.68039MR767316
- [CGS84] K. CULIK II, J. GRUSKA and A. SALOMAA, Systolic trellis automata Part I. International J. of Computer Mathematics, 1984, 15, pp. 195-212. Zbl0571.68041MR754266
- [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. MR963168
- [Dye80] C. DYER, One-way bounded cellular automata, Information and Control, 1980, 44, pp. 261-281. Zbl0442.68082MR574487
- [IJ87] O. H. IBARRA and T. JIANG, On one-way cellular arrays, SIAM J. of Computing, 1987, 16 pp. 1135-1154. Zbl0646.68070MR917045
- [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. Zbl0646.68071MR960105
- [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. Zbl0925.68328MR1245502
- [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. Zbl0761.68068
- [Smi71] A. R. SMITH III, Cellular automata complexity trade-offs, Information and Control, 1971, 18, pp. 466-482. Zbl0222.94057MR307853
- [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. Zbl0268.68044MR309383

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.