scientific article; zbMATH DE number 1342206

zbMath0934.03054MaRDI QIDQ4263790

Thomas Schwentick

Publication date: 25 April 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

linear time complexity classesnon-expressibilitysublogics of existential second-order logic

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (2)

Existential monadic second order logic on random rooted trees ⋮ On the expressive power of monadic least fixed point logic

This page was built for publication: