Abstract The computationally hard problem of finite language decomposition is investigated. A finite language L is decomposable if there are two languages L1 and L2 such that L = L1L2. Otherwise, L is prime. The main contribution of the paper is an adaptive parallel algorithm for finding all decompositions L1L2 of L. The algorithm is based on an exhaustive search and incorporates several original methods for pruning the search space. Moreover, the algorithm is adaptive since it changes its behavior based on the runtime acquired data related to its performance. Comprehensive computational experiments on more than 4000 benchmark languages generated over alphabets of various sizes have been carried out. The experiments showed that by using the power of parallel computing the decompositions of languages containing more than 200000 words can be found. Decompositions of languages of that size have not been reported in the literature so far.

The goal of this paper is to develop the parallel algorithms that, on input of a learning sample, identify a regular language by means of a nondeterministic finite automaton (NFA). A sample is a pair of finite sets containing positive and negative examples. Given a sample, a minimal NFA that represents the target regular language is sought. We define the task of finding an NFA, which accepts all positive examples and rejects all negative ones, as a constraint satisfaction problem, and then propose the parallel algorithms to solve the problem. The results of comprehensive computational experiments on the variety of inference tasks are reported. The question of minimizing an NFA consistent with a learning sample is computationally hard.

The goal of this paper is to develop a parallel algorithm that, on input of a learning sample, identifies a regular language by means of a nondeterministic finite automaton (NFA). A sample is a pair of finite sets containing positive and negative examples. Given a sample, a minimal NFA or the range of possible sizes of such an NFA, that represents the target regular language is sought. We define the task of finding an NFA, which accepts all positive examples and rejects all negative ones, as a constraint satisfaction problem, and then propose a parallel algorithm to solve the problem. The results of computational experiments on the variety of test samples are reported.

The work concerns the statistical measures of a fitness landscape in the context of the vehicle routing problem with time windows (VRPTW). The measures are determined by using a parallel simulated annealing algorithm as a tool for exploring a solution space. The landscape properties which are discovered allow us to evaluate the difficulty of the VRPTW benchmarking instances and to establish some parameters of the parallel algorithm.

A parallel simulated annealing algorithm for solving the vehicle routing problem with time windows (VRPTW) is considered. The VRPTW is a complex bicriterion optimization problem in which both the number of vehicles and the total distance traveled by vehicles should be minimized. The aim is to establish how the number of the cooling stages executed by parallel simulated annealing processes influence the quality of solutions to the problem.

The idea of quasi-perfect hashing is introduced and applied to solve the static dictionary problem. Given a universe U and a set S of n distinct keys belonging to U, we propose a quasi-perfect hash function which allows one to find a key from S, stored in the hash table of size m, m ≤ n, in O(1) time. While looking up a key at most two probes in the hash table are made. Our main motivation is to minimize the memory requirement for representing the hashing scheme, retaining a high probability of finding quasi-perfect hash functions for arbitrary sets S. If we compare the method of quasi-perfect hashing to Fredman, Komlós and Szemerédi's two-level hashing for the bounded universe U, we find that it is superior with regard to both space and speed.

The parallel random access machine (PRAM) is the most commonly used general-purpose machine model for describing parallel computations. Unfortunately the PRAM model is not physically realizable, since on large machines a parallel shared memory access can only be accomplished at the cost of a significant time delay. A number of PRAM simulation algorithms are known. The algorithms allow execution of PRAM programs on more realistic parallel machines. We study the randomized simulation of an exclusive read, exclusive write (EREW) PRAM on a module parallel computer (MPC). The simulation is based on utilizing universal hashing. The optimally efficient simulation involving parallel slackness is also investigated. The results of our experiments performed on the MPC built upon IMS T9000 transputers throw some light on the question whether using the PRAM model in parallel computations is practically viable given the present state of transputer technology.

Minimal perfect hash functions are used for memory efficient storage and fast retrieval of items from static sets. We present an infinite family of efficient and practical algorithms for generating order preserving minimal perfect hash functions. We show that almost all members of the family construct space and time optimal order preserving minimal perfect hash functions, and we identify the one with minimum constants. Members of the family generate a hash function in two steps. First a special kind of function into an r-graph is computed probabilistically. Then this function is refined deterministically to a minimal perfect has function. We give strong theoretical evidence that the first step uses linear random time. The second step runs in linear deterministic time. The family not only has theoretical importance, but also offers the fastest known methods for generating perfect hash functions.

A new algorithm for finding minimal perfect hash functions (MPHF) is proposed. The algorithm given three pseudorandom functions, h0, h1 and h2, searches for a function g such that F(w)=(h0(w)+(h1(w))+g(h2(w)) mod m is a MPHF, where m is a number of input words. The algorithm involves generation of random bipartite graphs and runs in linear time. The hash function generated is represented by using 2m+O(1) memory words of log m bits each. The empirical observations show that the algorithm runs very fast in practice.

Two algorithms for solving the problem of detecting undefined (or uninitialised) variables during compilation are considered. The first, well-known algorithm solves the problem by computing the use-definition chains for a program flow graph. Its time complexity is O(|N|2) where |N| is a number of nodes of the flow graph. An O(|N|) algorithm is proposed that analyses the direct acyclic graph of a reducible flow graph. The implementation of both algorithms in an Ada compiler are evaluated and compared. The number of programming languages in use today is very large … The number of high-quality language implementations, however, is quite small. – W. A. Wulf26