The incomplete perfect phylogeny (IPP) problem and the incomplete perfect phylogeny haplotyping (IPPH) problem deal with constructing a phylogeny for a given set of haplotypes or genotypes with missing entries. The earlier approaches for both of these problems dealt with restricted versions of the problems, where the root is either available or can be trivially re-constructed from the data, or certain assumptions were made about the data. In this paper, we deal with the unrestricted versions of the problems, where the root of the phylogeny is neither available nor trivially recoverable from the data. Both IPP and IPPH problems have previously been proven to be NP-complete. Here, we present efficient enumerative algorithms that can handle practical instances of the problem. Empirical analysis on simulated data shows that the algorithms perform very well both in terms of speed and in terms accuracy of the recovered data.

We consider real-time rendering of dynamic glossy objects with realistic shadows under distant all-frequency environment lighting. Previous PRT approaches pre-compute light transport for a fixed scene and cannot account for cast shadows on high-glossy objects occluded by dynamic neighbors. In this paper, we extend double/triple product integral to generalized multi-function product integral . We represent shading integral at each vertex as the product integral of multiple functions, involving the lighting, BRDF, local visibility and dynamic occlusions. Our main contribution is a new mathematical representation and analysis of multi-function product integral in the wavelet domain. We show that multi-function product integral in the primal corresponds to the summation of the product of basis coefficients and integral coefficients. We propose a novel generalized Haar integral coefficient theorem to evaluate arbitrary Haar integral coefficients. We present an efficient sub-linear algorithm to render dynamic glossy objects under time-variant all-frequency lighting and arbitrary view conditions in a few seconds on a commodity CPU, orders of magnitude faster than previous techniques. To further accelerate shadow computation, we propose a Just-in-time Radiance Transfer (JRT) technique. JRT is a new generalization to PRT for dynamic scenes. It is compact and flexible, and supports glossy materials. By pre-computing radiance transfer vectors at runtime, we demonstrate rendering dynamic view-dependent all-frequency shadows in real-time.

Summary form only given. A novel multiple-pattern matching algorithm for LZW compressed files using the Aho-Corasick algorithm (Aho, A.N. and Corasick, M.J., 1975) is reported. Since the LZW trie can be reconstructed without explicit decompression (Amir, A. et al., J. System Sciences, vol.52, p.299-307, 1996), a state transition table is then built from the LZW trie and the AC automaton and is used in our algorithm for fast multiple-pattern searching. The algorithm takes O(mt+n+r) time with O(mt) extra space, where n is the size of the compressed file, m is the total size of all patterns, t is the size of the LZW trie and r is the number of occurrences of the patterns. Extensive experiments have been conducted to test the performance of the algorithm and to compare it with other well-known compressed pattern matching algorithms, particularly the similar algorithm developed by M. Kida et al. (see J. Discrete Algorithm, vol.1, no.1, 2000). The results show that the proposed algorithm is practically the fastest among all approaches when the number of patterns is not very large. Therefore, our algorithm is preferable for general string matching applications. The proposed algorithm is efficient for large files and it is particularly efficient when being applied in an archival search, if the archives are compressed with a common LZW trie.

Summary form only given. With an increasing amount of text data being stored in compressed format, being able to access the compressed data randomly and decode it partially is highly desirable for efficient retrieval in many applications. The efficiency of these operations depends on the compression method used. We present a modified LZW algorithm that supports efficient indexing and searching on compressed files. Our method performs in a sublinear complexity, since we only decode a small portion of the file. The proposed approach not only provides the flexibility for dynamic indexing in different text granularities, but also provides the possibility for parallel processing in both encoding and decoding sides, independent of the number of processors available. It also provides good error resilience. The compression ratio is improved using the proposed modified LZW algorithm. Test results show that our public trie method has a compression ratio of 0.34 for the TREC corpus and 0.32 with text preprocessing using a star transform with an optimal static dictionary; this is very close to the efficient word Huffman and phrase based word Huffman schemes, but has a more flexible random access ability.

