Search

The mining of partial periodic patterns is an interesting type of data mining that is widely used in the analysis of markets, such as for stock management and sales management. However, the existence of huge data sets make the scalability of data-mining algorithms a very important objective, and in recent years parallel computing has been applied to general data-mining algorithms. This paper addresses the problem of mining multiple partial periodic patterns in a parallel computing environment. To reduce the cost of communication between the processors, our approach employs the independence property of prime numbers to classify partial periodic patterns into multiple independent sets. Moreover, a novel method of distributing mining tasks among the processors is proposed. A set of simulations is used to demonstrate the benefits of our approach.

Cost-sensitive decision tree induction is to build a decision tree from training data with minimal cost.No previous research has studied how to induce the minimal cost tree if the classification task has to be completed in a limited time.This paper proposed an algorithm to induce time-constrained minimal cost tree.The experiment results show the performance of our algorithm is very satisfactory under different time constraints. A cost-sensitive decision tree is induced for the purpose of building a decision tree from training data that minimizes the sum of the misclassification cost and test cost. Although this problem has been investigated extensively, no previous study has specifically focused on how the decision tree can be induced if the classification task must be completed within a limited time. Accordingly, we developed an algorithm to generate a time-constrained minimal-cost tree. The main idea behind the algorithm is to select the attribute that brings the maximal benefit when time is sufficient, and to select the most time-efficient attribute (i.e., the attribute that provides maximal benefit per unit time) when time is limited. Our experimental results show that the performance of this algorithm is highly satisfactory under various time constraints across distinct datasets.

The present paper is closely related to an earlier publication wherein the present authors proposed a mathematical formulation for continuous nonlinear minimal-variance filters that led to stochastic differential equations satisfying known existence and uniqueness conditions for such equations. The necessity for the proposed reformulation of the problem arose from the use of the white-noise model to represent the physical system. The adoption of such a model allows certain formal simplicities in the derivation of filter equations, but these simplicities must be paid for by new complexities introduced by the requirement for mathematical rigor, as discussed in the previous paper. It is now shown that the modified formulation, while necessary for assured mathematical validity, can be dispensed with in the context of a computational mechanization.

The purpose of this paper is to investigate various properties of some learning automata operating in random environments. Based on the strategies of ''many-armed bandit problems,'' two sequential learning models, A"r","k and B"r","k","b, having deterministic and stochastic transition rules, respectively, are formulated. Automata using these strategies have shown the desired learning behavior, which is similar to the performance of linear-strategy automata and certain type of stochastic automata. Furthermore, the learning behavior of fuzzy automata in random environments is also considered. Comparison among various models has been made. Computer-simulated examples for the application of proposed models include games against nature and games between automata. The results from simulation have been considered quite satisfactory.

This paper deals with a nonlinear learning algorithm characterized by a threshold effect. The algorithm is derived in relation to a learning process in pattern recognition where steps must be taken to minimize the effect of spurious samples carrying unreliable information. With the assumption of a multivariate normal density for each pattern population, the nonlinear algorithm reduces to discarding the spurious samples with a threshold element and in the meantime performing an ordinary linear algorithm for the remaining samples. Optimal properties of this algorithm are studied and a criterion for selecting a proper threshold is discussed. A computer-simulated experiment in character recognition is presented to illustrate a possible application for the nonlinear algorithm. Results of this experiment have shown significant improvement over an ordinary linear algorithm in handling character samples with various imperfections due to the poor quality in writing or printing encountered in practice.

One of the primary issues confronting XML message brokers is the difficulty associated with processing a large set of continuous XPath queries over incoming XML streams. This paper proposes a novel system designed to present an effective solution to this problem. The proposed system transforms multiple XPath queries before their run-time into a new data structure, called an XP-table, by sharing their common constraints. An XP-table is matched with a stream relation (SR) transformed from a target XML stream by a SAX parser. This arrangement is intended to minimize the run-time workload of continuous query processing. In addition, an early-query-termination strategy is proposed as an improved alternative to the basic approach. It optimizes query processing by arranging the evaluation sequence of the member-lists (m-lists) of an XP-table adaptively and offers increased efficiency, especially in cases of low selectivity. System performance is estimated and verified through a variety of experiments, including comparisons with previous approaches such as YFilter and LazyDFA. The proposed system is practically linear-scalable and stable for evaluating a set of XPath queries in a continuous and timely fashion.

