Theμ-calculus alternation-depth hierarchy is strict on binary trees

DOI10.1051/ITA:1999121MaRDI QIDQ4943546zbMATH OpenOpenAlexFDO

Authors André Arnold

Publication date 3 October 2000

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/222087

zbMATH Keywords

alternation-depth hierarchy of the \(\mu\)-calculus

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1136070
• Mu-depth 3 is more than 2: A game-theoretic proof
• scientific article; zbMATH DE number 2102739
• Fixpoint alternation: arithmetic, transition systems, and the binary tree
• The alternation hierarchy for the theory of -lattices

Cites work

• Alternating automata on infinite trees
• Alternating automata, the weak monadic theory of trees and its complexity
• Fixed point characterization of infinite behavior of finite-state systems
• Fixpoint alternation: arithmetic, transition systems, and the binary tree
• Hierarchies of weak automata and weak monadic formulas
• scientific article; zbMATH DE number 3709584 (Why is no real title available?)
• scientific article; zbMATH DE number 3790415 (Why is no real title available?)
• scientific article; zbMATH DE number 475417 (Why is no real title available?)
• scientific article; zbMATH DE number 1136070 (Why is no real title available?)
• scientific article; zbMATH DE number 2102739 (Why is no real title available?)
• scientific article; zbMATH DE number 4189200 (Why is no real title available?)
• Logical definability of fixed points
• Monadic second order logic on tree-like structures

Cited in

(33)

• On the equational definition of the least prefixed point.
• A gap property of deterministic tree languages.
• The \(\mu\)-calculus alternation depth hierarchy is infinite over finite planar graphs
• Ambiguous classes in \(\mu\)-calculi hierarchies
• \(\varSigma^{\mu}_2\) is decidable for \(\varPi^{\mu}_2\)
• On the separation question for tree languages
• Measure properties of regular sets of trees
• The alternation hierarchy in fixpoint logic with chop is strict too
• The alternation hierarchy for the theory of -lattices
• Unambiguous Büchi Is Weak
• Measure Properties of Game Tree Languages
• The mu-calculus and Model Checking
• Describing the Wadge Hierarchy for the Alternation Free Fragment of μ-Calculus (I)
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• The Descriptive Complexity of Parity Games
• The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem
• Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
• Domain mu-calculus
• On the strength of unambiguous tree automata
• The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity
• scientific article; zbMATH DE number 2102739 (Why is no real title available?)
• Deciding low levels of tree-automata hierarchy
• Monadic Second Order Logic And Its Fragments
• Fixpoint alternation: arithmetic, transition systems, and the binary tree
• On Distributive Fixed-Point Expressions
• Unambiguous languages exhaust the index hierarchy
• The arity hierarchy in the polyadic -calculus
• Alternation is strict for higher-order modal fixpoint logic
• Monoidal-closed categories of tree automata
• Index problems for game automata
• Computer Science Logic
• On the \(\mu \)-calculus over transitive and finite transitive frames
• The alternation hierarchy of the \(\mu \)-calculus over weakly transitive frames

This page was built for publication: Theμ-calculus alternation-depth hierarchy is strict on binary trees

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