Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: PRAM algorithms

Sortuj według:

Ogranicz wyniki do:

Fast and Efficient Parallel Coarsest Refinement

Juneam N., Kantabutra S.

Fundamenta Informaticae

2017

Vol. 150, nr 2

211--220

The process of merging two arbitrary partitions of a given finite set U of n elements is known as coarsest refinement. In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions X, Y of the set U such that X = {X1, X2, ...,Xx} and Y = {Y1, Y2, ..., Yy}, and determine a new partition Z = {Z1, Z2, ..., Zz} such that each is a common non-empty subset of some Xa ∈ X and some Yb ∈ Y and |Z| is as small as possible. This article describes a resource-efficient parallel algorithm to solve this problem. More specifically, we show that a coarsest refinement can be computed in O(t(n) + log n) parallel time using max{nlogn, p(n)} processors, where t(n) denotes the running time of a parallel stable sorting algorithm that uses p(n) processors on an EREW PRAM. This result depends on t(n) and p(n). We give a table that shows the best known time and processor complexities for a parallel stable sorting algorithm. If the parallel stable sorting algorithms by Ajtai et al., Cole, and Leighton are used, the coarsest refinement can be computed in O(log n) parallel time using n processors on an EREW PRAM. On the other hand, if the parallel stable sorting algorithm by Bahig et al. is used, the coarsest refinement can be computed in O(lognlog(nlogn)) parallel time using nlogn processors on an EREW PRAM. In addition, we show that on, a RAM machine, our parallel algorithm runs as asymptotically efficient as the fastest known sequential algorithm.

N-axioms Parallel Unification

Bellia M., Occhiuto M.E.

Fundamenta Informaticae

2003

Vol. 55, nr 2

115-128

MGUmon and MGUk-rep have a complementary role in unification in the complexity class NC . MGUmon is the upper bound of the unification classes that fall in NC and whose inputs admit an unrestricted number of repeated variables. MGUk-rep is the upper bound of the unification classes that still fall in NC but whose inputs admit an unrestricted arity on term constructors. No LogSpace reduction of the one to the other class is known. Moreover, very fast algorithms that solve the two separately are well known but no one is able to compute with both in polylog PRAM-Time. N-axioms unification extends the structure of unification inputs and brings out the notion of interleaving variable as a special repeated variable which serializes independet computations. Based on it, we define the unification class AMGUkp/h whose inputs have a fixed number of interleaving variables but admit unrestricted number of repeated variables and, at the same time, unrestricted arity for term constructors. Constructively, we prove that AMGUkp/h is in NC by introducing a new unification algorithm that works on graph contractions and solves AMGUkp/hin a polylog PRAM time of the input size. Finally, we prove that MGUmon, MGUk-rep and MGUlinear all are LogSpace reducible to AMGUkp/h. Hence, AMGUkp/h becomes the upper bound of the unification classes that are proved to be in NC .