Theory of computation.
From MaRDI portal
Publication:2492014
zbMath1102.68025MaRDI QIDQ2492014
Publication date: 31 May 2006
Published in: Texts in Computer Science (Search for Journal in Brave)
Turing machines; Completeness; Complexity classes; Lower bounds; Hierarchies; Theory of computing; Models of computation; Textbook; Computational difficulty of problems
68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q01: General topics in the theory of computing
Related Items
Infinitude of Primes Using Formal Languages, Adding Guarded Constructions to the Syllogistic, How Hard Is Positive Quantification?, Least and greatest solutions of equations over sets of integers, On pure space vs catalytic space, Games for query inseparability of description logic knowledge bases, Expressiveness and static analysis of extended conjunctive regular path queries, Hardness of conjugacy, embedding and factorization of multidimensional subshifts, Metric structures and probabilistic computation, Logic-based ontology comparison and module extraction, with an application to DL-Lite, Ehrenfeucht-Fraïssé goes automatic for real addition, Deciding Boolean algebra with Presburger arithmetic, 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, 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