In this paper, properties of normalized stochastic languages are discussed and alternative procedures for constructing the Chomsky and Greibach normal forms for normalized stochastic context-free grammar (nscfg) are presented. A normalized stochastic context-free language (nscf l) is defined in terms of a nscfg. Furthermore, stochastic languages accepted by stochastic pushdown automata (spda) are defined, and relationships between stochastic context-free languages and spda are studied. The class of languages accepted by a spda with a 0 cutpoint is precisely the class of scf l.

This paper uses optimization theory and continuous invariant imbedding in order to derive computationally efficient sequential algorithms for the maximum likelihood estimation of bias errors in recursive filtering with noise corrupted input observations and correlated plant and measurement noise. Error analysis algorithms are derived for adaptive and nonadaptive systems with bias and modeling errors. Examples demonstrate the efficacy of the adaptive estimation algorithms and the error analysis algorithms for estimation with bias uncertainty.

This paper describes a fuzzy logic anti-slip system for Heavy Duty Off Road Vehicles. The anti-slippage system is based on distributed detection and local/global fuzzy control of slippage within an interconnected system of mechatronic wheel motors. Within this paper, the system layout, implementation, sensor data preprocessing, slip detection, four different local/global and test results under real working conditions are described. The system developed may serve as an example for successfully applied fuzzy control for a competitive (soon) commercially available product.

In this paper we describe an approach to the artificial recognition of events of a nonsymbolic nature, such as the bidimensional perspective views of scenes of our everyday world. Scenes are presented as colored pictures and the objective of the cognitive task is the labeling of the interpreted scene objects. The method is based on three major components: 1. (i) a preprocessed version of the scene (stimulus), 2. (ii) a semantic map and 3. (iii) an algorithm which performs interpretation of the stimulus under the guidance of the semantic map. The algorithm is sequential and proceeds from general to specific, thereby achieving efficient tree-pruning (contextual elimination). Stimulus interpretation is based on attribute-value matching, but classification relies strongly on the accumulated context. Backtracking provisions are available in the sequential cognitive algorithm for correction of earlier wrong hypotheses. Experiments are presented and described. The major weakness of the approach is the present lack of a satisfactory theory of inference. Flexibility, generalizability, and efficiency appear to be valid merits.

By extracting the basic properties common to the formal grammars appeared in existing literatures, we develop a general formulation of formal grammars. We define a pseudo grammar and derive from it the well-known probabilistic, fuzzy grammars and so on. Moreover, several interesting grammars such as ⊔∗ grammars, ⊔ ⊓ grammars, ⊔ ⊓ grammars, composite B -fuzzy grammars, and mixed fuzzy grammars, which have never appeared in any other papers before, are derived.

This paper presents the innovations approach to space-time or distributed parameter filtering and smoothing. The innovations process is defined for systems with space-time coordinates and properties of this process are derived. Development of a special operator notation allows a very simple presentation of the algorithms for estimation. The filtering results are in agreement with those obtained by other derivations whereas it is believed that the fixed-interval and fixed-point smoothing algorithms for space-time systems are new.

This paper proposes a family of new methods for the storage and reconstruction of binary patterns by means of block-projections. More flexibility and less ambiguity is thus achieved. A complete analysis is presented in terms of (i) storage requirements, (ii) computation, and (iii) unambiguity ratio. Furthermore, applications to general patterns are described.

