Advanced search
Publication Cover
International Journal of Computer Mathematics Volume 43, 1992 - Issue 1-2
Submit an article Journal homepage
18
Views
4
CrossRef citations to date
0
Altmetric
Original Articles

Some results on time-varying and relativised cellular automataFootnote*

Meena Mahajan Department of Computer Science and Engineering, Indian Institute of Technology, Madras, 600 036, India
&
Kamala Krithivasan Department of Computer Science and Engineering, Indian Institute of Technology, Madras, 600 036, India
Pages 21-38 | Received 19 Jun 1991, Published online: 19 Mar 2007

References

  • Bucher , W. and Culik , K. II . 1984 . On real-time and linear-time cellular automata . RAIRO Inform. Theor. , 18 ( 4 ) : 307 – 325 .
  • Choffrut , C. and Culik , K. II . 1984 . On real-time cellular automata and trellis automata . Acta Inform. , 21 ( 4 ) : 393 – 409 .
  • Chang , J. , Ibarra , O. and Vergis , A. 1988 . On the power of one-way communication . J. ACM , 35 ( 3 ) : 697 – 726 .
  • Dyer , C. 1980 . One-way bounded cellular automata . Inform, and Control , 44 ( 3 ) : 54 – 69 .
  • Ibarra , O. and Jiang , T. 1988 . Relating the power of cellular arrays to their closure properties . Theor. Computer Science , 57 ( 3 ) : 225 – 238 .
  • Ibarra , O. and Jiang , T. 1987 . On the computing power of one-way cellular arrays . SIAM J. Comput , 16 : 46 – 55 .
  • Ibarra , O. , Palis , M. and Kim , S. 1985 . Some results concerning linear iterative (systolic) arrays . J. Parallel and Distributed Comput. , 2 : 182 – 218 .
  • Krithivasan , K. and Das , A. Treating terminals as function values of time . Proceedings of the 4th FST & TCS conference, LNCS . Vol. 181 , pp. 188 – 201 .
  • Krithivasan , K. and Das , A. 1985 . Terminals weighted grammars and picture description . Computer Vision, Graphics and Image Processing , 30 : 13 – 31 .
  • Krithivasan , K. and Das , A. 1986 . Time varying finite automata . International Journal of Computer Mathematics , 19 : 103 – 123 .
  • Krithivasan , K. and Srinivasan , V. 1988 . Time varying pushdown automata . International Journal of Computer Mathematics , 24 : 223 – 236 .
  • Kosaraju , S. 1974 . On some open problems in the theory of cellular automata . IEEE Trans, on Comput. , C-23 : 561 – 565 .
  • Mahajan , Meena and Krithivasan , Kamala . 1991 . Relativised cellular automata and complexity classes, Technical Report, Dept. of Computer Science, IIT Madras, Nov 90 . LNCS Proceedings of the 11th FST & TCS conference . December 1991 , New Delhi. to appear
  • Nasu , M. 1979 . Indecomposable local maps of tessellation automata . Mathematical System Theory , 13 December : 81 – 93 .
  • Salomaa , A. 1973 . “ Formal Languages ” . Academic Press .
  • Smith , A. III . 1971 . Cellular automata complexity trade-offs . Inform, and Control , 18 : 466 – 482 .
  • Smith , A. III . 1972 . Real-time language recognition by one-dimensional cellular automata . J. Comput. System. Sci. , 6 : 233 – 253 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.