×

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

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[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: 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.; Internat. J. Comput. Math. · Zbl 0571.68042
[6] Culik, K.; Gruska, J.; Salomaa, A., Systolic trellis automata: Stability, decidability and complexity, (Res. Rept. CS-82-04 (1982), Department of Computer Science, University of Waterloo) · 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, (Res. Rept. CS-81-32 (1981), Department of Computer Science, University of Waterloo)
[9] Ginsburg, S., Algebraic and Automata-Theoretic Properties of Formal Languages (1975), North-Holland: North-Holland Amsterdam · Zbl 0325.68002
[10] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[11] Hopcroft, J.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computations (1979), Addison-Wesley: 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, (Complexity of Computer Computations (1972), Plenum: Plenum New York), 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, (Res. Rept. (1979), Department of Computer Science, Carnegie-Mellon University)
[16] Kung, H.; Leiserson, C., Systolic arrays (for VLSI), (Duff, I. S.; Stewart, G. W., Proc. Sparse Matrix (1979), Society for Industrial and Applied Mathematics), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.