The parallel complexity of two problems on concurrency
From MaRDI portal
Publication:811123
DOI10.1016/0020-0190(91)90224-6zbMath0734.68044OpenAlexW2002701849MaRDI QIDQ811123
Carme Àlvarez, Joaquim Gabarró
Publication date: 1991
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(91)90224-6
Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Distributed algorithms (68W15)
Related Items (3)
On the synchronization of semi-traces ⋮ Solving trace equations using lexicographical normal forms ⋮ Solving word equations modulo partial commutations
Cites Work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- On the relative complexity of some languages in \(NC^ 1\)
- \(\varepsilon\)-productions in context-free grammars
- On uniformity within \(NC^ 1\)
- Simulation of Parallel Random Access Machines by Circuits
- Parity, circuits, and the polynomial-time hierarchy
- Constant Depth Reducibility
- Expressibility and Parallel Complexity
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The parallel complexity of two problems on concurrency
