Theory of computation.
zbMATH Open1102.68025MaRDI QIDQ2492014FDOQ2492014
Publication date: 31 May 2006
Published in: Texts in Computer Science (Search for Journal in Brave)
Turing machinesCompletenessComplexity classesLower boundsHierarchiesTheory of computingModels of computationTextbookComputational difficulty of problems
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of computing (68Q01)
Cited In (32)
- Games for query inseparability of description logic knowledge bases
- On the complexity of the quantified bit-vector arithmetic with binary encoding
- Quantifier elimination for counting extensions of Presburger arithmetic
- Parameterized resiliency problems
- Logic-based ontology comparison and module extraction, with an application to DL-Lite
- Metric structures and probabilistic computation
- A game-semantic model of computation
- From GTC to \textsc{Reset}: generating reset proof systems from cyclic proof systems
- On low for speed oracles
- On pure space vs catalytic space
- On pure space vs catalytic space
- On Low for Speed Oracles
- Inhabitation of Low-Rank Intersection Types
- On the complexity of two-dimensional signed majority cellular automata
- How Hard Is Positive Quantification?
- Ehrenfeucht-Fraïssé goes automatic for real addition
- Minimisation in logical form
- Document spanners: from expressive power to decision problems
- Adding Guarded Constructions to the Syllogistic
- Model Checking FO(R) over One-Counter Processes and beyond
- Deciding Boolean algebra with Presburger arithmetic
- Ontologies and Databases: The DL-Lite Approach
- Title not available (Why is that?)
- Geometric decision procedures and the VC dimension of linear arithmetic theories
- Reasoning on data words over numeric domains
- Hardness of conjugacy, embedding and factorization of multidimensional subshifts
- Solving quantified linear arithmetic by counterexample-guided instantiation
- Upper Bounds on the Automata Size for Integer and Mixed Real and Integer Linear Arithmetic (Extended Abstract)
- Expressiveness and static analysis of extended conjunctive regular path queries
- Least and greatest solutions of equations over sets of integers
- The domino problem is undecidable on every rhombus subshift
- Infinitude of Primes Using Formal Languages
Recommendations
- Computability and complexity theory. 👍 👎
- Theory of Computation 👍 👎
- Computability theory 👍 👎
- Computability theory 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
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)
