Complexity and decidability

zbMath0787.03030MaRDI QIDQ1308646

Patrick Dehornoy

Publication date: 24 November 1993

Published in: Mathématiques \& Applications (Berlin) (Search for Journal in Brave)

zbMATH Keywords

algorithmsTuring machinesarithmeticdecidabilitycomplexity theoryrecursive functionsBoolean calculusfirst- order logic

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)

Related Items (1)

A single-copy minimal-time simulation of a torus of automata by a ring of automata

This page was built for publication: Complexity and decidability