In the past, automatic procedures for the design of pattern classifiers have usually used a machine of fixed size. These procedures require that prior to learning we know, or can guess, the complexity of the decision surface used by the teacher. Techniques have been discovered for changing the complexity of a pattern classifier by adding or removing parts of it. These methods, respectively called “growing” and “pruning” use well established learning rules applied alternately with the addition or removal of comput,ing equipment. Growing is thus a process by which we can increase the complexity of a classifier until it fits the problem. Pruning removes computing equipment from a classifier whose performance is satisfactory, but inefficient. The paper describes our experimental evaluation of these procedures. These studies have shown that these techniques are capable of designing a classifier which closely models a complex teacher with a minimum of storage.

This paper describes the proceedings of the workshop on Biomedical Statistics and Computation of the Fourth Annual Symposium on the Interface. This was a two day symposium held at the University of California at Irvine on September 17 & 18, 1970. It was sponsored jointly by the ACM, ASA, and the California Mathematics Council. Dr. Tarter chaired this workshop. The thirty participants in this workshop represented all of the disciplines which combine to become Biocomputer Statistics. There were physicians both interested in and active in computer applications to medicine, directors of biomathematics and biostatistics programs, computer specialists, and mathematical and applied statisticians, as well as medical students. It should be noted that the three other workshops at the Interface Symposium were more concerned with computer hardware and software and thus attracted most of the pure computer specialists. This tended to weight this workshop with a large proportion of statisticians.

This paper presents the problem of unsupervised learning structure and parameter adaptive pattern recognition. Different near optimal solutions that alleviate the infinite or exploding memory requirements of the optimal solution are suggested. The learning capabilities of these methods are compared with that of the optimal supervised scheme by presenting an example.

TUTOR is a high speed Turing machine simulator, written in IBM System 360 Assembler Language. Turing machines are represented by flow diagrams using H. Hernes table of machines as the basic elements. Composite machines so represented may themselves be used as elements of other machines, thus incorporating the concept of subroutines. In this paper the relationship of a flow diagram to the basic concept of a Turing machine is developed, the functions of the basic machines are described, and a complete programmer's guide is included.

This paper describes procedures for the design of experiments to determine whether or not a given finite-state machine is operating correctly. The machines in question are assumed to be strongly connected and in a reduced form. The procedures presented are valid for any type of faults that do not increase the number of states of the original machine. More efficient procedures are presented in the last section, when certain restrictions are imposed on the class of possible faults.

If information science is to be considered a “science” in the true sense of the word, there is a clear need for the development of a set of general concepts and analytical expressions regarding the flow of information in any situation for which information serves as a resource. This paper discusses quantitative aspects of a theory leading to the development of such a pragmatic information theory . At the heart of a theory of pragmatic information is the measure of information contained in a set of data. At the pragmatic level, information has value to the extent that it is useful as a resource for purposeful activity. The primary “purposeful activity” in life is decision-making. Hence, information and decision-making are inextricably tied together; in fact, information is data of value in decision-making . In this paper, we discuss quantitatively a very general decision model which provides a formal and comprehensive representation of uncertainty in decision-making. Other decision models presented in the literature assume away a considerable and important portion of the uncertainty that exists in decision-making. This model is then used as a framework for examining the role of information in decision-making in a way that is also formal and comprehensive. Hence, the decision model suggested facilitates a meaningful analysis of information; this analysis culminates in the development of a measure of the value of the pragmatic information contained in a set of data.

As the size and efficiency of computers increases, it is clear that they will be used for extremely large file information storage and retrieval banks, in particular for non-scientific documents and data. Such an information bank might be, for example, the legal code for a large country or even the legal codes of all countries. Another example might be individual medical histories for a large population base, possibly the whole world. Storage and retrieval algorithms for such large files present special problems. It is no longer feasible, for instance, for the computer to consider every item in the memory in order to retrieve a designated subset. The problem, then, is how to classify the information, that is, divide it up into disjoint categories so that retrieval is feasible, efficient, and accurate. The present paper presents a general approach or logical framework for handling such problems. The basic observation is that classification really amounts to introducing an equivalence relation on the universal set of all the items in the file. The problem is how to define these equivalence relations in a natural manner, that is, in a manner which reflects something of the structure of the information and which thus allows us to store and retrieve the information in a structured fashion. This classification procedure is not conceived as being an algorithm but rather a mathematical procedure on which various algorithms can be based. This procedure can be described as follows: First a very broad, initial classification is made. For each such classification, there is a standard or canonical form. The canonical form involves some finite number of parameters. Syntactically these parameters are just terms of various sorts, but our approach is to consider rather the universe of values of each parameter. This is the semantic universe associated with the given parameter. These semantic universes are seen to have a very natural structure when they are considered in a certain way as subcollections of a type-theoretic universe based on some concrete set (such as the set of people, the set of married couples, etc). This structure allows us to define the desired equivalence in a natural way on a given semantic universe. Taking the conjunction of the parameters occurring in a given canonical form we thus get a classification for the sentences having that canonical form. Since this obtains for each canonical form, we thus have a classification for the whole information bank. Concrete examples are given to illustrate the applicability of this approach. The approach is, in fact, a mathematical generalization of a concrete case already treated by this method.

This paper deals with the problem of discrete-time demodulation of angle-modulated analog signals transmitted over fading channels, with emphasis on Rayleigh and Rician channels. First, analog and discrete communication models that represent both Rayleigh and Rician channels are presented. Then, various discrete nonlinear estimation techniques including the extended Kalman, iterated extended Kalman and truncated and Gaussian second-order filters are applied to the discrete communication model to obtain various digital quasi-optimum demodulator structures. The baseband forms of these structures are also developed.

In this paper a modified type of Turing machine is introduced and investigated: 1. (1) Information on the working tape “disappears” if it is not rewritten or reread during a certain length of time; 2. (2) states of the finite control are no longer attainable if they are not reached during a certain period. These machines are considered as devices for the recognition of formal languages. It is demonstrated that their capabilities in principle are the same as for Turing machines, but that the speed of recognition is reduced.

Homogeneous job systems are systems in which all of a finite set of jobs to be processed by the system have exactly the same processing requirements. This paper assumes that each job first executes an input task requiring an input unit (channel or controller) for some amount of time Tc along with a memory unit. Then it executes a computational task requiring a processing unit and the memory for some amount of time Tp. Under these assumptions, it is possible to derive some inequalities concerning the relative number of memory, input, and processor units which can be efficiently used by the system as a function of Tc and Tp. The scheduling problem is to order tasks and assign resources to them in such a way as to minimize some cost function. The cost functions considered in this paper are job set finishing time and dwell time. Some theorems are stated and proved which yield closed form expressions for the minimum finishing time in batch and in time-shared systems as a function of the number of jobs, memories, processors, input units, and Tc and Tp. The purpose of this study is to derive some general results which aid in the efficient utilization of multiprocessor computer systems. Although this study is directed toward a specific type of homogeneous system, it is shown that the results are applicable to other systems (e.g., systems with output).

In this paper a nonlinear distance metric criterion for feature selection in the measurement space is proposed. The criterion is not only a more reliable measure of class separability than criteria based on the Euclidean distance metric but also computationally more efficient.

In this paper, we propose a machine like a stochastic automaton as the generalized random environment and show that every random environment discussed up to the present is a special case of this machine. The system consisting of this environment and an automaton is equivalent to an autonomous stochastic automaton. Moreover, we introduce some examples for this system.

In this paper, we propose a novel differentiated domain protection (DDP) scheme to address survivability in multi-domain optical networks. Survivable routing in multi-domain networks is a challenging algorithmic problem because it requires choosing links that provide adequate protection both between domains and within domains that may offer different protection services. To satisfy the survivability requirements of different domains, DDP considers differentiated protection schemes, i.e., dedicated protection, shared protection, or no protection in different domains. In order to respect the principle of transparent management in multiple domains, DDP abstracts a multi-domain optical network to a virtual topology graph (VTG) for solving routing between domains. Simulation results show that DDP, unlike traditional schemes, can provide trade-off between protection methods and also allows better resource utilization.