Recently a number of algorithms have been developed to search files compressed with the Burrows-Wheeler Transform (BWT) without the need for full decompression first. This allows the storage requirement of data to be reduced through the exceptionally good compression offered by BWT, while allowing fast access to the information for searching by taking advantage of the sorted nature of BWT files. We provide a detailed description of five of these algorithms: BWT-based Boyer-Moore, Binary Search, Suffix Arrays, q-grams and the FM-index, and also present results from a set of extensive experiments that were performed to evaluate and compare the algorithms. Furthermore, we introduce a technique to improve the search times of Binary Search, Suffix Arrays and q-grams by 22% on average, as well as reduce the memory requirement of the latter two by 40% and 31%, respectively. Our results indicate that, while the compressed files of the FM-index are larger than those of the other approaches, it is able to perform searches with considerably less memory. Additionally, when only counting the occurrences of a pattern, or when locating the positions of a small number of matches, it is the fastest algorithm. For larger searches, Binary Search provides the fastest results. Comparative results with non-BWT based search methods are also included. Copyright © 2005 John Wiley & Sons, Ltd.

Compressed pattern matching is an emerging research area that addresses the following problem: Given a text file in compressed format and a pattern, report the occurrence(s) of the pattern in the file with minimal (or no) decompression. In this paper, we report our work on compressed pattern matching in LZW compressed files. The work includes an extension of Amir et al.'s well-known "almost-optimal" algorithm. The original Amir et al.'s algorithm has been improved to search not only the first occurrence of the pattern but also all other occurrences. A faster implementation for so-called "simple patterns" is also proposed. The work also includes a novel multiple-pattern matching algorithm using the Aho-Corasick algorithm. The algorithm takes O(mt+n+r) time with O(mt) extra space, where n is the size of the compressed file, m is the total length of all patterns, t is the size of the LZW trie, and r is the number of occurrences of the patterns. Extensive experiments have been conducted to test the performance of our algorithms and to compare with other well-known compressed pattern matching algorithms, particularly the BWT-based algorithms and another similar multiple-pattern matching algorithm by Kida et al. that also uses the Aho-Corasick algorithm on the LZW compressed data. The results showed that our multiple-pattern matching algorithm is competitive among the best compressed pattern-matching algorithms and is practically the fastest among all approaches when the number of patterns is not very large. Therefore, our algorithm is preferable for general string matching applications. The proposed algorithm is efficient for large files and it is particularly efficient when being applied on archive search if the archives are compressed with a common LZW trie. LZW is one of the most efficient and popular compression algorithms used extensively and our method requires no modification on the compression algorithm. The work reported in this paper, therefore, has great economic and market potential.

In this paper, work on compressed pattern matching in LZW compressed files is reported. The reported work is based on author's well-known "almost-optimal" algorithm. The improvements include the multipattern matching and a faster implementation for so-called "simple pattern", which is defined as "a pattern with no symbol appearing more than once". Extensive experiments have been conducted to test the search performance and compared with the "decompress-then-search" and the best available compressed pattern-matching algorithm, particularly the BWT-based algorithms.

Summary form only given. StarZip, a multi-copora text compression system, was introduced together with its transform engine StarNT. One of the key features of the StarZip compression system is to develop domain specific dictionaries and provide tools to develop such dictionaries. StarNT was utilized because it achieves a superior compression ratio than almost all the other recent efforts based on BWT and PPM. StarNT is a dictionary-based fast lossless text transform. The main idea is to record each English word with a representation of no more than three symbols. This transform maintains most of the original context information at the word level and provides an "artificial" strong context. It ultimately reduces the size of the transformed text that, in turn, is provided to a backend compressor. This data structure provides a very fast transform encoding with a low storage overhead. StarNT also treats the transformed codewords as an offset of words in the transform dictionary. The time complexity for searching a word in the dictionary is achieved in the transform decoder. Experimental results have shown that the average compression time has improved by orders magnitude compared to previous dictionary-based transform LIPT. The complexity and compression performance of bzip2, in conjunction with this transform, is better than both gzip and PPMD. Results from five copora have shown that StarZip achieved an average improvement in compression performance (in terms of BPC) of 13% over bzip2-9, 19% over gzip-9, and 10% over PPMD.

