On the expressive power of monadic least fixed point logic

DOI10.1016/J.TCS.2005.10.025zbMATH Open1086.68049OpenAlexW1560572178MaRDI QIDQ817849FDOQ817849

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

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

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)

Cites Work

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

Cited In (8)

• A logical description of priority separable games
• Counting on CTL\(^*\): On the expressive power of monadic path logic
• Title not available (Why is that?)
• Automata, Languages and Programming
• Extensions of MSO and the monadic counting hierarchy
• Title not available (Why is that?)
• Comparing the succinctness of monadic query languages over finite trees
• Mathematical Foundations of Computer Science 2005

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)