Traditionally, computer data base design has been handled intuitively without the assistance of quantitative techniques. A systematic approach to data base design consists of these phases: (1) a mathematical problem statement; (2) problem reduction; (3) mathematical solution. This paper addresses the first phase (associated work on the other phases is briefly discussed) and demonstrates that certain data base design problems can be formulated as nonlinear, zero-one programs. The decision variables state which logical data base elements (entities and attributes) are represented in each subdivision (subfile) of the physical data base. Computational experience using cluster analysis for problem reduction and branch and bound for mathematical solution is reported. It is shown that a planned subdivision of the physical data base can yield noticeable operating cost improvements over conventional data base designs.

This paper treats the problem of assessing utilities and worths over multi-attributed alternatives. Worth assessment is a systematic approach for evaluating complex alternatives under certainty. By incorporating an element of risk into the problem, worths may be transformed into utilities which are suitable for use in decision making. The role of hierarchies in worth assessment is emphasized. Several independence assumptions are discussed with restrict the multi-attributed utility functions to relatively simple forms, specifically the additive and quasi-additive or multiplicative form. Various techniques for evaluating milti-attributed utilities subject to such restrictions are surveyed. Again the role of hierarchies is emphasized. By keeping the various attributes in their proper structural relationship, the assessment of multi-attributed utilities can often be facilitated.

Many potential applications of mechanical theorem proving exist in such areas as question answering, robot control, program writing, proof of program correctness, verification of mathematical proofs, general problem solving, and command and control systems. Theorem-proving systems must become much more efficient before applications become generally practical, and much statistical testing will be necessary to select the strategies to be used in practical systems. This paper reports on the results of experimental testing of some major theorem-proving strategies and their interactions. Test results are based on CPU time. The paper concludes that (1) subsumption and factoring should not be used (at least, in this implementation), (2) set of support and P1-deduction should be used, (3) the choice between breadth-first searching and unit preference searching is highly problem dependent, and (4) merge and linear strategies have little effect on the proof process. No statistically significant interaction among the strategies was discovered.

This paper presents some formal generative specifications for describing the graph languages consisting of the sets of directed graphs with labeled arcs. Some mathematical results are introduced. In addition, we consider applications to specification technique for data structures and complexity measure of computer software. Finally, directions for future research are indicated.

This paper describes a new technique for representing complex data structures as labeled graphs and matrices instead of the conventional tree representation. Graph (matrix) representation gives a generalized and effective means of understanding, visualizing, and analyzing data systems. Some procedures are given to perform efficient query capability, i.e., to permit the user to select entities efficiently from his file that are the values of some Boolean functions.

The purpose of this paper is to propose an unitary formal model, comprehensive of both the classical state-space and problem-reduction approaches, in order to define a new structure of problem solver. In particular, the model we propose, which is strictly related in its formal aspects to the graphs and AND/OR graphs theory, is primarily intended to allow the problem solver to choose, at each step during the solution process, the best representation for the problem (state-space or problem-reduction) and, hence, the optimal expected search strategy. In the paper, the basic functions and the fundamental structure of a problem solver are first presented. The formal definition of the integrated approach is then introduced, together with explanatory examples, and the new model is critically discussed in detail. The formal notions are globally illustrated by a complete example dealing with all the aspects of the solution process. A problem solver model, based on the new approach, is also proposed. Implementation of systems to support an integrated problem solver and the related linguistic problems are not discussed in the paper.

The paper presents, as far as the author is aware, the first practical general method for constructing LR ( k ) parsers. It has been used without computational difficulty to produce LR (1), LR (2), and LR (3) parsers for grammars of the size of ALGOL. The algorithm involved consists of two phases, where phase 2, the state-splitting phase, is applied if phase 1 fails. Only the most important case of phase 1 with k = 1 is presented in detail here. Ways of enhancing the efficiency of the algorithm are considered and, in particular, a method is provided whereby the work required for phase 1 when k = 1 is at most a linear function of the number of configurations.

