A characterization of time complexity by simple loop programs

DOI10.1016/0022-0000(80)90001-XMaRDI QIDQ1137991zbMATH OpenFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3716758 (Why is no real title available?)
• scientific article; zbMATH DE number 3598447 (Why is no real title available?)
• scientific article; zbMATH DE number 3355016 (Why is no real title available?)
• Computational complexity of multitape Turing machines and random access machines
• Even Simple Programs Are Hard To Analyze
• Time bounded random access machines

Cited in

(5)

• Monadic logic programs and functional complexity
• On the edge of decidability in complexity analysis of loop programs
• scientific article; zbMATH DE number 7471667 (Why is no real title available?)
• scientific article; zbMATH DE number 7215283 (Why is no real title available?)
• Simple programming languages and restricted classes of Turing machines

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1137991)