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


68Q45 Formal languages and automata
Full Text: DOI


[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, ()
[3] Culik, K.; Gruska, J.; Salomaa, A., Systolic Trellis automata (for VLSI), () · Zbl 0571.68042
[4] Culik, K.; Gruska, J.; Salomaa, A., Systolic automata for VLSI on balanced trees, () · 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 New York · Zbl 0365.68072
[7] Salomaa, A.; Soittola, M., Automata-theoretic aspects of formal power series, (1978), 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. 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.