On the expressive power of monadic least fixed point logic
type: Item
instance of: scholarly article
title: On the expressive power of monadic least fixed point logic
zbMATH Open document ID: 1086.68049
author: Nicole Schweikardt
published in: Theoretical Computer Science
publication date: 2006-03-20T00:00:00Z
Mathematics Subject Classification ID: 68Q19
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5013343
zbMATH Keywords: finite model theory
zbMATH Keywords: descriptive complexity theory
zbMATH Keywords: fixed point logic
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: linear time complexity classes
MaRDI profile type: Publication
full work available at URL: j.tcs.2005.10.025
OpenAlex ID: W1560572178
cites work: The closure of monadic NP
cites work: The modal mu-calculus alternation hierarchy is strict
cites work: A restricted second order logic for finite structures
cites work: Nonerasing, counting, and majority over the linear time hierarchy
cites work: Q4255575
cites work: Query evaluation via tree-decompositions
cites work: Monadic datalog and the expressive power of languages for Web information extraction
cites work: Model Checking Games
cites work: Invariance properties of RAMs and linear time
cites work: Linear Time Algorithms and NP-Complete Problems
cites work: Sorting, linear time and the satisfiability problem
cites work: Monadic logical definability of nondeterministic linear time
cites work: Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
cites work: Q4866342
cites work: Comparing the succinctness of monadic query languages over finite trees
cites work: Locality of order-invariant first-order formulas
cites work: Q4227581
cites work: Complexity classes and theories of finite models
cites work: The quantifier structure of sentences that characterize nondeterministic time complexity
cites work: The monadic quantifier alternation hierarchy over grids and graphs
cites work: Rudimentary Languages and Second‐Order Logic
cites work: Arithmetic, first-order logic, and counting quantifiers
cites work: Automata, Languages and Programming
cites work: Q4263790
cites work: The polynomial-time hierarchy
DOI: 10.1016/J.TCS.2005.10.025
description: scientific article; zbMATH DE number 5013343