𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A characterization of Büchi tree automata

✍ Scribed by Jerzy Skurczyński

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
68 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

We show that a language of infinite binary trees is definable by a Σ 2 -formula of the monadic second order logic of two successors (with no additional symbols) iff it can be accepted by a Büchi automaton. The same result has been obtained by G. Lenzi, but our proof is simpler.

📜 SIMILAR VOLUMES

Unambiguous Büchi automata
Unambiguous Büchi automata
✍ Olivier Carton; Max Michel 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 428 KB

In this paper, we introduce a special class of B uchi automata called unambiguous. In these automata, any inÿnite word labels exactly one path going inÿnitely often through ÿnal states. The word is recognized by the automaton if this path starts in an initial state. The main result of the paper is t

A kleene-like characterization of langua
A kleene-like characterization of languages accepted by systolic tree automata
✍ E. Fachini; A. Monti 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 686 KB

We present a Kleen-like characterization of the class of languages accepted by systolic binary tree automata, L(SBTA). This characterization uses union, intersection, restricted concatenation, restricted concatenation closure, and finite substitution closure. The restrictions we impose on the operat