As the number of processes and resources increases within a computer system, does the probability of that system's encountering deadlock increase or decrease? The problem of deadlock in computer systems and a model applicable to the investigation of this problem are presented. The model treats sequences of resource activity as potential members of the set of strings accepted by a probabilistic automaton. This paper, after explaining the model and its application, describes a transformation on the automaton which makes it amenable to calculations of the probability of deadlock. These calculations consist of: 1. 1. Derivation of necessary and sufficient conditions for an automaton to be well-behaved —formally described as accepting a normalized language; 2. 2. Usage of these conditions to yield closed-form equations of deadlock probability under several definitions thereof. Although the automaton model used in these calculations is a probabilistic pushdown automaton, it is indicated that the procedures described can also be applied to other types of probabilistic automata modeling other deadlock situations. Results of calculations on actual computer system models are also described, indicating that within the types of systems considered, the probability of deadlock increases.

The File Design Analyzer is a software package which evaluates well-known data base storage structures and access methods in terms of secondary storage processing time and storage overhead required to service a set of user applications. It implements a first-order analytical model to specifically evaluate sequential, indexed sequential, direct access, and inverted multilist storage structures. Interaction with the package is available in conversational mode, enabling the experienced analyst to conduct on-line sensitivity analysis. The paper describes three extensions which converted an abstract conceptual model into a practical tool for evaluation of existing or proposed data base designs: batched transactions, multi-access interference due to shared secondary storage, and analysis of variable record size. A case study from a real system illustrates the potential of the File Design Analyzer to provide insight regarding the optimal choice of physical parameters within a specified storage structure and to effectively compare alternative storage structures for a particular set of applications.

The purpose of this paper is to propose a new type acceptor called the “two-dimensional on-line tessellation acceptor” (denoted by “2-ota”) and to examine several properties of the 2-ota. The 2-ota might be considered as a real-time mode of rectangular array bounded cellular space, introduced by Smith and Beyer. First, several fundamental properties (e.g., closure properties) of the 2-ota are examined. Then, the accepting power of the 2-ota is compared with that of the two-dimensional finite automaton, introduced by Blum and Hewitt. The main results are 1. 1. The class of sets accepted by nondeterministic 2-ota's contains properly that of sets accepted by nondeterministic two-dimensional finite automata; 2. 2. The class of sets accepted by deterministic 2-ota's is incomparable with that of sets accepted by deterministic (or nondeterministic) two-dimensional finite automata.

Management scientists studying the decision-making process are in agreement that information and decision making are closely tied together. Unfortunately, improvements in information technology have not included methodologies which capture this interdependence. This paper is concerned with treating this interdependence in an aspect of systems design termed the “information updating interval.” Three evaluation models are presented, along with a special-case model for estimating related probability distributions.

This paper discusses the least cost testing sequence problem. This problem has been considered under the assumption that costs and rejecting probabilities are completely known a priori. In this paper, a procedure for selecting the optimal testing sequence in the case that rejecting probabilities are unknown is proposed. Experimental results indicate that the optimal testing sequence can be selected by this procedure.

The paper presents a detailed analysis of a class of signal processing systems with continuous electronic array scanning in the presence of additive white Gaussian front-end receiver noise. In particular, it presents: 1. (1) a unified treatment of frequency-modulation and time-modulation scanning systems by using a set of orthogonal functions, 2. (2) the development of a generalized formula for the beam-sampling signal and its properties, and 3. (3) a performance evaluation of the system for estimating the unknown angle of arrival of the received signal. It is shown that for the detection and decision criteria chosen for the analysis, the system exhibits a threshold effect determined by the received signal-to-noise ratio, the number of receiving elements in the array, and the number of pulses integrated at the envelope-detector output.

TIL systems are L systems accommodating both the possibility of reaction to changes in environment and the possibility of cell interactions. In this sense they constitute an extension of TOL systems and IL systems. This paper investigates mathematical properties of the class of TIL systems and of the class of languages generated by them.

The observed sequence of electrocardiographic R-R intervals have been analyzed by appropriate linear and nonlinear Markoff processes. Recent investigations by the authors have shown that appropriate comprehensive descriptions of the models are provided only by generalized or multi-step Markoff processes. In this paper the problem of recognizing sequences of states in a generalized Markoff process model is discussed and solutions provided.

