scientific article

zbMath0569.68042MaRDI QIDQ3686043

Elaine J. Weyuker, Martin Davis

Publication date: 1983

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

zbMATH Keywords

Turing machinescomputability theorycomputable functionsgrammarspropositional calculusRegular languagesProcessesContext-free languagesunsolvable problemsPost's problemProgramsPolynomial-time computabilityAbstract complexityCalculations on stringsContext-sensitive languagesDegrees of unsolvabilityLoop programsPrimitive recursive functionsQuantification theory

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) Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Recursive functions and relations, subrecursive hierarchies (03D20) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items

Computing queries with higher-order logics, Small universal Turing machines, On the decidability of open logic, Elementary functions and loop programs, Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals, Collapsing degrees, Optimizing propositional calculus formulas with regard to questions of deducibility, Non-perturbative graph languages, halting problem and complexity, Parikh-reducing Church-Rosser representations for some classes of regular languages, The Banach fixed point theorem in fuzzy quasi-metric spaces with application to the domain of words, Conditional semi-Thue systems for presenting monoids, The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups, Retracted: Universal computation is `almost surely' chaotic, Verification-Led Smart Contracts, Distributed dynamic mobile multicast, Arrow's theorem, countably many agents, and more visible invisible dictators, Computable preference and utility, My Life as a Logician, The expressiveness of a family of finite set languages, Training digraphs, Secure multiparty computation of solid geometric problems and their applications, Simulating Turing machines on Maurer machines, On the expressibility and the computability of untyped queries, Murg term rewrite systems, A new approach for the execution and adjustment of a fuzzy algorithm, Model checking for process rewrite systems and a class of action-based regular properties, Unnamed Item, The origins of the halting problem, The Generalized Nagell–Ljunggren Problem: Powers with Repetitive Representations, Undecidability in Rⁿ: Riddled Basins, the KAM Tori, and the Stability of the Solar System, On the computational power of context-free PC grammar systems, The Boolean satisfiability problem in Clifford algebra, Cellular telephone networks and random maps in hypergraphs, Congruential complements of ground term rewrite systems, Higher type recursion, ramification and polynomial time, The Smyth Completion