Relationship between two concepts of equivalence for finite-state machines

In the letter, the relationship between the well-known concept of `equivalence? and the less well known but important concept of `relational equivalence? of finite-state machines is examined, It is shown that, for two strongly connected finite-state machines, the two concepts are the same. Also for two non-degenerate finite-memory finite-state machines it is shown that the two concepts of equivalence are the same. These results, together with some results already known, lead to a table of relationship between equivalence and relational equivalence of finite-state machines.     

An iteration algorithm of coding internal states of finite-state machines for minimizing the power consumption

A heuristic iteration algorithm of coding internal states of finite-state machines for reducing the power consumption is considered. The proposed algorithm is universal and can be applied to any results of coding the internal states (including random) to minimize the power consumption of the finite-state machine. In addition, the user can select a trade-off between the problem-solving quality and algorithm-execution time by specifying the maximum number of iterations. The experimental studies showed that the proposed approach is intended to decrease the power consumption of the finite-state machines on average by a factor of 1.73, as compared with the NOVA algorithm (in separate cases, by a factor of 3.29), and by a factor of 1.40, compared to the JEDI algorithm (in separate cases, by a factor of 2.31).     

Testability analysis and behavioral testing of the Hopfield neuralparadigm

Testability analysis and test pattern generation for neural architectures can be performed at a very high abstraction level on the computational paradigm. In this paper, we consider the case of Hopfield's networks, as the simplest example of networks with feedback loops. A behavioral error model based on finite-state machines (FSM's) is introduced. Conditions for controllability, observability and global testability are derived to verify errors excitation and propagation to outputs. The proposed behavioral test pattern generator creates the minimum length test sequence for any digital implementation     

Modeling robust asynchronous communication protocols withfinite-state machines

A.V. Aho et al. (Comput. Math. Applic., vol.8, p.205-14, 1982) used communicating finite-state machines to model synchronous protocols for reliable communication across unreliable channels. Their ideas are extended to modeling asynchronous protocols for communication across unreliable channels using finite-state machines communicating via an unreliable shared memory. Lower bounds on the size of machines and the number of symbols in the transmission alphabet required to achieve reliable communication are established. Two types of finite-state machines and two fault models for the shared memory are considered. In each case it is shown that there are robust protocols for deletion and insertion errors. It is also shown that there are no robust protocols for mutation errors. In contrast, in the synchronous case, robust protocols exist for all of these types of errors     

An algorithmic procedure for checking safety properties ofprotocols

A procedure for checking safety properties of communication protocols is presented. A protocol is specified as a collection of communicating finite-state machines (FSMs). Two novel algorithms used in this procedure are described. The first algorithm does incremental composition and reduction of FSMs. It uses three heuristic rules which reduce the number of states in the global FSM by one to two orders of magnitude while maintaining its observational equivalence. The second algorithm checks whether the behavior of one FSM is a subset of another FSM's behavior. This procedure has been applied to the ISDN Q.931 and alternating bit protocols     

Tokens vs. Signals: On Conformance between Formal Models of Dataflow and Hardware

Designing hardware often involves several types of modeling and analysis, e.g., in order to check system correctness, to derive performance properties such as throughput, to optimize resource usages (e.g., buffer sizes), and to synthesize parts of a circuit (e.g., control logic). Working directly with low-level hardware models such as finite-state machines (FSMs) to answer such questions is often infeasible, e.g., due to state explosion. Instead, designers often use dataflow models such as SDF and CSDF, which are more abstract than FSMs, and less expensive to use since they come with more efficient analysis algorithms. However, dataflow models are only abstractions of the real hardware, and often omit critical information. This raises the question, when can one say that a certain dataflow model faithfully captures a given piece of hardware? The question is of more than simply academic interest. Indeed, as illustrated in this paper, dataflow-based analysis outcomes may sometimes be defensive (e.g., buffers that are too big) or even incorrect (e.g., buffers that are too small). To answer the question of faithfully capturing hardware using dataflow models, we develop a formal conformance relation between the heterogeneous formalisms of (1) finite-state machines with synchronous semantics, typically used to model synchronous hardware, and (2) asynchronous processes communicating via queues, used as a formal model for dataflow. The conformance relation preserves performance properties such as worst-case throughput and latency.     