In this paper we propose a model for interaction between random environments and random automata. To this model we can apply the theory of (generalized) random systems with complete connections (i.e., learning models or dynamic models) in order to describe its behavior. We shall call such a system a general control system. Next criteria and conditions of expediency of a random automaton within such a system are formulated. Finally two special cases are examined.

Tomek's preprocessing scheme is discussed for editing the training set prior to analyzing it by Hart's condensed nearest neighbor technique. Preprocessing was performed by a κ-nearest-neighbor pdf estimation scheme, although other methods are suggested in this paper. The procedure was studied experimentally and was found to achieve a significant reduction in the storage requirements of the CNN method while maintaining approximately the same error rate, or even improving it.

This paper presents techniques for representing complex data structures as hierarchically organized sets of graphs or sets of matrices. We also present various system-reducing techniques for generating efficient retrieval systems from data management systems. Thus, the techniques provide an environment for efficient retrieval and fast maintenance as well as providing a simple and effective means of understanding, visualizing, and analyzing the data systems.

This paper develops a matrix approach to the solution of the measurement and control problems in synchronous sequential machines. The control problem in sequential machines is concerned with finding input sequences that take a given machine from a known initial state to a predesignated terminal state. There may be many different measurement problems of interest in sequential machines. One important measurement problem is the identification of the unknown initial state of the machine, called the initial-state identification problem or diagnosing problem; another important measurement problem is the identification of the terminal state of the machine, known as the terminal-state identification problem or homing problem, of which a special case is the synchronizing problem. These measurement problems may be solved by applying predetermined input sequences to the machine and noting the resulting output sequences. The conventional approach to the solution of these measurement and control problems is to make use of the information contained in the transition table of the machine in conjunction with its response tree, which is basically an exhaustive tree search process. In the present paper, instead of using the transition table and the corresponding response tree, we use only the transition matrix representation of the machine and its higher order forms to solve the aforementioned problems. The suggested approach is very systematic and completely algorithmic, and thus lends itself to easy computer implementation.

This paper deals with cellular d-graph automata in which each node has internal memory proportional to log"d"-"1N, where N is the number of nodes in the underlying graph G. It is shown how such an automaton can assign unique labels to the nodes of G in O(log"d"-"1N) time. Such an automaton can also count the number of nodes and edges in G in O(log"d"-"1N) time. Algorithms for identifying all the cut nodes and all bridges in G, each in O(log"d"-"1N) time, are also presented.

The purpose of this paper is to report a modeling approach to the evaluation of internal sorting methods. The technique used is a regression modeling technique and has been found to be a very fast statistical method for evaluation which relies on the performance of data collection from the system being evaluated. The parameters considered for evaluation are: (1) number of stages, (2) number of transfers, (3) number of records, (4) sort time, (5) number of comparisons. The empirical model has been developed for sorting time as a function of the number of stages, number of records, number of comparisons, and number of transfers. The correlation coefficient obtained during the process of modeling was an average of 0.96 and has been found statistically significant.

This paper describes a novel approach to automatic channel equalization in digital transmission systems. The approach is based on the use of a finite-dimensional rational approximation to the channel characteristics. This class of channel approximation has the following advantages: it allows a finite parametrization of the channel impulse response which may be of infinite duration, it allows for the possibility of the noise being colored, it applies to either single- or multiple-channel systems, and it has the pedigogical advantage that many other algorithms in current use are based on models which are special cases of this model. The rational approximation to the channel characteristics is used in the paper to develop a new receiver structure using fixed-lag smoothing ideas. Simulation studies are presented showing that the receiver offers advantages over other algorithms for mitigating the effects of intersymbol and interchannel interference including those arising from carrier phase errors.

In this paper, we first investigate the relationship between the accepting powers of four-way two-dimensional finite automata and deterministic three-way tape-bounded two-dimensional Turing machines whose input tapes are restricted to square ones. The second part of this paper solves several open problems concerning closure properties of deterministic three-way tape-bounded two-dimensional Turing machines.