Summary form only given. The approximate pattern matching on the text transformed by the Burrows-Wheeler transform (BWT) was considered. This is an important first step towards developing a compressed pattern matching algorithm for the BWT based compression system. Algorithms are proposed to solve the K-mismatch problem. Tests were performed on different pattern lengths using 133 selected files from the Canterbury, Calgary, and TREC corpus. The results on the K-mismatch pattern matching show that the running time and storage are superior to the fast suffix tree approach. Thus, once the index arrays are created, for repeated pattern search operations and for long patterns, the proposed algorithms perform significantly better than the agrep and ngrep. Using DFA verification, the search time is almost constant. The amortized cost is lower for multiple patterns search operations.

Summary form only given. The compressed pattern matching problem is to locate the occurrence(s) of a pattern P in a text string T using a compressed representation of T, with minimal (or no) decompression. The BWT performs a permutation of the characters in the text, such that characters in lexically similar contexts will be near to each other. The motivation for our approach is the observation that the BWT provides a lexicographic ordering of the input text as part of its inverse transformation process.

This paper explores two techniques for on-line exact pattern matching in files that have been compressed using the Burrows-Wheeler transform. We investigate two approaches. The first is an application of the Boyer-Moore algorithm (1977) to a transformed string. The second approach is based on the observation that the transform effectively contains a sorted list of all substrings of the original text, which can be exploited for very rapid searching using a variant of binary search. Both methods are faster than a decompress-and-search approach for small numbers of queries, and binary search is much faster even for large numbers of queries.

Summary form only given. Wavelets intrinsically give us the capability of localized signal decomposition and analysis in space and frequency. We present the recursive merge filter (RMF) discrete wavelet transform (DWT) algorithm, that organizes intermediate coefficients with respect to both space and frequency. This allows close coupling and pipelining with the encoder, fine grained coding, and "cheap growing" of larger DWT from smaller ones in a constant number of filter operations. The RMF algorithm computes the DWT of an array of length N in a bottom-up fashion, by successively "merging" two smaller DWT (four in 2D), and applying the wavelet filter only on the "smooth" or DC coefficients.

Summary form only given. The contribution of this paper is an extension of the pruned tree-structured hierarchical vector quantization (PTSHVQ) algorithm, with a focus on designing and benchmarking a complete Internet-aware system for the real-time delivery of compressed images. We extend the PTSHVQ algorithm to enable the encoder to use a combination of "coarse" and "fine" rate control mechanisms. The coarse rate control is achieved by switching between successive HVQ lookup tables, thereby changing the bit rate on a logarithmic scale, e.g., to give 4, 2, 1, 0.5 bpp, etc. The fine rate control is achieved by sub-setting into the address space of the current HVQ lookup table, e.g., generating 4, 3.5, 3, 2.5 bpp. The combination of these two strategies of switching between HVQ stages and subsetting the available range of addresses at each stage gives us a much larger dynamic range as well as finer calibration of operational bit rates than any existing HVQ system. Organizing the codebooks into binary tree structures by using the greedy BFOS algorithm guarantees locally optimal rate-distortion behavior at each operational bit rate. The function of the distributed transcoder is to enable the regulation of operational bandwidth over a heterogeneous network, thereby guaranteeing fairness in broadcast type applications.

No abstract available.

[Summary form only given]. In this paper we describe several methods that can be used to improve the compression ratio of compression algorithms based an the Burrows-Wheeler transform, as implemented in 'bzip2', when used in combination with English language text files. We first briefly describe the Burrows-Wheeler transform and some of its strengths and weaknesses. We then describe our implementations of enhancements and test results. All of our enhancements are implemented in the form of pre- and postprocessing algorithms that are used in addition to the transform. The use of our algorithms has resulted in improvements in compression ratios of up to 20% over bzip2. The first method involves changing the order of characters in the character set encoding of the input file. We describe different ways to improve the encoding order. A more elaborate method involves minimizing the contextual differences between subsequent codes, using an optimized encoding order obtained by solving a traveling salesman problem. In the second method we replaced frequently occurring bigrams by single unused character codes, in order to better utilize the available character encoding space. In most cases this method did not result in improvements in the compression ratio. The final method is a refinement of the method we presented in "Preprocessing Text to Improve Compression Ratios", DCC 98. A common English language dictionary is used to preprocess input text and replace English words with encodings that are more easily compressible by bzip2. In this paper we describe optimizations to our original method to further improve the compression ratio. We also show practical ways to use our method on wide-area networks like the Internet, and easy ways to solve the problem of dictionary distribution and caching.

