scientific article

Harry R. Lewis, Christos H. Papadimitriou

Publication date: 1981

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Church's thesis Turing machines finite automata context-free languages theory of computation halting problem uncomputability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20) Classical first-order logic (03B10) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Classical propositional logic (03B05) Algorithms in computer science (68W99) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (84)

Computational complexity of optimization and crude range testing: A new approach motivated by fuzzy optimization ⋮ Cube-tilings of \(\mathbb{R}^ n\) and nonlinear codes ⋮ A general approach to avoiding two by two submatrices ⋮ Unnamed Item ⋮ On termination of one rule rewrite systems ⋮ Turing Machines for Dummies ⋮ What is the Church-Turing Thesis? ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ On simple and creative sets in NP ⋮ Solving H-horizon, stationary Markov decision problems in time proportional to log (H) ⋮ Logics of communication and change ⋮ Dominoes and the complexity of subclasses of logical theories ⋮ Finite generation of ambiguity in context-free languages ⋮ The language intersection problem for non-recursive context-free grammars ⋮ Common knowledge and update in finite environments ⋮ Computability of a map and decidability of its graph in the model of Blum, Shub and Smale ⋮ Comparisons of Parikh's condition to other conditions for context-free languages ⋮ Deciding unique decodability of bigram counts via finite automata ⋮ Fixed Structure Complexity ⋮ A heuristic approach to domino grid problem ⋮ A family of NFAs which need 2\(^{n}-\alpha\) deterministic states ⋮ The computational complexity of generating random fractals ⋮ Tile complexity of approximate squares ⋮ Complexity results for classes of quantificational formulas ⋮ On ground-confluence of term rewriting systems ⋮ A survey on the structure of approximation classes ⋮ Symmetric space-bounded computation ⋮ The modal argument for hypercomputing minds ⋮ Computation of distances for regular and context-free probabilistic languages ⋮ The Possibility of Analysis: Convergence and Proofs of Convergence ⋮ A Skolem-Mahler-Lech theorem in positive characteristic and finite automata ⋮ Computational complexity of sentences over fields ⋮ Knowledge-based proof planning ⋮ Undecidability of safety for the schematic protection model with cyclic creates ⋮ On condition/event systems with discrete state realizations ⋮ On players with a bounded number of states ⋮ Multilist layering: Complexity and applications ⋮ Commutation-augmented pregroup grammars and mildly context-sensitive languages ⋮ Finite objects in a locos ⋮ A multiparameter analysis of domino tiling with an application to concurrent systems ⋮ Pictorial reasoning with cell assemblies ⋮ A closed-form evaluation for Datalog queries with integer (gap)-order constraints ⋮ Augmented infinitesimal perturbation analysis: An alternate explanation ⋮ Minimum-complexity pairing functions ⋮ Statistical estimation with bounded memory ⋮ Multiobjective service restoration in electric distribution networks using a local search based heuristic ⋮ The emptiness of intersection problem for languages of k-valued categorial grammars (classical and Lambek) is undecidable ⋮ On the limit set of some universal cellular automata ⋮ Planar tilings by polyominoes, polyhexes, and polyiamonds ⋮ Some observations on supervisory policies that enforce liveness in partially controlled free-choice Petri nets ⋮ Deep pushdown automata ⋮ Uniquely decodable \(n\)-gram embeddings ⋮ Grid structures and undecidable constraint theories ⋮ A time bound on the materialization of some recursively defined views ⋮ Is Universal Computation a Myth? ⋮ On Computable Numbers, Nonuniversality, and the Genuine Power of Parallelism ⋮ Quantum principles and mathematical computability ⋮ Branching time controllers for discrete event systems ⋮ Unnamed Item ⋮ Turing machines with access to history ⋮ Cook reducibility is faster than Karp reducibility in NP ⋮ The end of pumping ⋮ The calculi of emergence: Computation, dynamics and induction ⋮ Lattices of local two-dimensional languages ⋮ Domino-tiling games ⋮ Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs ⋮ A one-key cryptosystem based on a finite nonlinear automaton ⋮ The computational complexity of the Lorentz lattice gas ⋮ Sentences over integral domains and their computational complexities ⋮ A low and a high hierarchy within NP ⋮ REPRESENTING DEFAULTS IN THE FRAMEWORK OF POSSIBILITY THEORY∗ ⋮ A framework to visualize equivalences between computational models of regular languages. ⋮ Cut and paste ⋮ Unnamed Item ⋮ Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization ⋮ The complexity of the satisfiability problem for Krom formulas ⋮ Minimal strings in a regular language with respect to a partial order on the alphabet ⋮ Complexity analysis of propositional concurrent programs using domino tiling ⋮ Optimizing the clausal normal form transformation ⋮ Counter machines ⋮ Inclusion dependencies and their interaction with functional dependencies ⋮ Synthesis of real time acceptors ⋮ Computation of equilibria in noncooperative games ⋮ Living with a new mathematical species

This page was built for publication: