On a family of L languages resulting from systolic tree automata (Q800102)

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.