On the expressive power of monadic least fixed point logic

DOI10.1016/J.TCS.2005.10.025MaRDI QIDQ817849zbMATH OpenOpenAlexFDO

Authors Nicole Schweikardt

Publication date 20 March 2006

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

Full work available at URL https://doi.org/10.1016/j.tcs.2005.10.025

zbMATH Keywords

finite model theorymonadic second-order logicdescriptive complexity theoryfixed point logiclinear time complexity classes

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Automata, Languages and Programming
• scientific article; zbMATH DE number 873906
• Mathematical Foundations of Computer Science 2005
• Expressive equivalence of least and inflationary fixed-point logic
• Comparing the succinctness of monadic query languages over finite trees

Cites work

• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 1342206 (Why is no real title available?)
• scientific article; zbMATH DE number 850318 (Why is no real title available?)
• A restricted second order logic for finite structures
• Arithmetic, first-order logic, and counting quantifiers
• Automata, Languages and Programming
• Comparing the succinctness of monadic query languages over finite trees
• Complexity classes and theories of finite models
• Invariance properties of RAMs and linear time
• Linear Time Algorithms and NP-Complete Problems
• Locality of order-invariant first-order formulas
• Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
• Model Checking Games
• Monadic Datalog and the expressive power of languages for web information extraction
• Monadic logical definability of nondeterministic linear time
• Nonerasing, counting, and majority over the linear time hierarchy
• Query evaluation via tree-decompositions
• Rudimentary Languages and Second‐Order Logic
• Sorting, linear time and the satisfiability problem
• The closure of monadic NP
• The modal mu-calculus alternation hierarchy is strict
• The monadic quantifier alternation hierarchy over grids and graphs
• The polynomial-time hierarchy
• The quantifier structure of sentences that characterize nondeterministic time complexity

Cited in

(8)

• Counting on CTL\(^*\): On the expressive power of monadic path logic
• Comparing the succinctness of monadic query languages over finite trees
• scientific article; zbMATH DE number 7450024 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2005
• scientific article; zbMATH DE number 1841812 (Why is no real title available?)
• Automata, Languages and Programming
• Extensions of MSO and the monadic counting hierarchy
• A logical description of priority separable games

This page was built for publication: On the expressive power of monadic least fixed point logic

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