Hierarchies of weak automata and weak monadic formulas
type: Item
instance of: scholarly article
title: Hierarchies of weak automata and weak monadic formulas
zbMATH Open document ID: 0728.68086
DOI: 10.1016/0304-3975(91)90283-8
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
review text: Given a set of trees, define its Muller index (the Rabin index, respectively) as the minimal Muller (Rabin) index of the alternating finite automata (afa) representing this set. First, it is proved that the two indices - the Muller index and the Rabin index - coincide, both in weak and in strong conditions. The main result proves that for k successor monadic arithmetics, a weak formula with a bounded suffix has m unbounded quantifiers (m\(\geq 2)\) in the prefix iff it is represented by a weak afa of index m. An infinite hierarchy of weak indices for afa is obtained in this way. See defnitions in the related papers by \textit{D. E. Muller}, \textit{P. E. Schupp} [Theor. Comput. Sci. 54, 264-276 (1987; Zbl 0636.68108) and Lect. Notes Comput. Sci. 192, 100-107 (1985; Zbl 0608.03004)].
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4203740
zbMATH Keywords: Muller index
zbMATH Keywords: alternating finite automata
zbMATH Keywords: Rabin index
author: A. Włodzimierz Mostowski
reviewed by: Gheorghe Păun
MaRDI profile type: Publication
full work available at URL: 0304-3975(91)90283-8
OpenAlex ID: W1992595180
cites work: The monadic second order theory of all countable ordinals
cites work: Q3753490
cites work: Q3787992
cites work: Q4726235
cites work: Alternating automata on infinite trees
cites work: Q5632564
cites work: Q5616162
cites work: Generalized finite automata theory with an application to a decision problem of second-order logic
cites work: Q3967525
Recommended article: Hierarchies of weakly monotone restarting automata
Recommended article: Q3787992
Recommended article: Weak equivalence of higher-dimensional automata
Recommended article: Weak morphisms of higher dimensional automata
Recommended article: Alternating automata, the weak monadic theory of trees and its complexity
Recommended article: Q4726235
Recommended article: Q2754058
Recommended article: Q3340164
Recommended article: Q4992511
description: scientific article; zbMATH DE number 4203740