Some Structural Properties of Systolic Tree Automata

Article type: Research Article

Authors: Fachini, E.^a | Maggiolo Schettini, A.^b | Resta, G.^b | Sangiorgi, D.^b

Affiliations: [a] Dipartimento di Informatica ed Applicazioni, Università di Salerno, 84081 Baronissi, Italy | [b] Dipartimento di Informatica, Università di Pisa, 56100 Pisa, Italy

Abstract: We prove that the classes of languages accepted by systolic automata over t-ary trees (t-STA) are always either equal or incomparable if one varies t. We introduce systolic tree automata with base (T(b)-STA), a subclass of STA with interesting properties of modularity, and we give a necessary and sufficient condition for the equivalence between a T(b)-STA and a t-STA, for a given base b. Finally, we show that the stability problem for T(b)-ST A is decidible.

DOI: 10.3233/FI-1989-12409

Journal: Fundamenta Informaticae, vol. 12, no. 4, pp. 571-585, 1989