Fixpoint alternation: arithmetic, transition systems, and the binary tree

DOI10.1051/ITA:1999122MaRDI QIDQ4943547zbMATH OpenOpenAlexFDO

Authors Julian Bradfield

Publication date 16 March 2000

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

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

zbMATH Keywords

modal mu-calculus alternation hierarchy

Mathematics Subject Classification ID

Hierarchies of computability and definability (03D55) Inductive definability (03D70) Applications of computability and recursion theory (03D80) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Theμ-calculus alternation-depth hierarchy is strict on binary trees
• scientific article; zbMATH DE number 1136070
• Strictness of the Modal μ-Calculus Hierarchy
• The alternation hierarchy in fixpoint logic with chop is strict too
• The modal mu-calculus alternation hierarchy is strict

Cites work

• μ-definable sets of integers
• Automata for the modal -calculus and related results
• Fixed point characterization of infinite behavior of finite-state systems
• scientific article; zbMATH DE number 51556 (Why is no real title available?)
• scientific article; zbMATH DE number 52748 (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?)
• On the expressivity of the modal mu-calculus
• Results on the propositional \(\mu\)-calculus
• The modal mu-calculus alternation hierarchy is strict
• Theμ-calculus alternation-depth hierarchy is strict on binary trees

Cited in

(9)

• On temporal logic versus Datalog
• On the universal and existential fragments of the \(\mu\)-calculus
• The alternation hierarchy in fixpoint logic with chop is strict too
• The descriptive complexity of modal model-checking games
• Inf-datalog, Modal Logic and Complexities
• The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity
• Deciding low levels of tree-automata hierarchy
• Theμ-calculus alternation-depth hierarchy is strict on binary trees
• The arity hierarchy in the polyadic -calculus

This page was built for publication: Fixpoint alternation: arithmetic, transition systems, and the binary tree

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