On a family of L languages resulting from systolic tree automata
type: Item
instance of: scholarly article
title: On a family of L languages resulting from systolic tree automata
zbMATH Open document ID: 0549.68081
DOI: 10.1016/0304-3975(83)90032-4
published in: Theoretical Computer Science
publication date: 1983-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3876635
zbMATH Keywords: BT-VLSI languages
zbMATH Keywords: systolic tree automata
zbMATH Keywords: EOL language
zbMATH Keywords: emptiness problem
zbMATH Keywords: formal power series
author: Karel II Culik
author: Jozef Gruska
author: Arto Salomaa
reviewed by: Markus Kunze
MaRDI profile type: Publication
full work available at URL: 0304-3975(83)90032-4
OpenAlex ID: W2081564114
cites work: On some families of languages related to developmental systems
cites work: Systolic trellis automatat†
cites work: Systolic automata for VLSI on balanced trees
cites work: Q4068111
cites work: Q4140407
cites work: Q4155837
description: scientific article; zbMATH DE number 3876635