On the complexity of commutativity analysis

DOI10.1007/3-540-61332-3_166MaRDI QIDQ6184677zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, Pedro C. Diniz, Martin C. Rinard

Publication date 29 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61332-3_166

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the Complexity of Commutativity Analysis
• Synthesizing precise and useful commutativity conditions
• Automatic generation of precise and useful commutativity conditions
• Commutativity and its role in the processing of linear recursion
• Decomposing data structure commutativity proofs with \(mn\)-differencing

Cites work

• A note on the complexity of program evaluation
• Commutativity-based concurrency control for abstract data types
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the complexity of simple arithmetic expressions
• On the Simplification and Equivalence Problems for Straight-Line Programs
• On the zero-inequivalence problem for loop programs
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• The Complexity of the Equivalence Problem for Simple Loop-Free Programs
• The Complexity of the Equivalence Problem for Simple Programs

This page was built for publication: On the complexity of commutativity analysis

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