×

Systolic tree acceptors. (English) Zbl 0571.68043

Motivated by VLSI and systolic arrays this paper introduces a new kind of automata as language acceptors: systolic tree acceptors (STA). Like in a tree representing an arithmetical expression an operator or function symbol is associated with each (internal) node of the tree. For convenience the underlying tree is supposed to be infinite, satisfying a regularity and a growth rate condition. The entire input string (augmented with blanks) is fed simultaneously at the smallest level of the tree which contains sufficiently many nodes that it fits. The final decision about acceptance is made at the root of the tree. Regular languages can be accepted by STAs with any underlying tree. Depending on the tree structure certain languages with a suitable exponential growth rate are acceptable too, but all the examples of nonregular context-free languages which were studied are not acceptable with an underlying binary tree structure. If we fix the tree structure, we obtain a language family which is closed under Boolean operations. However, in general the class of STA acceptable languages has weak closure properties. As a normal form of an STA one may require that nodes of the same arity represent identical functions. All these introductory results are presented nicely with mostly informal outlines of proofs which seems to be quite appropriate in this area.
Reviewer: M.Kunze

MSC:

68Q45 Formal languages and automata
68Q80 Cellular automata (computational aspects)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] 1. L. CONWAY and C. MEAD, Introduction to VLSI Systems, Addison-Wesley, 1980.
[2] 2. K. CULIK II and H. A. MAURER, Tree Controlled Grammars, Computing, Vol. 19, 1977, pp. 129-139. Zbl0363.68108 MR464718 · Zbl 0363.68108
[3] 3 G. ROZENBERG and A. SALOMAA, The Mathematical Theory of L Systems, Academic Press, 1980. Zbl0508.68031 MR561711 · Zbl 0508.68031
[4] 4. A. SALOMAA, Formal Languages, Academic Press, 1973. Zbl0262.68025 MR438755 · Zbl 0262.68025
[5] 5. H. T. KUNG, Let’s Design Algorithms for VLSI Systems, Proceedings of the Caltech Conference on VLSI, Charles L. Seitz, Ed., Pasadena, California, January 1979, pp. 65-90.
[6] 6. C. E. LEISERSON and J. B. SAXE, Optimizing Synchronous Systems, 22nd Annual Symposium on Foundations of Computer Science, October 1981, pp. 270-281.
[7] 7. K. CULIK II, J. GRUSKA and A. SALOMAA, Systolic Trellis Automata, International Journal of Computer Mathematics, to appear. Zbl0571.68042 · Zbl 0571.68042
[8] 8. C. R. DYER and A. ROSENFELD, Triangle Cellular Automata, Information and Control, Vol. 48, 1981, pp. 54-69. Zbl0459.68023 MR629464 · Zbl 0459.68023
[9] 9. R. W. FLOYD and J. D. ULLMAN, The Compilation of Regular Expressions into Integrated Circuits, Proceedings 21st Annual Symposium on Foundations of Computer Science, I.E.E.E. Computer Society, 1980, pp. 260-269.
[10] 10. M. J. FOSTER, and H. T. KUNG, Recognizable Regular Languages with Programmable Building-Blocks, in J. P. GRAY, Ed., VLSI 81, Academic Press 1981, pp. 75-84.
[11] 11. M. STEINBY, Systolic Trees and Systolic Language Recognition by Tree Automata, Theoretical Computer Science, to appear. Zbl0501.68046 MR693057 · Zbl 0501.68046
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.