On the expressive power of monadic least fixed point logic
From MaRDI portal
Publication:817849
DOI10.1016/j.tcs.2005.10.025zbMath1086.68049OpenAlexW1560572178MaRDI QIDQ817849
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
monadic second-order logicfixed point logicfinite model theorydescriptive complexity theorylinear time complexity classes
Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The quantifier structure of sentences that characterize nondeterministic time complexity
- The polynomial-time hierarchy
- Monadic logical definability of nondeterministic linear time
- A restricted second order logic for finite structures
- The modal mu-calculus alternation hierarchy is strict
- Invariance properties of RAMs and linear time
- The closure of monadic NP
- Sorting, linear time and the satisfiability problem
- Nonerasing, counting, and majority over the linear time hierarchy
- The monadic quantifier alternation hierarchy over grids and graphs
- Query evaluation via tree-decompositions
- Complexity classes and theories of finite models
- Linear Time Algorithms and NP-Complete Problems
- Rudimentary Languages and Second‐Order Logic
- Comparing the succinctness of monadic query languages over finite trees
- Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
- Model Checking Games
- Arithmetic, first-order logic, and counting quantifiers
- Automata, Languages and Programming
- Monadic datalog and the expressive power of languages for Web information extraction
- Locality of order-invariant first-order formulas
This page was built for publication: On the expressive power of monadic least fixed point logic
