Theory of computation.

zbMath1102.68025MaRDI QIDQ2492014

Dexter Kozen

Publication date: 31 May 2006

Published in: Texts in Computer Science (Search for Journal in Brave)

zbMATH Keywords

Turing machinesCompletenessComplexity classesLower boundsHierarchiesTheory of computingModels of computationTextbookComputational difficulty of problems

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of computing (68Q01)

Related Items (27)

How Hard Is Positive Quantification? ⋮ Document spanners: from expressive power to decision problems ⋮ Deciding Boolean algebra with Presburger arithmetic ⋮ On the complexity of two-dimensional signed majority cellular automata ⋮ On Low for Speed Oracles ⋮ Expressiveness and static analysis of extended conjunctive regular path queries ⋮ The domino problem is undecidable on every rhombus subshift ⋮ Solving quantified linear arithmetic by counterexample-guided instantiation ⋮ Logic-based ontology comparison and module extraction, with an application to DL-Lite ⋮ Quantifier elimination for counting extensions of Presburger arithmetic ⋮ On the complexity of the quantified bit-vector arithmetic with binary encoding ⋮ Upper Bounds on the Automata Size for Integer and Mixed Real and Integer Linear Arithmetic (Extended Abstract) ⋮ Hardness of conjugacy, embedding and factorization of multidimensional subshifts ⋮ Metric structures and probabilistic computation ⋮ On low for speed oracles ⋮ Ehrenfeucht-Fraïssé goes automatic for real addition ⋮ Infinitude of Primes Using Formal Languages ⋮ Least and greatest solutions of equations over sets of integers ⋮ On pure space vs catalytic space ⋮ Inhabitation of Low-Rank Intersection Types ⋮ Ontologies and Databases: The DL-Lite Approach ⋮ Model Checking FO(R) over One-Counter Processes and beyond ⋮ A game-semantic model of computation ⋮ Parameterized resiliency problems ⋮ On pure space vs catalytic space ⋮ Adding Guarded Constructions to the Syllogistic ⋮ Games for query inseparability of description logic knowledge bases

This page was built for publication: Theory of computation.