zbMATH — the first resource for mathematics

Characterizations and computational complexity of systolic trellis automata. (English) Zbl 0536.68048
Recently, K. Čulik II, J. Gruska and A. Salomaa [”Systolic trellis automata (for VLSI)”, Int. J. Comput. Math. (to appear)] have introduced the notion of systolic trellis automata. In the paper under review, various types of triangularly shaped trellis automata (roughly speaking, networks of finite processors) both deterministic and non-deterministic ones used as language recognizers have been studied. Their computational power is characterized in terms of suitably restricted Turing machines. These characterizations allow translating of Turing machine programs into programs of systolic trellis automata which is remarkable insofar as systolic trellis automata work to a certain extent in parallel. Further results included concern the Turing machine time and space complexity of language families recognizable by systolic trellis automata.
Reviewer: G.Wechsung

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
Full Text: DOI
[1] Chandler, W., Abstract families of deterministic languages, Proc. 1st ann. ACM symp. on the theory of computing, 21-30, (1969) · Zbl 1282.68153
[2] Conway, L.; Mead, C., Introduction to VLSI systems, (1980), Addison-Wesley Reading, MA
[3] Cook, S., An observation on time-storage trade-off, J. comput. system sci., 9, 308-316, (1974) · Zbl 0306.68026
[4] Cook, S.; Setili, R., Storage requirements for deterministic polynomial time recognizable languages, J. comput. system sci., 13, 25-37, (1976) · Zbl 0337.68031
[5] Internat. J. Comput. Math., to appear. · Zbl 0571.68042
[6] Culik, K.; Gruska, J.; Salomaa, A., Systolic Trellis automata: stability, decidability and complexity, () · Zbl 0626.68048
[7] Culik, K.; Gruska, J.; Salomaa, A., Systolic automata for VLSI on balanced trees, Acta informatica, 18, 335-344, (1983) · Zbl 0493.68054
[8] Culik, K.; Salomaa, A.; Wood, D., VLSI systolic trees as acceptors, ()
[9] Ginsburg, S., Algebraic and automata-theoretic properties of formal languages, (1975), North-Holland Amsterdam · Zbl 0325.68002
[10] Harrison, M.A., Introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058
[11] Hopcroft, J.; Ullman, J.D., Introduction to automata theory, languages, and computations, (1979), Addison-Wesley Reading, MA · Zbl 0426.68001
[12] Hopcroft, J.; Ullman, J.D., An approach to a unified theory of automata, Bell system tech. J., 46, 1763-1829, (1967) · Zbl 0155.34303
[13] Karp, R., Reducibility among combinatorial problems, (), 85-104 · Zbl 0366.68041
[14] Kung, H.; Seitz, Ch.L., Let’s design algorithms for VLSI systems, Proc. caltech conf. on very large scale integration, 65-90, (1979), Pasadena, CA
[15] Kung, H., The structure of parallel algorithms, ()
[16] Kung, H.; Leiserson, C., Systolic arrays (for VLSI), (), 256-282 · Zbl 0404.68037
[17] Leiserson, C.; Saxe, J., Optimizing synchronous systems, Proc. 22nd ann. symp. on foundations of computer science, 23-26, (1981), Nashville, TN
[18] Savitch, W., Relationship between nondeterministic and deterministic tape complexities, J. comput. system sci., 4, 177-192, (1970) · Zbl 0188.33502
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.