Summary form only given. We propose a video coding and delivery scheme which is geared towards low bit-rate and real-time performance requirements. We use a hybrid vector quantization scheme, with finite state wavelet-based hierarchical lookup vector quantization (FSWHVQ) for coding motion vectors, which embeds the Horn and Schunck optical flow algorithm in table-lookups, and uses lattice vector quantization (LVQ) for the prediction errors. This video coding scheme is both fast (table-lookups) and accurate (dense motion field), and avoids the blocking artifacts and poor prediction which plagues block coding schemes at low bit rates. For restricted image compression/transmission scenarios like teleconferencing, for which a good training set may be available, the FSWHVQ scheme may be viewed as storing as an internal representation in its lookup tables, a valid and complete model of the problem domain. Two row-wise lookups quantize the row-wise pixel values to give two table indices, Y0 and Y1, followed by a column-wise second-level table lookup, which quantizes the column-wise indices into one index, ZO. Horn and Schunck's optical flow method applies spatial and temporal derivative masks, e.g., of size 2/spl times/2, at corresponding spatial locations of the current and previous images. These mask applications are embedded inside table-lookups. The motion field averages (u/sub av/,v/sub av/), and the previous frame, I/sub t-I/, together comprise the "state", and are updated at each frame. The prediction errors are encoded with LVQ, as the error vectors are small (due to the accurate optical flow-based motion estimation), but more randomly distributed. It is possible to handle large displacements, by using the optical flow computations on the "smooth" bands in the DWT (discrete wavelet transform) domain.

We propose a real-time image coding system, which is capable of adapting instantaneously to the available channel bandwidth. The range of operational bandwidths for this system has a finer calibration than ordinary hierarchical vector quantization (HVQ) or wavelet based hierarchical vector quantization (WHVQ) methods suggested in the literature. These properties make it very attractive for networks with fluctuating available bandwidth, like the Internet. All encoder and decoder operations are strictly constant time per pixel, proceeding through table lookups, and are intrinsically suitable for parallel and hardware implementation.

We propose a video coding and delivery scheme which is geared towards low bit-rate and real-time performance requirements. We use a finite state wavelet-based hierarchical lookup vector quantization (FSWHVQ) scheme, which embeds the optical flow calculations in table-lookups. This video coding scheme is both fast (table-lookups) and accurate (dense motion field), and avoids the blocking artifacts and poor prediction which plagues block coding schemes at low bit rates. For restricted image compression/transmission scenarios like teleconferencing, for which a good training set may be available, the FSWHVQ scheme may be viewed as storing an internal representation in its lookup tables, a valid and complete model of the problem domain.

Summary form only given. We discuss the use of a text preprocessing algorithm that can improve the compression ratio of standard data compression algorithms, in particular 'bzip2', when used on text files, by up to 20%. The text preprocessing algorithm uses a static dictionary of the English language that is kept separately from the compressed file. The method in which the dictionary is used by the algorithm to transform the text is based on earlier work of Holger Kruse, Amar Mukherjee (see Proc. Data Comp. Conf., IEEE Comp. Society Press, p.447, 1997). The idea is to replace each word in the input text by a character sequence which encodes the position of the original word in the dictionary. The character sequences used for this encoding are chosen carefully in such a way that specific back-end compression algorithms can often compress these sequences more easily than the original words, increasing the overall compression ratio for the input text. In addition to the original method, this paper describes a variation of the method specifically for the 'bzip2' data compression algorithm. The new method yields an improvements in compression ratio of up to 20% over bzip2. We also describe methods how our algorithm can be used on wide area networks such as the Internet, and in particular how dictionaries can automatically be synchronized and kept up to date in a distributed environment, by using the existing system of URLs, caching and document types, and applying it to dictionaries and text files.

