Pages that link to "Item:Q3942945"
From MaRDI portal
The following pages link to Complexity classes and theories of finite models (Q3942945):
Displayed 26 items.
- Model-checking hierarchical structures (Q414908) (← links)
- Graph properties checkable in linear time in the number of vertices (Q596315) (← links)
- On Horn spectra (Q757356) (← links)
- On the expressive power of monadic least fixed point logic (Q817849) (← links)
- First-order spectra with one variable (Q909462) (← links)
- A uniform method for proving lower bounds on the computational complexity of logical theories (Q917543) (← links)
- Lower bound results on lengths of second-order formulas (Q1071760) (← links)
- Complete problems in the first-order predicate calculus (Q1075318) (← links)
- Circumscribing DATALOG: expressive power and complexity (Q1127538) (← links)
- Arithmetizing uniform \(NC\) (Q1176198) (← links)
- Formulas, regular languages and Boolean circuits (Q1193413) (← links)
- The quantifier structure of sentences that characterize nondeterministic time complexity (Q1198956) (← links)
- Investigation of binary spectra by explicit polynomial transformations of graphs (Q1318703) (← links)
- First-order spectra with one binary predicate (Q1350533) (← links)
- A descriptive complexity approach to the linear hierarchy. (Q1401413) (← links)
- First-order expressibility of languages with neutral letters or: The Crane Beach conjecture (Q1776372) (← links)
- Linear time and the power of one first-order universal quantifier (Q1854556) (← links)
- Arithmetical definability and computational complexity (Q1885035) (← links)
- On winning Ehrenfeucht games and monadic NP (Q1919539) (← links)
- Arity and alternation in second-order logic (Q1919768) (← links)
- An algebra and a logic for \(NC^ 1\) (Q2638772) (← links)
- On the Variable Hierarchy of First-Order Spectra (Q2957699) (← links)
- The polynomial and linear time hierarchies in V<sup>0</sup> (Q3184215) (← links)
- Universal quantifiers and time complexity of random access machines (Q3699679) (← links)
- (Q4643954) (← links)
- Regular Graphs and the Spectra of Two-Variable Logic with Counting (Q5258916) (← links)