Expressibility and Parallel Complexity

Name: Expressibility and Parallel Complexity
Creator: Neil Immerman
Keywords: 0202 electrical engineering, electronic engineering, information engineering, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences

Neil Immerman

Found an issue? Give us feedback

SIAM Journal on Comp...arrow_drop_down

SIAM Journal on Computing

Article . 1989 . Peer-reviewed

Data sources: Crossref

DBLP

Article

Data sources: DBLP

https://dx.doi.org/10.1137/021...

Article

Data sources: Microsoft Academic Graph

Expressibility and Parallel Complexity

descriptionPublicationkeyboard_double_arrow_right Article 01 Jun 1989 English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Computing, volume 18, pages 625-638 (issn: 0097-5397, eissn: 1095-7111,

Copyright policy )

Authors: Neil Immerman;

doi: 10.1137/0218043

Expressibility and Parallel Complexity

- Summary
- Related research
  (10)
- Metrics

Abstract

It is shown that the time needed by a concurrent-read, concurrent-write parallel random access machine (CRAM) to check if an input has a certain property is the same as the minimal depth of a first...

Related Organizations

Yale University
United States

10 Research products, page 1 of 1

Sorting roughly sorted sequences in parallel
1990IsAmongTopNSimilarDocuments
Top-Bottom Routing around a Rectangle is as Easy as Computing Prefix Minima
1994IsAmongTopNSimilarDocuments
A fast parallel quicksort algorithm
1989IsAmongTopNSimilarDocuments
An Optimal O(log log n) Time Parallel Algorithm for Detecting all Squares in a String
1995IsAmongTopNSimilarDocuments
On the power of concurrent-write PRAMs with read-only memory
1989IsAmongTopNSimilarDocuments
New lower bounds for parallel computation
1986IsAmongTopNSimilarDocuments
Efficient simulations between concurrent-read concurrent-write pram models
2005IsAmongTopNSimilarDocuments
Transforming comparison model lower bounds to the parallel-random-access-machine
1997IsAmongTopNSimilarDocuments
Asynchronous PRAMs are (almost) as good as synchronous PRAMs
2002IsAmongTopNSimilarDocuments
Parallel recognition algorithms for chordal_planar graphs and planar k-trees
2005IsAmongTopNSimilarDocuments

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	86
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%