✦ LIBER ✦

A kleene-like characterization of languages accepted by systolic tree automata

✍ Scribed by E. Fachini; A. Monti

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 686 KB
Volume: 49
Category: Article
ISSN: 0022-0000
DOI: 10.1016/s0022-0000(05)80090-x

No coin nor oath required. For personal study only.

✦ Synopsis

We present a Kleen-like characterization of the class of languages accepted by systolic binary tree automata, L(SBTA). This characterization uses union, intersection, restricted concatenation, restricted concatenation closure, and finite substitution closure. The restrictions we impose on the operator of concatenation are purely in terms of the length of the words to be concatenated.