Algebras for iteration and infinite computations

We give axioms for an operation that describes iteration in various relational models of computations. The models differ in their treatment of finite, infinite and aborting executions, covering partial, total and general correctness and extensions thereof. Based on the common axioms we derive separation, refinement and program transformation results hitherto known from particular models, henceforth recognised to hold in many different models. We introduce a new model that independently describes the finite, infinite and aborting executions of a computation, and axiomatise an operation that extracts the infinite executions in this model and others. From these unifying axioms we derive explicit representations for recursion and iteration. We show that also the new model is an instance of our general theory of iteration. All results are verified in Isabelle heavily using automated theorem provers.     

Infinite vs. finite size-bounded randomized computations

Randomized computations can be very powerful with respect to space complexity, e.g., for logarithmic space, LasVegas is equivalent to nondeterminism. This power depends on the possibility of infinite computations, however, it is an open question if they are necessary. We answer this question for rotating finite automata (rfas) and sweeping finite automata (sfas). We show that LasVegas rfas (sfas) allowing infinite computations, although only with probability 0, can be exponentially smaller than LasVegas rfas (sfas) forbidding them. In particular, we show that even rfas (sfas) with linear expected running time may require exponentially more states than rfas (sfas) running in exponential time. We also strengthen this result, showing that the restriction on time cannot be traded for the more powerful bounded-error randomization. To prove our results, we introduce a technique for proving lower bounds on size of rfas (sfas) that generalizes the notion of generic strings discovered by M. Sipser.     

Infinite arrays and controlled deterministic table 0L array systems

Deterministic table 0L array systems with control are considered for the generation of infinite arrays. Rewriting of a rectangular array is done in parallel by a table of rules, the rightmost edge horizontally or the lowermost edge vertically downwards. The application of the tables is controlled by a control set. Cube-free and square-free infinite arrays are obtained as an application of this model. The adherence of the array language of a controlled deterministic table 0L array system is related to the adherence of its control set. The limit language equivalence problem and the adherence equivalence problem are shown to be undecidable for this system.     

Accelerating unstructured finite volume computations on field‐programmable gate arrays

In the paper, an field‐programmable gate array (FPGA)‐based framework is described to efficiently accelerate unstructured finite volume computations where the same mathematical expression has to be evaluated at every point of the mesh. The irregular memory access patterns caused by the unstructured spatial discretization are eliminated by a novel mesh node reordering technique, and a special architecture is designed to fully utilize the benefits of the predictable memory access patterns. In the proposed architecture, a fixed‐size moving window of the input stream of the reordered state variables is cached into the on‐chip memory and a pipelined chain of processing elements, which gets input only from the fast on‐chip memory, is used to carry out the computations. The arithmetic unit (AU) of the processing elements is generated from the data flow graph extracted from the given mathematical expression. The data flow graph is partitioned with a novel graph partitioning algorithm to break up the AU into smaller locally controlled parts, which can be more efficiently implemented in FPGA than the globally controlled AU. The proposed architecture and algorithms are presented via a case study solving the Euler equations on an unstructured mesh. On the currently available largest FPGA, the generated architecture contains three processing elements working in a pipelined fashion to provide one order of magnitude speedup compared with a high performance microprocessor and three times speedup compared with a high performance graphics processing unit. Copyright © 2013 John Wiley & Sons, Ltd.     

There is no fully abstract fixpoint semantics for non-deterministic languages with infinite computations

It is well known that for many non-deterministic programming languages there is no continuous fully abstract fixpoint semantics. This is usually attributed to “problems with continuity”, that is, the assumption that the semantic functions should be continuous supposedly plays a role in the difficulties of giving a fully abstract fixpoint semantics. We show that for a large class of non-deterministic programming languages there is no fully abstract least fixpoint semantics even if one considers arbitrary functions (not necessarily continuous) over arbitrary partial orders (not necessarily complete).     

Infinite games on finitely coloured graphs with applications to automata on infinite trees

We examine a class of infinite two-person games on finitely coloured graphs. The main aim is to construct finite memory winning strategies for both players. This problem is motivated by applications to finite automata on infinite trees. A special attention is given to the exact amount of memory needed by the players for their winning strategies. Based on a previous work of Gurevich and Harrington and on subsequent improvements of McNaughton we propose a unique framework that allows to reestablish and to improve various results concerning memoryless strategies due to Emerson and Jutla, Mostowski, Klarlund.     

