We introduce generalized finite automata as a tool for specification of bi-level images. We describe an inference algorithm for generalized finite automata and a lossy compression system for bi-level images based on this algorithm and vector quantization.

Weighted finite automata (WFA) is a tool for specifying real functions and in particular grayscale images. The image compression software based on this algorithm is competitive with other methods in compression of typical grayscale images. It performs particularly well for high compression rates, for color images, and compared to other methods it has several additional advantages. This paper mainly deals with image manipulation. Weighted finite transducers (WFT) can be used to specify the widest variety of image transformations (linear operators on grayness functions). The authors briefly introduce WFA and WFT and give some examples of image transformations specified by WFT.

A new application of finite automata as computers of real functions is introduced. It is shown that even automata with a restricted structure compute all polynomials, many fractal-like and other functions. Among the results shown, the authors give necessary and sufficient conditions for continuity, show that continuity and equivalence are decidable properties, and show how to compute integrals of functions in the automata representation.

The authors show how to integrate wavelet-based and fractal-based approaches for data compression. If the data is self-similar or smooth, one can efficiently store its wavelet coefficients using fractal compression techniques resulting in high compression ratios.>

The limit sets of cellular automata, defined by Wolfram, play an important role in applications of cellular automata to complex systems. A number of results on limit sets are proved, considering both finite and infinite configurations of cellular automata. The main concern of this paper is with testing membership and (essential) emptiness of limit sets for linear and two-dimensional cellular automata.

The equivalence problem for deterministic two-way transducers was a longstanding problem finally shown decidable by E. M. Gurari. We show a generalization of this result, namely that it is decidable whether two single-valued two-way transducers are equivalent on an NPDTOL language. We obtain this result by showing that it is even decidable whether a two-way transducer is single-valued on an NPDTOL language. Our solution is based on the compactness property of the systems of equations over a finitely generated free monoid shown recently by J. Lawrence and M. Albert and also V. S. Guba. This was a longstanding open problem known as the Ehrenfeucht Conjecture. Our approach also shows that for one-way transducers their single-valuedness on a given HDTOL language can be tested, and thus the equivalence of two single-valued one-way transducers on an HDTOL language is decidable, too. Our results imply the decidability of the HDOL and HDTOL sequence equivalence problems, also longstanding open problems solved recently by K. Ruohonen and the authors, respectively.

The following problem is shown to be decidable.Given are homomorphisms h~ and h2 from 2" to ~* and strings a~ and a2 over 2: such that h,~(a,) is a proper prefix of h?+~(o,) for t = 1, 2 and all n -> 0; that is, for t --1, 2, h, generates from o, an infinite string at with prefixes/g/(a~) for all n -> 0. Test whether at = a2.From this result easily follows the decidability of limit language equivalence (~-eqmvalence) for D0L systems.

Informal mathematical proofs admit and require interpretation while formal logic proofs suppress (abstract from) meanings.The former is closely related to problem solving and computer programming.The latter, which is commonly used for proving program correctness, complicates this procedure because it separates problem solving from programming.A constructive mathematical proof in finite discrete mathematics of an existential theorem is a computer program if the nertinent data structures and functions are expressed in a programming language.Several detailed examples of graph theoretical problems and theorems are presented along with their constructive proofs and corresponding programs.

We consider the subfamilies of rational and pushdown transducers and corresponding translations (relations) which are most frequently encountered in the literature. We survey some of the known results on the characterization, factorization, closure properties, decision problems and comparisons of classes and give new results on these properties using either direct proofs or results from other theories such as homomorphic equivalence.

This paper is about two constructions for transforming planar systolic arrays. By a systolic array we mean a uniformly structured processor configuration that allows only local communication (between neighbour processors) and supports high throughout by pipelining. Such configurations are suitable for VLSI implementation [4, 5].

The following problem is shown to be decidable. Given are homomorphisms h1 and h2 from Σ* to Σ* and strings σ1 and σ2 over Σ such that hni(σi) is a proper prefix of hn+1i (σi) for i = 1, 2 and all n ≥ 0, i.e. for i = 1, 2, hi generates from σi an infinite string αi with prefixes hni(σi) for all n ≥ 0. Test whether α1 = α2. From this result easily follows the decidability of limit language equivalence (ω-equivalence) for DOL systems.

B-trees of order m are a “balanced” class of m -ary trees, which have applications in the areas of file organization. In fact, they have been the only choice when balanced multiway trees are required. Although they have very simple insertion and deletion algorithms, their storage utilization, that is, the number of keys per page or node, is at worst 50 percent. In the present paper we investigate a new class of balanced m -ary trees, the dense multiway trees, and compare their storage utilization with that of B-trees of order m . Surprisingly, we are able to demonstrate that weakly dense multiway trees have an Ο (log 2 N ) insertion algorithm. We also show that inserting m h - 1 keys in ascending order into an initially empty dense multiway tree yields the complete m -ary tree of height h , and that at intermediate steps in the insertion sequence the intermediate trees can also be considered to be as dense as possible. Furthermore, an analysis of the limiting dynamic behavior of the dense m -ary trees under insertion shows that the average storage utilization tends to 1; that is, the trees become as dense as possible. This motivates the use of the term “dense.”

Charactenzattons of recurs~vely enumerable sets as mappings of equality and mtmmal sets are given An equality (minimal) set is the set of all (minmaal) solutions of an instance of the Post correspondence problem where the solutions are viewed as stnngs The mar result ~s that every recurstvely enumerable set can be expressed (effecUvely) as a homomorphlc image of a minimal set.From the algebraic pomt of view this seems to be the simplest characterization of recurslvely enumerable languages A corollary of the mare result ts the solution of an open problem formulated by A Salomaa A purely homomorphlc characterization of regular sets is denved How such a characterization can be obtained for various ttrne and space complexRy classes for languages ts outhned