Minimization of incompletely specified mealy finite-state machines by merging two internal states

A heuristic method for the minimization of Mealy finite state machines (FSMs) with unspecified values of the output variables based on merging two states is considered. Necessary and sufficient conditions for the possibility to merge two states and for forming wait states are given. Algorithms for determining the set of state pairs that can be merged, algorithms for finding the best pair for merging, and for the minimization of the number of FSM states and FSM input variables are presented. The proposed method makes it possible to reduce the number of internal states by a factor of 1.22 on the average and sometimes even by a factor of 2.75. The number of FSM transitions is reduced by a factor of 1.32 on the average and sometimes by a factor of 2.27. Compared with the well-known STAMINA computer program, the proposed method does not reduce the number of states but considerably reduces the number of transitions by a factor of 1.55 on the average and sometimes by a factor of 3.92.     

Minimization of mealy finite-state machines by internal states gluing

A problem of minimization of Mealy finite-state machines that is common in synthesizing digital devices on programmable logic devices is considered. The proposed approach uses an operation of gluing two states and represents the finite-state machine as a list of transitions. Cases when gluing two states generates wait states are described. Algorithms that minimize the number of internal states, the number of transitions and input variables of Mealy finite-state machines are given. The experimental results showed that when used to implement finite-state machines on programmable logic devices, the proposed method helps decrease the implementation cost 1.31 times on average and 3 times at best. Topical directions for further study of finite-state machines minimization methods are given.     

A method for minimizing the number of states for a restricted class of incompletely specified sequential machines

Summary In this paper are considered incompletely specified sequential machines for which the only unspecified entries are those which occur because of a restriction on the input states which can directly follow each possible input state.For these machines the minimum number of states is equal to the chromatic number of the graph of all pairs of incompatible states. A new method for determining a minimum-class partition of the set of states which is formed from compatible classes is given.     

A framework for compositional nonblocking verification of extended finite-state machines

This paper presents a framework for compositional nonblocking verification of discrete event systems modelled as extended finite-state machines (EFSM). Previous results are improved to consider general conflict-equivalence based abstractions of EFSMs communicating both via shared variables and events. Performance issues resulting from the conversion of EFSM systems to finite-state machine systems are avoided by operating directly on EFSMs, deferring the unfolding of variables into state machines as long as possible. Several additional methods to abstract EFSMs and remove events are also presented. The proposed algorithm has been implemented in the discrete event systems tool Supremica, and the paper presents experimental results for several large EFSM models that can be verified faster than by previously used methods.     

Unboundedness detection for a class of communicating finite-state machines

Let M and N be two communicating finite-state machines that exchange one type of message. We discuss an algorithm to decide whether the communication between M and N is bounded. The algorithm is based on constructing a finite representation of the reachability tree of M and N assuming that M and N progress at equal speeds.     

Transformation of a mealy finite-state machine into a moore finite-state machine by splitting internal states

The problem of transformation of a Mealy finite-state machine (FSM) into an equivalent Moore FSM is considered. This problem often arises in the practice of engineering design, when one needs to avoid direct dependence of the output values on variations in the input values. The proposed approach uses the operation of splitting of internal states of an FSM and represents the machine as a list of transitions. Experiment results have shown that transformation of Mealy FSM into Moore FSM increases the number of internal states, on the average, by a factor of 1.96 and increases the number of transitions by a factor of 2.05; the cost of realization of Moore FSM using an industrial software package is approximately twice as great as the corresponding cost for a Mealy machine. The up-to-date tendencies of development of minimization methods and Moore FSM synthesis are described.     

Optimal transfer trees and distinguishing trees for testing observable nondeterministic finite-state machines

The fault-state detection approach for blackbox testing consists of two phases. The first is to bring the system under test (SUT) from its initial state to a targeted state t and the second is to check various specified properties of the SUT at t. This paper investigates the first phase for testing systems specified as observable nondeterministic finite-state machines with probabilistic and weighted transitions. This phase involves two steps. The first step transfers the SUT to some state t' and the second step identifies whether t' is indeed the targeted state t or not. State transfer is achieved by moving the SUT along one of the paths of a transfer tree (TT) and state identification is realized by using diagnosis trees (DT). A theoretical foundation for the existence and characterization of TT and DT with minimum weighted height or minimum average weight is presented. Algorithms for their computation are proposed.     

Minimization of mealy finite-state machines by using the values of the output variables for state assignment

Structural models of finite-state machines (FSMs) that make it possible to use the values of the output variables for encoding the internal states are studied. To minimize the area (the parameter area is used to denote cost in the context of this paper) of FSM implementation, it is proposed to use the structural model of the class D FSM. A method for the design of the class D FSM in FPGA is proposed. This method involves two phases—splitting the internal states of the FSM (to satisfy the necessary conditions for the construction of the class D FSM) and encoding the internal states (to ensure that the codes are mutually orthogonal). It is shown that the proposed method reduces the area of FSM implementation for all families of FPGAs of various manufacturers by a factor of 1.41–1.72 on average and by a factor of two for certain families. Practical issues concerning the method and the specific features of its use are discussed, and possible directions of the elaboration of this approach are proposed.     

A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines

We study on-line scheduling on parallel batch machines. Jobs arrive over time. A batch processing machine can handle up to B jobs simultaneously. The jobs that are processed together form a batch and all jobs in a batch start and are completed at the same time. The processing time of a batch is given by the processing time of the longest job in the batch. The objective is to minimize the makespan. We deal with the unbounded model, where B is sufficiently large. We first show that no deterministic on-line algorithm can have a competitive ratio of less than 1+(?{m²+4}-m)/21+(\sqrt{m^{2}+4}-m)/2 , where m is the number of parallel batch machines. We then present an on-line algorithm which is the one best possible for any specific values of m.     

A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines

Identical parallel machine scheduling problem for minimizing the makespan is a very important production scheduling problem, but there have been many difficulties in the course of solving large scale identical parallel machine scheduling problem with too many jobs and machines. Genetic algorithms have shown great advantages in solving the combinatorial optimization problem in view of its characteristic that has high efficiency and that is fit for practical application. In this article, a kind of genetic algorithm based on machine code for minimizing the makespan in identical machine scheduling problem is presented. Several different scale numerical examples demonstrate the genetic algorithm proposed is efficient and fit for larger scale identical parallel machine scheduling problem for minimizing the makespan, the quality of its solution has advantage over heuristic procedure and simulated annealing method.     

A bottleneck-based heuristic for minimizing makespan in a flexible flow line with unrelated parallel machines

This study developed a bottleneck-based heuristic (BBFFL) to solve a flexible flow line problem with a bottleneck stage, where unrelated parallel machines exist in all the stages, with the objective of minimizing the makespan. The essential idea of BBFFL is that scheduling jobs at the bottleneck stage may affect the performance of a heuristic for scheduling jobs in all the stages. Therefore, in BBFFL, a variant of Johnson's rule is used to develop a bottleneck-based initial sequence generator (BBISG). Then, a bottleneck-based multiple insertion procedure (BBMIP) is applied to the initial sequence to control the order by which jobs enter the bottleneck stage to be the same as that at the first stage. Five experimental factors were used to design 243 different production scenarios and 10 test problems were randomly generated in each scenario. These test problems were used to compare the performance of BBFFL with several well-known heuristics. Computational results show that the BBFFL significantly outperforms all the well-known heuristics.     

Graph-theoretic method for merging security system specifications

