Logical definability of fixed points

DOI10.1016/0304-3975(88)90129-6MaRDI QIDQ1114673zbMATH OpenOpenAlexFDO

Authors André Arnold

Publication date 1988

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

Full work available at URL https://doi.org/10.1016/0304-3975(88)90129-6

zbMATH Keywords

\(\nu \) \(\mu\)-definabilityBüchi setfixed pointslabelled treespecial automatonsystem of equationstree automaton

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Inductive definability (03D70) Algebraic structures (08A99) Formal languages and automata (68Q45)

Review text

A class of monotonic functions is defined whose least fixed points are weakly definable in the sense of Rabin. The author uses this property to give a new proof that \(\nu\) \(\mu\)-definable sets of trees are recognized by Rabin's special automata.

Recommendations

• scientific article; zbMATH DE number 475417
• Definable fixed points in modal and temporal logics -- a survey
• scientific article; zbMATH DE number 3960988
• scientific article; zbMATH DE number 2113976
• scientific article; zbMATH DE number 4208050

Cites work

• Decidability of Second-Order Theories and Automata on Infinite Trees
• scientific article; zbMATH DE number 3960988 (Why is no real title available?)
• scientific article; zbMATH DE number 3339435 (Why is no real title available?)
• scientific article; zbMATH DE number 4189200 (Why is no real title available?)
• Results on the propositional \(\mu\)-calculus
• The greatest fixed-points and rational omega-tree languages

Cited in

(7)

• On modal mu-calculus and Büchi tree automata
• scientific article; zbMATH DE number 475417 (Why is no real title available?)
• scientific article; zbMATH DE number 1923098 (Why is no real title available?)
• scientific article; zbMATH DE number 2103277 (Why is no real title available?)
• Theμ-calculus alternation-depth hierarchy is strict on binary trees
• Evidence for Fixpoint Logic
• Characters and fixed points in provability logic

This page was built for publication: Logical definability of fixed points

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