The average case complexity of the parallel prefix problem

DOI10.1007/3-540-58201-0_101zbMath1422.68117OpenAlexW1635542106MaRDI QIDQ4632459

Christian Schindelhauer, Stephan Weis, Andreas Jakoby, K. Ruediger Reischuk

Publication date: 29 April 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58201-0_101

zbMATH Keywords

finite automatonaverage casereachability problemaverage delayinput gate

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (2)

Improving the average delay of sorting ⋮ Malign distributions for average case circuit complexity.

Cites Work

• Probabilistic parallel prefix computation
• Circuit complexity
• Characterization of Associative Operations with Prefix Circuits of Constant Depth and Linear Size
• Depth-size trade-offs for parallel prefix computation
• Parallel Prefix Computation
• Size-time complexity of Boolean networks for prefix computations

This page was built for publication: The average case complexity of the parallel prefix problem