Theory of computation.
CompletenessComplexity classesComputational difficulty of problemsHierarchiesLower boundsModels of computationTextbookTheory of computingTuring machines
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) General topics in the theory of computing (68Q01) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
- Theory of computation.
- scientific article; zbMATH DE number 2062344
- Theory of computation
- scientific article; zbMATH DE number 194974
- scientific article; zbMATH DE number 6164359
- scientific article; zbMATH DE number 1052322
- Computability and complexity theory.
- scientific article; zbMATH DE number 5595162
- Computability theory
- Computability theory
- Complexity and decidability
- Document spanners: from expressive power to decision problems
- Solving quantified linear arithmetic by counterexample-guided instantiation
- On the complexity of the quantified bit-vector arithmetic with binary encoding
- On low for speed oracles
- A game-semantic model of computation
- Parameterized resiliency problems
- On the complexity of two-dimensional signed majority cellular automata
- Games for query inseparability of description logic knowledge bases
- Basic complexity
- On low for speed oracles
- Upper Bounds on the Automata Size for Integer and Mixed Real and Integer Linear Arithmetic (Extended Abstract)
- Inhabitation of Low-Rank Intersection Types
- Ontologies and Databases: The DL-Lite Approach
- Model Checking FO(R) over One-Counter Processes and beyond
- scientific article; zbMATH DE number 4090803 (Why is no real title available?)
- Expressiveness and static analysis of extended conjunctive regular path queries
- scientific article; zbMATH DE number 1542049 (Why is no real title available?)
- Infinitude of primes using formal languages
- scientific article; zbMATH DE number 6164359 (Why is no real title available?)
- Hardness of conjugacy, embedding and factorization of multidimensional subshifts
- Adding Guarded Constructions to the Syllogistic
- How hard is positive quantification?
- Metric structures and probabilistic computation
- On pure space vs catalytic space
- Least and greatest solutions of equations over sets of integers
- On pure space vs catalytic space
- The domino problem is undecidable on every rhombus subshift
- Quantifier elimination for counting extensions of Presburger arithmetic
- Logic-based ontology comparison and module extraction, with an application to DL-Lite
- From GTC to \textsc{Reset}: generating reset proof systems from cyclic proof systems
- Minimisation in logical form
- Reasoning on data words over numeric domains
- Geometric decision procedures and the VC dimension of linear arithmetic theories
- Kolmogorov's Calculus of Problems and its Legacy
- Being polite is not enough (and other limits of theory combination)
- Alternating Turing machines and the analytical hierarchy
- Identifying tractable quantified temporal constraints within Ord-Horn
- Ehrenfeucht-Fraïssé goes automatic for real addition
- An introduction to the theory of linear integer arithmetic (invited paper)
- Deciding Boolean algebra with Presburger arithmetic
This page was built for publication: Theory of computation.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2492014)
