CHOMSKY HIERARCHY AND SYSTOLIC Y-TREE AUTOMATA

Article type: Research Article

Authors: Fachini, Emanuela | Monti, Angelo

Affiliations: D.to di Informatica, Sistemi e Produzione, Università di Roma “Tor Vergata”, Via della Ricerca Scientifica, 00133 Roma, Italy, e-mail: fachini@info.utovrm.it | D.to di Scienze dell' Informazione, Università di Roma “La Sapienza”, Via Salaria 113, 00198 Roma, Italy, e-mail: monti@dsi.uniromal.it

Abstract: We prove that no nonregular deterministic context-free language is accepted by any systolic Y-tree automaton while some of them, but not all, can be accepted by nondeterministic systolic Y-tree automata. We show that weak superstable systolic automata over incomplete Y-tree can accept only regular languages. We also show that the weak superstability and the superstability problems are decidable for deterministic systolic automata over a sparse and superprefix Y-tree. Moreover we prove that the regularity problem is decidable for systolic binary tree automata.

DOI: 10.3233/FI-1997-29402

Journal: Fundamenta Informaticae, vol. 29, no. 4, pp. 325-339, 1997