Abstract only given. Presents an algorithm for text compression that exploits the properties of the words in a dictionary to produce an encryption of given text. The basic idea is to define a unique encryption or signature of each word in the dictionary by replacing certain characters in the words by a special character "*" and retain a few characters so that the word is still retrievable. The question is whether we can develop a better signature of the text before compression so that the compressed signature uses less storage than the original compressed text. This indeed is possible as our experimental results confirm. For any cryptic text the most frequently used character is "*" and the standard compression algorithms can effectively exploit this redundancy in an effective way. Our algorithm produces the best lossless compression rate reported to date in the literature. One basic assumption of our algorithm is that the system has access to a dictionary of words used in all the texts along with a corresponding "cryptic" dictionary. The cost of this dictionary is amortized over the compression savings for all the text files handled by the organization. If two organizations wish to exchange information using our compression algorithm, they must share a common dictionary. We used ten text files from the English text domain to test our algorithm.

Road networks are important features of satellite imagery. The main contribution of the present road detection method consists of an effective enhancement technique and an efficient segmentation technique that removes non-road pixels step by step from the image where parameters involved: in each step images are determined by the sensor characteristics (like spatial resolution and spectral range) of the satellite. Also, the segmentation process depends not only on the road contrast but also on the road length. Thus, a low contrast but long road segment does not get removed. We have tested the algorithm on a number of images from IRS and SPOT satellites and the results are satisfactory.

Data compression methods are used to reduce the redundancy in data representation in order to decrease the data storage requirements and communication costs. In order to exploit the benefits of data compression to conserve internal processor storage and computation resources, it is desirable to perform operations on compressed data without decompressing it. We present hardware algorithms and VLSI implementation of a chip to search a compressed text with respect to keys or patterns in compressed form using Huffman-type tree-based codes.

We present a new high speed parallel architecture and its VLSI implementation to design a special purpose hardware for real-time lossless image compression/ decompression using a decorrelation scheme. The proposed architecture can easily be implemented using state-of-the-art VLSI technology. The hardware yields a high compression rate. A prototype 1-micron VLSI chip based on this architectural idea has been designed. The scheme is favourably comparable to the lossless JPEG standard image compression schemes. We also discuss the parallelization issues of the lossless JPEG standard still compression schemes and their difficulties.

In this article, we discuss the problem of enhancing the speed of Huffman decoding. One viable solution to this problem is the multibit scheme which uses the concept of k-bit trees to decode up to k bits at a time. A linear-time optimal solution for the mapping of 2-bit trees into memory is presented. The optimal solution is derived by formulating the memory mapping problem as a binary string mapping problem and observing that at most four different 4-bit patterns can occur within any 2-bit Huffman tree. In addition to reducing the processing time of decoding, the optimal scheme is storage efficient, does not require changes to the encoding process, and is suitable for hardware implementations. © 1995 John Wiley & Sons, Inc.

The paper presents a method for detecting linear features in a satellite image. For enhancing these features, a local operation based algorithm is proposed which uses a certain multiplicative score rather than the commonly used additive score. The main contribution is in segmenting the linear features in the enhanced image where an adaptive segmentation technique is proposed on the basis of statistical models. A robust parameter estimation is done for this purpose.

Standard Boolean and comparison operators are based on the True/False logic and are therefore not quite suitable for handling events/activities defined over periods of time. In this paper, we generalize the Boolean and comparison operators by allowing their input and output operands to be sets of time intervals. Efficient algorithms for the implementation of the extended operators are presented. The generalized operators can be used to enhance the user interface of time-oriented query languages and allow application users to express their time-related qualifications more succinctly and elegantly. The paper is concluded by examples showing the flexibility of the extended operators in expressing time-related requirements.

