Hierarchies of weak automata and weak monadic formulas

DOI10.1016/0304-3975(91)90283-8zbMATH Open0728.68086OpenAlexW1992595180MaRDI QIDQ805253FDOQ805253

Authors: A. Włodzimierz Mostowski 

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90283-8

Recommendations

• Hierarchies of weakly monotone restarting automata
• scientific article; zbMATH DE number 4051591
• Weak equivalence of higher-dimensional automata
• Weak morphisms of higher dimensional automata
• Alternating automata, the weak monadic theory of trees and its complexity
• Publication:4726235
• scientific article; zbMATH DE number 1670757
• scientific article; zbMATH DE number 3874623
• Weighted automata and monadic second order logic

zbMATH Keywords

alternating finite automataMuller indexRabin index

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Alternating automata on infinite trees
• The monadic second order theory of all countable ordinals
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (22)

• On the weak index problem for game automata
• Definable operations on weakly recognizable sets of trees
• Verification, Model Checking, and Abstract Interpretation
• Title not available (Why is that?)
• Complexity of weak acceptance conditions in tree automata.
• Axiomatising extended computation tree logic
• Computing the Rabin Index of a Parity Automaton
• Alternating automata with start formulas
• Permissive strategies: from parity games to safety games
• Theμ-calculus alternation-depth hierarchy is strict on binary trees
• A gap property of deterministic tree languages.
• Index problems for game automata
• On the separation question for tree languages
• Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
• Weak morphisms of higher dimensional automata
• Weak index versus Borel rank
• Weak equivalence of higher-dimensional automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Way to Alternating Weak Automata
• Title not available (Why is that?)
• Deciding low levels of tree-automata hierarchy

This page was built for publication: Hierarchies of weak automata and weak monadic formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q805253)