Computer security policies specify conditions for permissions to access various computer resources and information. Merging two security policies is needed when two organizations, together with their computer systems, merge into one entity as in corporate business acquisition. We propose a graph-theoretic method for merging the role/object hierarchies of two security policies. The formulation of merged hierachies is based on the graph minor relation in graph theory. Ideally, the merged role hierarchy should contain both the participating role hierarchies as graph minors, and similarly for the object hierarchy. We show that one can decide in polynomial time whether this ideal case is possible when the participating hierarchies are trees. We also show that in case the merged hierarchy exists, it can be constructed in polynomial time. Algorithms for detecting the feasibility of an ideal merged tree and for constructing the merged tree are presented. Our hierarchy/tree merge method is also applicable to the integration of heterogeneous databases with generalization hierarchies.     

Nested partitions method for assembly sequences merging

The severe competition in the market has driven enterprises to produce a wider variety of products to meet consumer’s need. However, frequent variation of product specification and more complexity of product cause the assembly sequence planning of product become more and more complicated. As a result, the issue of assembly sequence planning of complex product becomes a problem which is worthy of concern. In this study, a methodology for assembly sequence planning of complex components is presented, which consists of three phases: assembly-based modular design, assembly subsequences generation for each module and assembly sequences merging. Nested partitions (NP) method is used to merge assembly subsequences. Assembly sequences merging can make full use of subsequences information of modules and simplify assembly sequence planning of the complex products. A desk lamp is used as an example for implementation to validate the feasibility of this research.     

A grouped storage method for minimizing relocations in block stacking systems

When storage and retrieval times of inventories are uncertain and the storage space for the inventories is limited, it is an important problem to assign the inventories to storage spaces so that the total expected number of relocations is minimized. This paper addresses a dynamic location problem as well as a static location problem. Mathematical models are proposed for obtaining the optimal solution. To overcome the excessive computational time of optimizing methods, a genetic algorithm is suggested. Also, simple heuristic rules are suggested to solve the dynamic location problem. Performance of various solution methods are compared with each other. Received: June 2005 / Accepted: December 2005     

A modified phoneme-based Chinese input method for minimizing conflict code rate

Previously, we proposed a phoneme-based Chinese input method with conflict code rate 24.7%. In this paper, we aim at constructing a modified method to further reduce the conflict code rate significantly. The modified method first introduces a new feature extraction rule that extracts the feature phonetic symbol of an extended radical in different manners. In the scope of 1043 extended radicals, 10 selected extended radicals are determined to be processed by the new feature extraction rule. The conflict code rate of the modified method is 13.5%, much lower than that of the original method, 24.7%.     

Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints

The efficiency of the classic alternating direction method of multipliers has been exhibited by various applications for large-scale separable optimization problems, both for convex objective functions and for nonconvex objective functions. While there are a lot of convergence analysis for the convex case, the nonconvex case is still an open problem and the research for this case is in its infancy. In this paper, we give a partial answer on this problem. Specially, under the assumption that the associated function satisfies the Kurdyka–?ojasiewicz inequality, we prove that the iterative sequence generated by the alternating direction method converges to a critical point of the problem, provided that the penalty parameter is greater than 2L, where L is the Lipschitz constant of the gradient of one of the involved functions. Under some further conditions on the problem's data, we also analyse the convergence rate of the algorithm.     

A subgradient selection method for minimizing convex functions subject to linear constraints

A readily implementable subgradient algorithm is given for minimizing a convex, but not necessarily differentiable, functionf subject to a finite number of linear constraints. It is shown that the algorithm converges to a solution, if any. The convergence is finite iff is piecewise linear.     

An algorithm for calculating indistinguishable states and clusters in finite-state automata with partially observable transitions

This paper presents a new algorithm for efficiently calculating pairs of indistinguishable states in finite-state automata with partially observable transitions. The need to obtain pairs of indistinguishable states occurs in several classes of problems related to control under partial observation, diagnosis, or distributed control with communication for discrete event systems. The algorithm obtains all indistinguishable state pairs in polynomial time in the number of states and events in the system. Another feature of the algorithm is the grouping of states into clusters and the identification of indistinguishable cluster pairs. Clusters can be employed to solve control problems for partially observed systems.