Intuitionistic formal theories with realizability in subrecursive classes

DOI10.1016/S0168-0072(97)00002-XzbMath0895.03017MaRDI QIDQ1377631

Anatoly Petrivich Beltiukov

Publication date: 14 September 1998

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

inductionTuring machinepolynomial timeintuitionistic theoriescomputable functionKalmar elementary functionsGrzegorczyk classrelationships between formal theories and complexity classesstrings over finite alphabets

Mathematics Subject Classification ID

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)

Related Items

A strong induction scheme that leads to polynomially computable realizations, A weak constructive second-order arithmetic with extraction of algorithms computable in polynomial time, Theory of computational complexity. Part 8. Transl. from the Russian

Cites Work

• On the computational power of pushdown automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item