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

How to cite

top

Mahajan, 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
  1. [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
  2. [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
  3. [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
  4. [Boo74] R. V. BOOK, Tally languages and complexity classes, Information and Control, 1974, 26, pp. 186-193. Zbl0287.68029MR345446
  5. [CC84] C. CHOFFRUT and K. CULIK II, On real-time cellular automata and trellis automata, Acta Informatica, 1984, 21, pp. 393-409. Zbl0534.68039MR767316
  6. [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
  7. [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
  8. [Dye80] C. DYER, One-way bounded cellular automata, Information and Control, 1980, 44, pp. 261-281. Zbl0442.68082MR574487
  9. [IJ87] O. H. IBARRA and T. JIANG, On one-way cellular arrays, SIAM J. of Computing, 1987, 16 pp. 1135-1154. Zbl0646.68070MR917045
  10. [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
  11. [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. 
  12. [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. 
  13. [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
  14. [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
  15. [Smi71] A. R. SMITH III, Cellular automata complexity trade-offs, Information and Control, 1971, 18, pp. 466-482. Zbl0222.94057MR307853
  16. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.