The class of omega-languages recognized by systolic (binary) tree automata is introduced. This class extends the class of Buchi omega-languages though maintaining the closure under union, intersection and complement and the decidability of emptiness. The class of systolic tree omega-languages is characterized in terms of a (suitable) concatenation of(finitary) systolic tree languages, A generalization of Buchi Theorem is provided which establishes a correspondence between systolic tree omega-languages and a suitable extension of the sequential calculus SIS. (C) 2000 Elsevier Science B.V. All rights reserved.
Systolic tree omega-languages: the operational and the logical view / Monti, Angelo; A., Peron. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 233:(2000), pp. 1-18. [10.1016/s0304-3975(97)00257-0]
Systolic tree omega-languages: the operational and the logical view
MONTI, Angelo;
2000
Abstract
The class of omega-languages recognized by systolic (binary) tree automata is introduced. This class extends the class of Buchi omega-languages though maintaining the closure under union, intersection and complement and the decidability of emptiness. The class of systolic tree omega-languages is characterized in terms of a (suitable) concatenation of(finitary) systolic tree languages, A generalization of Buchi Theorem is provided which establishes a correspondence between systolic tree omega-languages and a suitable extension of the sequential calculus SIS. (C) 2000 Elsevier Science B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
