On proving time constructibility of functions

DOI10.1016/0304-3975(85)90015-5MaRDI QIDQ1059393zbMATH OpenOpenAlexFDO

Authors Kojiro Kobayashi

Publication date 1985

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(85)90015-5

zbMATH Keywords

Turing machinetime complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Recommendations

• Publication:4934340
• Constructible functions in cellular automata and their applications to hierarchy results
• A note on A.E. h-complex functions
• On average time hierarchies
• Strong time bounds: Non-computable bounds and a hierarchy theorem

Cites work

• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Circuit-size lower bounds and non-reducibility to sparse sets

Cited in

(6)

• Deterministic Turing machines in the range between real-time and linear-time.
• scientific article; zbMATH DE number 1390074 (Why is no real title available?)
• A note on square rooting of time functions of Turing machines
• Alternating time versus deterministic time: A separation
• scientific article; zbMATH DE number 3860251 (Why is no real title available?)
• scientific article; zbMATH DE number 3958737 (Why is no real title available?)

This page was built for publication: On proving time constructibility of functions

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