SUCCINCTNESS OF DESCRIPTIONS OF SBTA-LANGUAGES

Systolic binary tree automata (SBTA) provide a basic and robust model for one-way parallel computations on binary tree networks of memoryles s processors. In this paper we investigate succinctness of description s of languages accepted by SBTA, measured in terms of the number of st ates of minimal SBTA. We study the problem in different settings. Firs t we provide various criteria to determine lower bounds on the state-c omplexity of an SBTA-language L, that is bounds on the minimum number of states for an SBTA to accept L, and we show the existence of dense hierarchies of families of SBTA-languages with respect to their state- complexity, We study then how much Boolean operations can contribute t o the increase of the state-complexity of SBTA-languages and we provid e tight bounds on the complexity of languages obtained by union, inter section and complement of SBTA-languages. Finally, we consider differe nt but equiv alent models of SBTA and determine bounds on the trade-of f between the state-complexity of a language L for any two equivalent models of SBTA. Moreover, we compare the state-complexity of regular l anguages with respect to their description by deterministic finite aut omata and several types of SBTA. We conclude the paper with a brief di scussion on the minimization problem of SBTA and with some open proble ms.