Straight-line program length as a parameter for complexity measures

DOI10.1145/800133.804343MaRDI QIDQ5402552zbMATH OpenOpenAlexFDO

Authors Nancy Lynch

Publication date 14 March 2014

Published in Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/800133.804343

Mathematics Subject Classification ID

Abstract data types; algebraic specification (68Q65) Complexity of computation (including implicit computational complexity) (03D15) Word problems, etc. in computability and recursion theory (03D40)

Recommendations

• On minimal-program complexity measures
• scientific article; zbMATH DE number 4049010
• scientific article; zbMATH DE number 1534573
• Unification as a complexity measure for logic programming
• scientific article; zbMATH DE number 3913694

Cited in

(7)

• scientific article; zbMATH DE number 5117088 (Why is no real title available?)
• Relative complexity of operations on numeric and bit-string algebras
• Accessibility of values as a determinant of relative complexity in algebras
• LISP program-size complexity. III
• Straight-line program length as a parameter for complexity analysis
• Complexity of algebraic implementations for abstract data types
• Relative complexity of algebras

This page was built for publication: Straight-line program length as a parameter for complexity measures

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