Relative complexity of operations on numeric and bit-string algebras

DOI10.1007/BF01744295MaRDI QIDQ3923596zbMATHFDO

Authors Edward K. Blum, Nancy Lynch

Publication date 1980

Published in Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

polynomial timepartial recursive functionflowchartreducibility relationcomputing power of various algebrasrecursive power

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Applications of computability and recursion theory (03D80)

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A difference in expressive power between flowcharts and recursion schemes
• Real-Time Simulation of Multihead Tape Units
• Relative complexity of algebras
• Straight-line program length as a parameter for complexity measures

Cited in

(4)

• Relative complexity of algebras
• Necessary and sufficient conditions for the universality of programming formalisms
• THICKET DENSITY
• Straight-line program length as a parameter for complexity analysis

This page was built for publication: Relative complexity of operations on numeric and bit-string algebras

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