Halfadders modulo 2N using read-only memories

Halfadders modulo 2N are regarded as finite-state sequential machines, and are implemented with read-only memories. The application of the theory of `closed? partitions is shown to lead to considerable savings in the memory storage required, which improves with increasing word lengths, and gives a very regular interconnection pattern and parallel operation.     

A new formulation for state equation representation for Petri nets

A new algorithm for determination of state equations for Petri nets has been proposed. The proposed algorithm results in state equations similar to the state equations for linear sequential machines. All Petri nets may not be represented in the form of linear sequential machines. The resulting state equations are different from Petri net state equations and include output equations used in control theory literature.     

Heuristic procedure for the reduction of finite-state machines

A practical technique for the reduction of large finite-state machines is proposed. The method is based on an empirical evaluation of the machine outputs.     

Non-real-time realization of any finite-state sequential machine using a single shift-register

A model for simulating any finite-state sequential machine is presented as an alternative to the single shift-register model in [1]. The proposed model not only uses a single shift-register but also has the advantage of allowing a machine to be synthesized whose speed is improved by a factor of 2 and whose cost is reduced by nearly a factor of 2 over machines produced by the synthesis procedure associated with the former model.     

Understanding representational sensitivity in the iterated prisoner's dilemma with fingerprints

The iterated prisoner's dilemma is a widely used computational model of cooperation and conflict. Many studies report emergent cooperation in populations of agents trained to play prisoner's dilemma with an evolutionary algorithm. This study varies the representation of the evolving agents resulting in levels of emergent cooperation ranging from 0% to over 90%. The representations used in this study are directly encoded finite-state machines, cellularly encoded finite-state machines, feedforward neural networks, if-skip-action lists, parse trees storing two types of Boolean functions, lookup tables, Boolean function stacks, and Markov chains. An analytic tool for rapidly identifying agent strategies and comparing across representations called a fingerprint is used to compare the more complex representations. Fingerprints provide functional signatures of an agent's strategy in a manner that is independent of the agent's representation. This study demonstrates conclusively that choice of a representation dominates agent behavior in evolutionary prisoner's dilemma. This in turn suggests that any soft computing system intended to simulate behavior must be concerned with the representation issue.     

Synchronization for interactive multimedia presentations

When multimedia presentations allow users to make online adjustments such as reverse, skip, freeze-restart, and scale, maintaining temporal synchrony among several media streams becomes a complex modeling problem. Our approach uses dynamic extended finite-state machines for the task-an “actor” DEFSM for each medium and a “synchronizer” DEFSM to orchestrate them. This model achieves clear state-transition control flow and allows concise, precise specifications     

Efficient computation of unique input/output sequences in finitestate machines

This paper makes two contributions toward computing unique input/output (UIO) sequences in finite-state machines. Our first contribution is to compute all UIO sequences of minimal lengths in a finite-state machine. Our second contribution is to present a generally efficient algorithm to compute a UIO sequence for each state, if it exists. We begin by defining a path vector, vector perturbation, and UIO tree. The perturbation process allows us to construct the complete UIO tree for a machine. Each sequence of input/output from the initial vector of a UIO tree to a singleton vector represents a UIO sequence. Next, we define the idea of an inference rule that allows us to infer UIO sequences of a number of states from the UIO sequence of some state. That is, for a large class of machines, it is possible to compute UIO sequences for all possible states from a small set of initial UIOs. We give a modified depth-first algorithm, called the hybrid approach, that computes a partial UIO tree, called an essential subtree, from which UIO sequences of all possible states can be inferred. Using the concept of projection machines, we show that sometimes it is unnecessary to construct even a partial subtree. We prove that if a machine remains strongly connected after deleting all the converging transitions, then all of the states have UIO sequences. To demonstrate the effectiveness of our approach, we develop a tool to perform experiments using both small and large machines     

Implementation of finite-state machines based on programmable logic ICs with the help of the merged model of Mealy and Moore machines

The problem concerning the synthesis of finite-state machines (FSMs) based on programmable logic ICs, in which FSM’s output variables serve as the code (or part of the code) of internal states, has been examined. A solution to the problem is obtained with the help of the merged model of Mealy and Moore machines. A principal distinction between the proposed and well-known techniques is that an initial FSM undergoes no conversions related to an increase in the number of internal states and transitions thereof. The necessary conditions under which output variables can be used as the code of FSM’s internal states are presented. The method for synthesizing the merged model AC of Mealy and Moore machines is described. Basic results of investigations, as well as promising directions of further studies concerned with the development of new structural models of FSMs, are discussed.     

A Simple Protocol Whose Proof Isn't

Aho, Ullman, and Yannakakis have proposed a set of protocols that ensure reliable transmission of data across an error-prone channel. They have obtained lower bounds on the complexity required of the protocols to assure reliability for different classes of errors. They specify these protocols with finite-state machines. Although the protocol machines have only a small number of states, they are nontrivial to prove correct. In this paper we present proofs of one of these protocols using the finite-state-machine approach and the abstract-program approach. We also show that the abstract-program approach gives special insight into the operation of the protocol.     

Modeling, qualitative analysis, and performance evaluation of theetching area in an IC wafer fabrication system using Petri nets

Integrated circuit (IC) wafer fabrication systems can be characterized as discrete event systems. Petri nets are tools that have been successfully used to model and analyze such systems. This paper reports a project of applying Petri net methodologies to detailed modeling, qualitative analysis, and performance evaluation of the etching area in a real-world IC wafer fabrication system located in Taiwan's Hsinchu Science-Based Industrial Park, To tackle the problem of building a large and complex system model, a synthesis technique is used. The resultant extended net model is checked for important qualitative properties in manufacturing. A simple control policy for deadlock prevention is proposed. To obtain performance measures, simulation is used. The simulation result shows that except a small number of machines, the errors between the simulated and actual utilizations are less than 5%, The validated model can be used to answer many “what-if” questions, such as predicting the maximal throughput and bottleneck machines     

Hidden Markov processes

An overview of statistical and information-theoretic aspects of hidden Markov processes (HMPs) is presented. An HMP is a discrete-time finite-state homogeneous Markov chain observed through a discrete-time memoryless invariant channel. In recent years, the work of Baum and Petrie (1966) on finite-state finite-alphabet HMPs was expanded to HMPs with finite as well as continuous state spaces and a general alphabet. In particular, statistical properties and ergodic theorems for relative entropy densities of HMPs were developed. Consistency and asymptotic normality of the maximum-likelihood (ML) parameter estimator were proved under some mild conditions. Similar results were established for switching autoregressive processes. These processes generalize HMPs. New algorithms were developed for estimating the state, parameter, and order of an HMP, for universal coding and classification of HMPs, and for universal decoding of hidden Markov channels. These and other related topics are reviewed     

Reverse-time Markov processes (Corresp.)

The problem of representing a Markov process as a reverse-time Markov process is discussed. Diffusions and finite-state Markov processes are two important classes of Markov processes for which this problem has been considered. A gap in a paper of Castanon is pointed out which discusses diffusions; reverse-time finite and discrete-state Markov processes are then considered using martingale methods.     

Algebras of discrete event models

The authors consider discrete event models (DEMs) that describe logical system behavior, i.e. mathematical models that represent the set of traces of sequences of events that the system can execute. Examples of DEM formalisms include state machines, Petri nets, and Hoare's communicating sequential processes. All these formalisms are algebras, i.e. a set of models together with operators that combine models to form other models in ways in which real systems are interconnected. A general approach toward constructing model algebras is proposed. The approach covers both deterministic and nondeterministic models, and it can be tailored to recover existing formalisms and to obtain model families