scientific article

zbMath0593.03001MaRDI QIDQ3722466

Egon Börger

Publication date: 1985

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

zbMATH Keywords

truthsemanticscomputabilityproofarithmetic hierarchysyntaxcomplexity classescomplexity of decision problemsTheory of computationrecursivityrecursively unsolvable problemstheory of algorithmsPredicate logic

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Undecidability and degrees of sets of sentences (03D35) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Automata and formal grammars in connection with logical questions (03D05) Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15) Cut-elimination and normal-form theorems (03F05) Recursive functions and relations, subrecursive hierarchies (03D20) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithms in computer science (68W99) Hierarchies of computability and definability (03D55) Computability and recursion theory (03Dxx)

Related Items (2)

Implication of clauses is undecidable ⋮ A uniform method for proving lower bounds on the computational complexity of logical theories

This page was built for publication: