International Journal of Foundations of Computer Science

This paper provides a short guided tour through the world of pairing functions—bijections between and —as models for computational "situations." After a short discussion of the computationally simplest pairing functions—the Cauchy-Cantor "diagonal" polynomials—we describe in detail two specific computational situations where pairing functions give an unexpectedly simple handle on apparently complex systems-related problems. (1) We discuss the use of pairing functions as storage mappings for rectangular arrays/tables that are extendible, in the sense that the programmer may expand and shrink them dynamically. (2) We discuss the use of pairing functions as the basis for a mechanism for instilling accountability into Web-computing projects, by linking remote "volunteers" to the tasks they compute.

The last thirty years have seen tremendous growth in research in mobile telecommunications. However, interest in mobile computing, which includes mobile telephony and more, has increased over the last ten years. Nevertheless, most of the research on mobile computing addresses the "engineering" issues and the electronic componentary required for building mobile systems. On the other hand, algorithmics research in mobile computing is still in its infancy, and only dates back to few years. The elegance and terseness that exist today in algorithmics, especially parallel computing algorirthmics, can be brought to bear on research on "mobile computing algorithmics". However, mobility brings to the stage a whole gamut of new problems that needs to be addressed in order to develop new and efficient parallel algorithms that can be used to solve mobile computing problems.

Stencil codes such as the Jacobi, Gauß-Seidel, and red-black Gauß-Seidel kernels are among the most time-consuming routines in many scientific and engineering applications. The performance of these codes critically depends on an efficient usage of caches, and can be improved by tiling. Several tiling schemes have been suggested in the literature; this paper gives an overview and comparison. Then, in the main part, we prove a lower bound on the number of cold and capacity misses. Finally, we analyze a particular tiling scheme, and show that it is off the lower bound by a factor of at most ten. Our results show up limitations to the speedup that can be gained by future research.

Clusters of symmetric multiprocessor nodes (SMP clusters) are one of the most important parallel architectures at the moment. The architecture consists of shared-memory nodes with multiple processors and a fast interconnection network between the nodes. New programming models try to exploit this architecture by using threads in the nodes and using message-passing-libraries for inter-node communication. In order to develop efficient algorithms, it is necessary to consider the hybrid nature of the architecture and of the programming models. We present the κNUMA-model and a methodology that build a good base for designing efficient algorithms for SMP clusters. The κNUMA-model is a computational model that extends the bulk-synchronous parallel (BSP) model with the characteristics of SMP clusters and new hybrid programming models. The κNUMA-methodology suggests to develop efficient overall algorithms by developing efficient algorithms for each level in the hierarchy. We use the problem of personalized one-to-all-broadcast and the dense matrix-vector-multiplication for the presentation. The theoretical results of the analysis of the dense matrix-vector-multiplication are verified practically. We show results of experiments, made on a Linux-cluster of dual Pentium-III nodes.

The computational model on which the algorithms are developed is the array with reconfigurable optical buses (AROB). It integrates the advantages of both optical transmission and electronic computation. The main contributions of this paper are in designing several optimal and/or optimal speed-up template matching algorithms with varying degrees of parallelism on the AROB model. For an N × N digitized image and an M × M template, when the domains of the image and the template are O(log N)-bit integers, we first design several basic operations for window broadcasting and rotation. Then based on these basic operations, three efficient and scalable algorithms for template matching are derived using various numbers of processors on a two-dimensional (2-D) or 3-D AROB. For 1 ≤ r ≤ N, 1 ≤ p ≤ M ≤ q ≤ N, one runs in time using r × r processors, another runs in , (resp. ) time using pN × pN/log M (resp. pN × pN × log N) processors, and the other runs in (resp. ) time using pq × pq/log M (or pq × pqN × log N) processors, respectively. The latter two algorithms can be tuned to run in O(1) time on a 2-D AROB. To the best of our knowledge, there are no algorithms which can reach this time complexity for this problem on a 2-D array architecture.

The problem of merging two intransitive sorted sequences (that is, to generate a sorted total order without the transitive property) is considered. A cost-optimal parallel merging algorithm is proposed under the EREW PRAM model. This algorithm has a run time of O(log² n) using O(n/log² n) processors. The cost-optimal merge in the strong sense is still an open problem.

In [7] was introduced a new decomposition scheme for bipartite graphs that was called canonical decomposition. Weak-bisplit graphs are totally decomposable following this decomposition. We give here linear time algorithms for the recognition of weak-bisplit graphs as well as for two subclasses of this class, the P₆-free bipartite graphs and the bi-cographs. Our algorithms extends the technics developped in [2] for cographs's recognition. We conclude by presenting efficient solutions for some optimization problems when dealing with weak-bisplit graphs.

This paper deals with two kinds of generalized hypercubes: a d-dimensional c-ary clique and a d-dimensional c-ary array . A d-dimensional c-ary clique has nodes labeled by c^d integers from 0 to c^d - 1 and two nodes are connected by an edge if and only if the c-ary representations of their labels differ by one and only one digit. A d-dimensional c-ary array also has nodes labeled by c^d integers from 0 to c^d - 1, and two nodes are connected if and only if the c-ary representations of their labels differ by one and only one digit and the absolute value of the difference in that digit is 1. Further, an n-node c-ary clique is the induced subgraph of with nodes labeled by integers from 0 to n - 1. The main contribution of this paper is to clarify several topological properties of and in terms of their linear layouts. For this purpose, we first prove that is a maximum subgraph of , that is, has the largest number of edges over all n-node subgraphs of , whenever n ≤ m. Using this fact, we show the exact values of the bisection width, cut width, and total edge length of . We also show the exact value of the bisection width of and nearly tight values of the cut width and the total edge length of .

In this paper we define a variant of P systems, namely, probabilistic rewriting P systems, where the selection of rewriting rules is probabilistic. We show that, with non-zero cut-point, probabilistic rewriting P systems with/without priorities generate only finite languages, but with zero cut/point and without priorities, probabilistic rewriting P systems of degree 1 characterize the family of languages generated by matrix grammars. We also prove that probabilistic rewriting P systems of degree 1 with zero cut-point and priorities characterize recursively enumerable languages.