Straight-line program length as a parameter for complexity analysis

DOI10.1016/0022-0000(80)90024-0MaRDI QIDQ1151750zbMATH OpenOpenAlexFDO

Authors Nancy Lynch

Publication date 1980

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(80)90024-0

zbMATH Keywords

algebraic complexitycomplexity-bounded group theorydata structure algorithmssize measure

Mathematics Subject Classification ID

Word problems (aspects of algebraic structures) (08A50) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A difference in expressive power between flowcharts and recursion schemes
• Abstract data types and software validation
• Computable Algebra, General Theory and Theory of Computable Fields
• Hierarchies of Computable groups and the word problem
• scientific article; zbMATH DE number 3430636 (Why is no real title available?)
• scientific article; zbMATH DE number 3430637 (Why is no real title available?)
• On Finitely Generated Subgroups of a Free Group
• Relative complexity of operations on numeric and bit-string algebras
• Straight-line program length as a parameter for complexity measures
• The metamathematics of algebraic systems. Collected papers: 1936-1967. Translated, edited, and provided with supplementary notes by Benjamin Franklin Wells III

Cited in

(7)

• A view of computability on term algebras
• Accessibility of values as a determinant of relative complexity in algebras
• Better complexity bounds for cost register automata
• Towards factoring in \(\mathrm{SL}(2,\mathbb F_{2^n})\)
• Relative complexity of algebras
• Better complexity bounds for cost register automata
• Showcasing straight-line programs with memory via matrix Bruhat decomposition

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

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