Straight-line program length as a parameter for complexity analysis

DOI10.1016/0022-0000(80)90024-0zbMath0458.68008OpenAlexW2093439469MaRDI QIDQ1151750

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

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

Related Items (7)

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

Cites Work

• Unnamed Item
• Unnamed Item
• The metamathematics of algebraic systems. Collected papers: 1936-1967. Translated, edited, and provided with supplementary notes by Benjamin Franklin Wells III
• A difference in expressive power between flowcharts and recursion schemes
• Relative complexity of operations on numeric and bit-string algebras
• Abstract data types and software validation
• Straight-line program length as a parameter for complexity measures
• Computable Algebra, General Theory and Theory of Computable Fields
• Hierarchies of Computable groups and the word problem
• On Finitely Generated Subgroups of a Free Group

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