Straight-line program length as a parameter for complexity measures

DOI10.1145/800133.804343zbMath1282.03021OpenAlexW1972445302MaRDI QIDQ5402552

Nancy A. 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)

Related Items

Straight-line program length as a parameter for complexity analysis, Complexity of algebraic implementations for abstract data types, Accessibility of values as a determinant of relative complexity in algebras, Relative complexity of operations on numeric and bit-string algebras, Relative complexity of algebras