Describes the architecture and design of a CMOS VLSI chip for data compression and decompression using tree-based codes. The chip, called MARVLE, implements a memory-based architecture for variable length encoding and decoding based on tree-based codes. The architecture is based on an efficient scheme of mapping the tree representing any binary code onto a memory device. A prototype 2-mm CMOS VLSI chip has been designed, verified, and fabricated by the MOSIS facility. The chip has a 512*12 static RAM with an access time of 4 ns and logic circuitry for compression as well as decompression. The chip occupies a silicon area of 6.8 mm*6.9 mm and consists of 49695 transistors. The prototype chip yields a compression rate of 95.2 Mb/s and a decompression rate of 60.6 Mb/s with a clock rate of 83.3 MHz. The VLSI hardware can be used to implement the JPEG baseline compression scheme.>

This paper presents special-purpose linear array processor architecture for determining longest common subsequences (LCS) of two sequences. The algorithm uses systolic and pipelined architectures suitable for VLSI implementation. The algorithms are also suitable for implementation on parallel machines. The author first develops a 'greedy' algorithm to determine some of the LCS and then proposes a generalization to determine all LCS of the given pair of sequences. Earlier hardware algorithms were concerned with determining only the length of LCS or the edit distance of two sequences.>

The design and implementation of a CMOS VLSI chip for data compression and decompression, using tree-based codes are described. The chip, called MARVLE, implements a memory-based architecture, for variable length encoding and decoding based on tree-based codes. The chip implements an architecture that is based on an efficient scheme for mapping the tree representing any binary code onto a memory device. A prototype 2- mu m chip has been designed and verified, and fabricated by MOSIS. The chip can yield a compression rate of 57 Mb/s and a decompression rate of 31 Mb/s with a clock rate of 50 MHz. The VLSI hardware can be used to implement the JPEG baseline compression scheme.>

New optimal systolic algorithms for the transitive closure problem on ring and linear arrays of processors is presented. The data dependency of the Warshal-Floyd algorithm is exploited to obtain highly pipelined parallel algorithms. One of the algorithms is asymptotically seven times more cost-effective than previous algorithms for computing transitive closure problems. The authors introduce a new expository device, called the RCT diagram, that depicts simultaneously the flow of data and computation of parallel algorithms.>

We present new memory based architectures for the design of special purpose hardware for real-time compression and decompression of data. The architecture is based on a novel idea of mapping the decode/encode tree of any binary code on to a memory device that corresponds to simultaneous decoding/encoding of multiple bits. The hardware is programmable, adaptable and yields a high compression rate. Using 1 μm CMOS process technology, this could easily lead to over 100 Mbits/sec compression rate for the JPEG baseline compression scheme.

A new class of VLSI architectures for data transformation of tree-based codes is proposed. The focus is on transformation functions used for data compression and decompression. The encoding algorithm is based on a pipeline architecture and can generate the code bits in parallel. The algorithms use the principle of propagation of a token in a reverse binary tree constructed from the original codes. The design approaches are applicable to any binary codes, although static Huffman code is used as an illustration. A new hardware algorithm for generating adaptive Huffman codes is proposed and a VLSI architecture for implementing the algorithm is described. The high speed of the new algorithms ensures that data transformation is done as data are being transferred from/to high-speed I/O communication devices.>

Methods are discussed to enhance the efficiency and speed of data compression techniques in DBMS (database management systems). Arithmetic coding utilizes the skewness of character distribution by assigning larger intervals (code ranges) to characters having higher probabilities of occurrence. A scheme is presented which effectively increases the code ranges of individual characters by splitting the interval assignment into different groups. This decreases the rate of interval narrowing and hence improves the compression efficiency. Hardware assistance for arithmetic and tree-based coding is also discussed and high-speed VLSI algorithms for data compression are presented. The proposed algorithms give rates that are an order of magnitude faster than currently attainable encoding speeds.>

The author presents pipelined hardware algorithms with time complexity O(n+m) for determining between two character strings expressed as the length of the longest common subsequence of the given pair of strings. The algorithms use cellular architecture with simple basic cells and regular nearest-neighbor communication generally suitable for VLSI implementation. Two methods are presented: a sequential method with serial text input and an alternating method in which both the pattern and the text are serially applied to the machine. Theorems are proved that lead to a very optimized design of a basic cell.>

