A characterization of time complexity by simple loop programs

DOI10.1016/0022-0000(80)90001-XzbMath0431.03027MaRDI QIDQ1137991

Takumi Kasai, Akeo Adachi

Publication date: 1980

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

time complexityprimitive recursive functionslanguage recognitionexponential time computationsKalmar's elementary functionsloop programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (5)

Monadic logic programs and functional complexity ⋮ Unnamed Item ⋮ ON THE EDGE OF DECIDABILITY IN COMPLEXITY ANALYSIS OF LOOP PROGRAMS ⋮ Unnamed Item ⋮ Simple programming languages and restricted classes of Turing machines

Cites Work

• Computational complexity of multitape Turing machines and random access machines
• Time bounded random access machines
• Even Simple Programs Are Hard To Analyze
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A characterization of time complexity by simple loop programs