Mapping computations

Let Z be a set of integers and Z ^n×n be a ring for any integer n. We define as a latter point. Hom(Z ⁿ ,Z ^m ) denotes as a homomorphism of Z ⁿ into Z ^m . For any element in Z ⁿ , we define S+T:Z ⁿ →Z ^m as . As a result, S+T become a homomorphism of Z ⁿ into Z ^m . We also define kU:Z ⁿ →Z ^m as . Consequently, kU become a homomorphism of Z ⁿ into Z ^m . Moreover, Hom (Z ⁿ ,Z ^m ) is isomorphic to Z ^n×m . A novel class of the structured matrices which is a set of elements of Hom (Z ⁿ ,Z ⁿ ) over a ring of integers with a displacement structure, referred to as a C-Cauchy-like matrix, will be formulated and presented. Using the displacement approach, which was originally discovered by Kailath, Kung, and Morf (J. Math. Anal. Appl. 68:395–407, 1979), a new superfast algorithm for the multiplication of a C-Cauchy-like matrix of the size n×n over a field with a vector will be designed. The memory space for storing a C-Cauchy-like matrix of the size n×n over a field is O(n) versus O(n ²) for a general matrix of the size n×n over a field. The arithmetic operations of a product of a C-Cauchy-like matrix and a vector is reduced dramatically to O(n) from O(n ²), which can be used to transform a latter point to another latter point such that . Moreover, the displacement structure can also be extended to a Kronecker matrix W ⊗ Z. A new class of the Kronecker-like matrices with the displacement rank r, r<n will be also discovered. The memory space for storing a Kronecker-like matrix of the size (n×1)⊗(1×n) over a field is decreased to O(rn). The arithmetic operations for a product of a Kronecker-like matrix with the displacement rank r and a vector is also accelerated to O(rn).     

Parallel computations and committee constructions

The paper reviewed the results bearing out the deep-seated relation between the parallel computations and learning procedures for the laminated neural networks one of whose formalizations is represented by the theory of committee constructions. Additionally, consideration was given to two combinatorial problems concerned with learning pattern recognition in the class of affine committees—the problem of verifying existence of a three-element affine separating committee and that of element-minimal affine separating committee. The first problem was shown to be N P-complete, whereas the second problem is N P-hard and does not belong to the Apx class.     

Modified designs and modified computations

This paper is concerned with devising computation schemes which can be used efficiently and economically to solve two-dimensional problems of elasticity for a series of successively modified versions of a design. Two computation schemes have been proposed. The first is an exact one in the finite element sense, representing a generalization and development of the substructure method. The second is formulated based on successive approximation. By making use of these computation schemes and the numerical result of the original version of the design, computations for the subsequent modified versions can be carried out easily, without the arduous and tedious work of determining the inverses of new assembled stiffness matrices. Numerical results, given in graphic and tabular forms, demonstrate the validity, versatility and efficiency of the computation schemes, including the remarkable convergence behavior for the successive approximation computation. Furthermore, exact and simple relations, connecting the basic quantities of the original to those of the modified versions, have been developed. With these relations, a general solution can be obtained by utilizing the numerical data from a few particular situations.     

Mapping and load-balancing iterative computations

We consider the mapping of iterative algorithms onto heterogeneous clusters. The application data is partitioned over the processors, which are arranged along a virtual ring. At each iteration, independent calculations are carried out in parallel, and some communications take place between consecutive processors in the ring. The aim is to determine how to slice the application data into chunks, and to assign these chunks to the processors, so that the total execution time is minimized. One major difficulty is to embed a processor ring into a network that typically is not fully connected, so that some communication links have to be shared by several processor pairs. We establish a complexity result that assesses the difficulty of this problem, and we design a practical heuristic that provides efficient mapping, routing, link- sharing, and data distribution schemes.     

Optimization of computations

Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 65–94, March–April, 1994.     

Infinite Possibilities

When it comes to creative technique, cover artist Rick Spix will sometimes have a plan in mind while other times implement a more improvised trial-and-error approach. Spix says that the Ultrafractal program lets him simply create art the way he wants to.     

A Remark on Infinite Matching vs Infinite Unification

In this note we refine a result in Berarducci and Venturini Zilli (1993), by showing that the limit of iterations of a matching gives rise to the most general unifying substitution.