A compression algorithm that is tailored to utilize the enormous speed and memory size of supercomputers is presented. It utilizes an enhanced arithmetic coding scheme. Efficient VLSI designs for the enhanced scheme are given. The designs are suitable for inclusion in disk and communication controllers of supercomputers and would provide a practical way to increase thresholds of data transfer rates and communication bandwidth effectively.>

In this paper, we present a functional description of a VLSI chip aimed at reducing the cost of data transmission and data access within information processing machines and distributed information systems. The chip maps standard character codes (e.g., ASCII) into more efficient codes (e.g., Huffman's codes) using a tree module of basic cells. In bit-serial communication controllers, for example, the parallel-to-serial transformation unit can be simply replaced by the proposed chip. The VLSI design can provide speeds that far exceed current and projected peak transfer rates of high-speed disks and communication controllers.

Integrated circuit fabrication technologies place certain restrictions on the relationships with and between mask layers. These “design rules” are intended to describe the class of designs that the fabrication process will correctly implement.

This paper is concerned with the design of hardware algorithms for nonnumeric computation. The subset of nonnumeric operations considered is derived from string processing languages such as Snobol or high-level database languages used in database management architectures. Being uniformly structured, the hardware could be implemented using LSI technology yielding an estimated pattern matching rate of about 100 million characters/s. The proposed nonnumeric processor will find applications in the environment of parallel (or associative) database management architectures, processing of large unstructured textual files, as a stand-alone microprocessor in digital communications which need simple search and update operations, or as a nonnumeric CPU that can be used along with the conventional CPU to expedite string processing operations.

This paper is concerned with the design of hardware algorithms for nonnumeric computation. The subset of nonnumeric operations considered is derived from string processing languages such as SNOBOL or high-level data base languages used in data base management architectures. It is shown that cellular hardware can be designed to perform these operations on-line while the data is accessed from a rotating secondary storage medium. Being uniformly structured, the hardware could be implemented using LSI technology yielding an estimated pattern matching rate of about 100 million characters/sec. The proposed nonnumeric processor will find applications in the environment of parallel (or associative) data base management architecture, processing of large unstructured textual files, as a stand-alone microprocessor in digital communications which need simple search and update operations, or as a nonnumeric CPU that can be used along with the conventional CPU to expedite string processing operations.

This paper is an attempt to develop minimization algorithms for switching circuits based on Reed-Muller canonic forms. In particular, algorithms are presented for obtaining minimal modulo 2 or complement modulo 2 sum-of- products (or sums) expressions of any arbitrary single-output or multiple-output switching function with fixed polarities of the input variables.

A fundamental problem in "cellular logic" is to be able to "synthesize" "cellular arrays" for arbitrary switching functions that minimize a set of design parameters like size of the arrays and complexity of the individual cells and of the interconnection pattern on the cells. This paper is an attempt to develop "minimization algorithms for cellular arrays."

In this paper it is proved that regular events are representable in the cellular model proposed by John von Neumann, and a construction of a finite-state cellular automaton is presented. The procedure was motivated primarily by McNaughton's construction of an automaton using slow but well-timed elements.

This paper develops a theory of symmetric ternary switching functions and presents systematic methods for their detection, identification and synthesis. Shannon's theory of binary symmetric functions is extended to ternary functions by defining a set of five ``priming'' operations which, together with the ``permutation'' operations, form a group. Algebraic characterizations of totally and partially symmetric ternary functions are discussed. The method of detection and identification is based on a set of simple rules derived in terms of equalities of the residual functions of the given function with respect to pairs of variables of symmetry in a cyclic order. The notions of fundamental and simple symmetric ternary functions have been introduced and their algebraic properties have been studied. These concepts are then applied to develop a synthesis procedure which uses two basic 3-valued electronic gates recognizing the ``maximum'' or the ``minimum'' of the inputs. Possible generalizations of the results derived in this paper to arbitrarily many-valued functions are indicated.