×

On a family of L languages resulting from systolic tree automata. (English) Zbl 0549.68081

The class of BT-VLSI languages accepted by binary systolic tree automata contains all rational languages, is closed under Boolean operations, and the equivalence problem is decidable. This paper shows that every BT-VLSI language is an EOL language. In order to describe the relationship between these two classes the notion of a semibinary EOL language is introduced. Every EOL language is the coding of a semibinary EOL language, and an EOL language belongs to BT-VLSI if it is a coding of a semibinary suffix EOL language. On the other hand, the emptiness problem for the class of T-VLSI languages, i.e. the languages accepted by general systolic tree automata, can be reduced to two well-known open problems about \({\mathbb{Z}}\)-rational formal power series. In particular it remains open whether an arbitrary T-VLSI language is an EOL language.
Reviewer: M.Kunze

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Culik, K., On some families of languages related to developmental systems, Internat. J. Comput. Math., 4, 31-42 (1974) · Zbl 0294.68025
[2] Culik, K.; Salomaa, A.; Wood, D., VLSI systolic trees as acceptors, (Research Report CS-81-32 (1981), Department of Computer Science, University of Waterloo: Department of Computer Science, University of Waterloo Waterloo, Ontario)
[3] Culik, K.; Gruska, J.; Salomaa, A., Systolic trellis automata (for VLSI), (Research Report CS-81-34 (1981), Department of Computer Science, University of Waterloo: Department of Computer Science, University of Waterloo Waterloo, Ontario) · Zbl 0571.68042
[4] Culik, K.; Gruska, J.; Salomaa, A., Systolic automata for VLSI on balanced trees, (Research Report CS-82-01 (1982), Department of Computer Science, University of Waterloo: Department of Computer Science, University of Waterloo Waterloo, Ontario) · Zbl 0493.68054
[5] Culik, K.; Opatrny, J., Macro OL systems, Internat. J. Comput. Math., 4, 327-342 (1975) · Zbl 0309.68064
[6] Rozenberg, G.; Salomaa, A., The Mathematical Theory of L Systems (1980), Academic Press: Academic Press New York · Zbl 0365.68072
[7] Salomaa, A.; Soittola, M., Automata-Theoretic Aspects of Formal Power Series (1978), Springer: Springer Berlin · Zbl 0377.68039
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.