In:
International Journal of Algebra and Computation, World Scientific Pub Co Pte Ltd, Vol. 03, No. 02 ( 1993-06), p. 237-250
Abstract:
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ü.
Type of Medium:
Online Resource
ISSN:
0218-1967
,
1793-6500
DOI:
10.1142/S0218196793000172
Language:
English
Publisher:
World Scientific Pub Co Pte Ltd
Publication Date:
1993
SSG:
17,1
Bookmarklink