Descriptive complexity, lower bounds and linear time
From MaRDI portal
Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)
Recommendations
Cited in
(19)- Succinctness as a source of complexity in logical formalisms
- Some descriptive-set-theoretical problems in complexity theory
- A descriptive complexity approach to the linear hierarchy.
- Existential monadic second order logic on random rooted trees
- Linear time and the power of one first-order universal quantifier
- Descriptive complexity of \#P functions: a new perspective
- Descriptive complexity of deterministic polylogarithmic time
- On the descriptive complexity of \(\overline{\varSigma ^*\overline{L}}\)
- Descriptive complexity of deterministic polylogarithmic time and space
- Descriptive Complexity of approximate counting CSPs
- scientific article; zbMATH DE number 4106276 (Why is no real title available?)
- scientific article; zbMATH DE number 1231505 (Why is no real title available?)
- scientific article; zbMATH DE number 1948492 (Why is no real title available?)
- Descriptive and parameterized complexity
- scientific article; zbMATH DE number 7315103 (Why is no real title available?)
- The Density of Linear-Time Properties
- The Descriptive Complexity of the Deterministic Exponential Time Hierarchy
- scientific article; zbMATH DE number 969067 (Why is no real title available?)
- On the expressive power of monadic least fixed point logic
This page was built for publication: Descriptive complexity, lower bounds and linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4263790)
