Fixed point characterization of infinite behavior of finite-state systems

DOI10.1016/S0304-3975(97)00039-XzbMath0893.68102MaRDI QIDQ1389678

Damian Niwinski

Publication date: 30 June 1998

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

zbMATH Keywords

fixed pointspowerset algebrasRabin automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (19)

ON MODAL μ-CALCULUS OVER FINITE GRAPHS WITH SMALL COMPONENTS OR SMALL TREE WIDTH ⋮ Equivalence of probabilistic \(\mu\)-calculus and p-automata ⋮ A fixpoint approach to finite delay and fairness ⋮ On temporal logic versus Datalog ⋮ The complexity of stochastic Müller games ⋮ Unnamed Item ⋮ Deciding low levels of tree-automata hierarchy ⋮ Ambiguous classes in \(\mu\)-calculi hierarchies ⋮ On modal \(\mu\)-calculus and non-well-founded set theory ⋮ Automata and fixed point logic: a coalgebraic perspective ⋮ Theμ-calculus alternation-depth hierarchy is strict on binary trees ⋮ Fixpoint alternation: arithmetic, transition systems, and the binary tree ⋮ On Distributive Fixed-Point Expressions ⋮ The alternation hierarchy in fixpoint logic with chop is strict too ⋮ Free \(\mu\)-lattices ⋮ Domain mu-calculus ⋮ Fixpoints, games and the difference hierarchy ⋮ Pushdown processes: Games and model-checking ⋮ Modular Games for Coalgebraic Fixed Point Logics

Cites Work

• Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and Safra
• Results on the propositional \(\mu\)-calculus
• Alternating automata with start formulas
• The greatest fixed-points and rational omega-tree languages
• Automata-theoretic techniques for modal logics of programs
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• Alternating automata on infinite trees
• An automata theoretic decision procedure for the propositional mu- calculus
• Set theory. With an introduction to descriptive set theory. Translation of the original Polish edition. 2nd, completely revised ed
• The computational complexity of logical theories
• The modal mu-calculus alternation hierarchy is strict
• Infinite games played on finite graphs
• Completeness of Kozen's axiomatisation of the propositional \(\mu\)-calculus.
• A lattice-theoretical fixpoint theorem and its applications
• Automata for the modal μ-calculus and related results
• Fixed-point characterization of context-free ∞-languages
• On ω-regular sets
• On the synthesis of strategies in infinite games
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Fixed point characterization of infinite behavior of finite-state systems