Systolic trellis automatat†

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.

Abstract

In the second part of this paper we discuss mainly various programming techniques for systolic automata. These techniques are used to derive theoretical results e.g. the closure of (homogeneous) systolic automaton under Boolean operations, or that every linear context free language can be accepted by a homogeneous systolic automaton and that their languages have time complexity 0(n²)

Keywords:

• Systolic systems
• arrays of processors
• parallel algorithms
• trellis automata
• cellular automata
• VLSI

C.R. Subject Discriptors::

• B.6.1
• B.7.1
• F.l.l
• F.4.2
• F.4.3

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.

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.

Notes

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.