Systolic tree ω-languages: the operational and the logical view

✍ Scribed by Angelo Monti; Adriano Peron

• Book ID: 104326383
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 187 KB
• Volume: 233
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(97)00257-0

✦ Synopsis

The class of !-languages recognized by systolic (binary) tree automata is introduced. This class extends the class of B uchi !-languages though maintaining the closure under union, intersection and complement and the decidability of emptiness. The class of systolic tree !-languages is characterized in terms of a (suitable) concatenation of (ÿnitary) systolic tree languages. A generalization of B uchi Theorem is provided which establishes a correspondence between systolic tree !-languages and a suitable extension of the sequential calculus S1S.