Systolic trellis automatatFootnote†

This work was supported by Natural Scienceand Engineering Research Council of Canada grants A-7403 and A-1617. Most of the work was done while the second and third author were visiting the Computer Science Department of the University of Waterloo.

References

• Berstel , J. 1979 . Transductions and Context‐free Languages , Stuttgart : B. G. Teubner .
   Google Scholar
• Choffrut , C. and Culik , K. II . 1979 . On real time cellular automata and trellis automata . Acta Informatica , to appear
   Google Scholar
• Culik , K. II , Gruska , J. and Salomaa , A. 1981 . Systolic Automata for VLSI , University of Waterloo . Research Report CS-81-33, Department of Computer Science
   Google Scholar
• Culik , K. II , Gruska , J. and Salomaa , A. 1982 . Systolic Trellis Automata: Stability, Decidability and Complexity , University of Waterloo . Research Report CS-82-04, Department of Computer Science
   Google Scholar
• Culik , K. II , Gruska , J. and Salomaa , A. 1983 . Systolic automata for VLSI on balanced trees . Acta Informatica , 18 : 335 – 344 .
   Web of Science ®Google Scholar
• Culik , K. II , Salomaa , A. and Wood , D. 1983 . Systolic tree acceptors . RAIRO , 18 to appear
   Google Scholar
• Kung , H. T. 1979 . “ Let's design algorithms for VLSI systems ” . Edited by: Seitz , Ch. L. 65 – 90 . Pasadena . Proc. Caltech Conference on Very Large Scale Integration
   Google Scholar
• Kung , H. T. 1979 . The Structure of Parallel Algorithms , Carnegie‐Mellon University . Research report, Department of Computer Science
   Google Scholar
• King , H. T. and Leiserson , C. E. 1979 . “ Proc. Sparse Matrix ” . In Systolic Arrays (for VLSI) Edited by: Duff , I. S. and Stewart , G. W. 256 – 282 . Society for Industrial and Applied Mathematics
   Google Scholar
• Leiserson , C. E. and Saxe , J. B. 1981 . “ Proc. 22nd Annual Symposium on foundations of computer science ” . In Optimising Synchronous Systems , 23 – 36 . Tennessee : Nashville .
   Google Scholar
• Mead , C. A. and Conway , L. A. 1980 . Introduction to VLSI Systems , Addison‐Wesley . Reading Massachussets
   Google Scholar
• Ibarra , O. H. and Kim , S. M. 1980 . Characterization and computational complexity of systolic trellis automata . Theoretical Computer Science , to appear
   Google Scholar
• Ibarra O. H. Kim S. M. Noran S. Trellis automata: characterizations, speed-up, hierarchy, decision problems Submitted for publication
   Google Scholar
• Dyer , C. R. 1980 . One‐way bounded cellular automata . Inf. and Control , 44 : 261 – 281 .
   Google Scholar
• Morita Umeoh , K. and Sugata , K. 1982 . Deterministic one‐way simulation of two‐way real‐time cellular automata and its related problems . Information Proc. Letters , 14 : 158 – 161 .
   Web of Science ®Google Scholar