The parallel complexity of two problems on concurrency
type: Item
instance of: scholarly article
title: The parallel complexity of two problems on concurrency
zbMATH Open document ID: 0734.68044
DOI: 10.1016/0020-0190(91)90224-6
published in: Information Processing Letters
publication date: 1991-01-01T00:00:00Z
review text: It is shown that unbounded fan-in circuits can solve the following two problems in constant time: The membership problem for firing sequences of Petri nets and the trace equivalence for partially commutative monoids. It is proved in addition that neither problem can be solved in constant time by a PRAM with a polynomial number of processors.
reviewed by: Matthias Jantzen
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68Q85
zbMATH DE Number: 4215361
zbMATH Keywords: Trace equivalence
zbMATH Keywords: boolean circuits
zbMATH Keywords: threshold gates
zbMATH Keywords: Petri nets
zbMATH Keywords: partially commutative monoids
zbMATH Keywords: PRAM
author: Carme Àlvarez
author: Joaquim Gabarró
MaRDI profile type: Publication
full work available at URL: 0020-0190(91)90224-6
OpenAlex ID: W2002701849
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: On the relative complexity of some languages in \(NC^ 1\)
cites work: On uniformity within \(NC^ 1\)
cites work: Constant Depth Reducibility
cites work: Q3736919
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Q3992991
cites work: \(\varepsilon\)-productions in context-free grammars
cites work: Expressibility and Parallel Complexity
cites work: Q4385522
cites work: Q4733400
cites work: Q3484350
cites work: Q3911403
cites work: Simulation of Parallel Random Access Machines by Circuits
description: scientific article; zbMATH DE number 4215361