THE EFFECT OF THE NUMBER OF SUCCESSFUL PATHS IN A BÜCHI TREE AUTOMATON
Danièle Beauquier, Maurice Nivat, Damian Niwiński · International Journal of Algebra and Computation · 1993
We modify an acceptance condition of Büchi automaton on infinite trees: rather than to require that each computation path is successful, we impose various restrictions on the number of successful paths in a run of the automaton on a tree. All these modifications alter the recognizing power of Büchi automata. We examine the classes induced by the acceptance conditions that require ≤α, ≥α, =α successful paths, where α is a cardinal number. It turns out that, except for some trivial cases, the “≤” classes are incomparable with the class Bü of Büchi acceptable tree languages, while the classes “≥” are strictly included in Bü.