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.     

Transformation of a language L* specification of an FSM into an automata equivalent specification in the language L

A method is proposed to transform an FSM specification in the language L* into a specification in the language L. Using additional predicate symbols, the former specification is first transformed into a specification of an FSM with finite memory. Then this specification is transformed into an automata equivalent specification in the language L.     

Improved method of synthesis of an automaton from its specification in the language L

A modification of an algorithm for synthesis of an automaton from its logical specification is proposed. This algorithm is based on a procedure of splitting components of a disjunctive form. Improvements are aimed at decreasing the number of most complex procedures used during synthesis and at reducing the complexity of formulas processed by the procedures. Moreover, the modification enhances the natural parallelism of the algorithm.     

On the class of L*-language formulas that specify finite-memory finite-state machines

The class of L*-language specifications that specify finite-memory finite-state machines is characterized. The transformation of an L*-language specification into an equivalent specification that specifies a finite-memory finite-state machine is substantiated.     

Using a Protean language to enhance expressiveness in specification

A Protean specification language (B. Bloom, 1995) based on structured operational semantics (SOS) allows the user to invent appropriate operations to improve abstraction and readability. This is in contrast to traditional specification languages, where the set of operations is fixed. An efficient algorithm, described by A. Dsouza and B. Bloom (1995), uses binary decision diagrams (BDDs) to verify properties of finite specifications written in a Protean language and provides the basis for a model checker we have developed. The paper provides a synthesis of our work on Protean languages and relates the work to other specification techniques. We show how abstraction and refinement in the Protean framework can improve the effectiveness of model checking. We rewrite and verify properties of an existing Z specification by defining suitable operations. We also show how a Protean language can be used to model restricted I/O automata, action refinement, and 1-safe and k-bounded Petri nets     

Formal methods for analysis of discrete systems using a specification language

A realization of an algorithm that translates an MSC diagram (an MSC document) into an event equivalent Petri net is described, and the correctness of the algorithm is proved. The net obtained in this way can be used to analyze properties of the original MSC document. The mentioned algorithm is a part of a system designed for verification and analysis of MSC documents. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 31–56, July–August 2009.     

On removing the machine from the language

Summary Many of the problems in programming languages today are a result of the model of computation offered by our machines. Structured programming combats these problems by restricting flow of control and storage references to a relatively safe set of control and data structures. Some current research attempts to aid programming reliability by enforcing such restrictions in the programming language. This paper proposes a simpler view of some basic language elements (variable, assignment, parameter), not based on our machines, that is safe without restriction. Structuring is then defined independently of what is being structured. A single, simple structure, applied to both values and assignments, yields equivalents for the safe set of data and control structures.This work was supported by the National Research Council of Canada     

Decomposition analysis of the multidisciplinary coupling in LED System-in-Package design using a DSM and a specification language

LED System-in-Package (SiP) aims to reduce manufacturing and material costs of LED lighting products through integration of components into one single package, based on semiconductor technology. This introduces multidisciplinary coupling in the system behavior which requires reconsideration of the existing LED design decomposition practice. This paper presents our method to do a decomposition analysis of the multidisciplinary coupling structure for an industry scale LED SiP design problem. The innovative aspect of our method is the use of a specification language to specify the input-output (binary) relationships between design variables, behavioral responses, objective and constraint responses. A design structure matrix, representing the mutual linkage, is automatically generated from the specification. The rows and columns of the DSM are subsequently re-ordered using partitioning and sequencing algorithms to provide insight in the coupling structure. The method is illustrated by means of a simplified example. Subsequently, the results for a recently manufactured LED SiP design prototype are presented.     

The functional logic language BABEL and its implementation on a graph machine

The first-order, untyped, functional logic language Babel is extended by polymorphic types and higher order functios. A sophisticated incompatibility check which is used to guarantee nonambiguity of BABEL programs is presented. For the implementation of the language, unification and backtracking are integrated in a programmed (functional) graph reduction machine. The implementation of this machine has been used for a comparison between Babel and PROLOG based on the runtimes of some example programs.     

The development of a specification language for a computer security system

The primary goal of this paper is to define an initial step towards the definition of ‘systems grammar’ based on the notion of formal languages which can be used as a ‘tool’ in the formal representation of computer security systems. Currently all modelling done on computer security systems is written up as mathematical models. These mathematical models are usually based on the mathematics of relations amongst objects, as opposed to the model described in this paper which is based on the theory of formal languages. This paper is aimed at people who are doing research on the logical aspects of computer security. It is the first of a series of two papers. This paper will give interim results and make more specific the definition of a ‘formal language’ which suits the computer security environment. The second paper will illustrate the actual use of the defined ‘formal language’ and show how to represent the characteristics of a computer security environment by using this ‘formal language’.     

Synthesis of a nondeterministic automaton from its logical specification. I

Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 3–15, September–October, 1995.     

Performability analysis of computer systems: from model specification to solution

Computer systems reliability/availability modeling deals with the representation of changes in the structure of the system being modeled, which are generally due to faults, and how such changes affect the availability of the system. On the other hand, performance modeling involves representing the probabilistic nature of user demands and predicting the system capacity to perform useful work, under the assumption that the system structure remains constant. With the advent of degradable systems, the system may be restructured in response to faults and may continue to perform useful work, even though operating at lower capacity. Performability modeling considers the effect of structural changes and their impact on the overall performance of the system. The complexity of current computer systems and the variety of different problems to be analyzed, including the simultaneous evaluation of performance and availability, demonstrate the need for sophisticated tools that allow the specification of general classes of problems while incorporating powerful analytic and/or simulation techniques. Concerning model specification, a recently proposed object oriented modeling paradigm that accommodates a wide variety of applications is discussed and compared with other approaches. With respect to solution methods, a brief overview of past work on performability evaluation of Markov models is presented. Then it is shown that many performability related measures can be calculated using the uniformization or randomization technique by coloring distinguished states and/or transitions of the Markov model of the system being studied. Finally, the state space explosion problem is addressed and several techniques for dealing with the problem are discussed.     

A Mandarin dictation machine based upon a hierarchical recognitionapproach and Chinese natural language analysis

An experimental Mandarin dictation machine for inputting Mandarin speech (spoken Chinese language) into computers is described. Because of the special characteristics of the Chinese language, syllables are chosen as the basic units for dictation. The machine is designed based on a hierarchical language recognition approach in which acoustic signals are first recognized as a sequence of syllables, possible word hypotheses are then formed from the syllables, and the complete sentences are finally obtained. This approach is implemented by two subsystems. The first recognizes the syllables using speech signal processing techniques, the second subsystem then identifies the exact characters from the syllable and corrects the errors in syllable recognition. The detailed syllable recognition algorithms, word formation rules, parser, grammar, and the syntactic checking algorithms are described. With newspaper text in the form of isolated syllables as input, the preliminary test results indicate that such a dictation machine is not only practically attractive, but technically feasible     

Sufficient conditions of deterministic implementation of finite-state automata with retention of the numbers of their states

The following three conditions for nondeterministic finite-state automata are defined: input embeddability, output embeddability, and input decomposability. Automata satisfying these conditions are called nondeterministic automata with embeddability. A method for deterministic implementation of such automata with retention of the numbers of their states is proposed. These automata correspond to block-procedural high-level programming languages. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 55–62, May–June, 2000.     

From a domain analysis to the specification and detection of code and design smells

Code and design smells are recurring design problems in software systems that must be identified to avoid their possible negative consequences on development and maintenance. Consequently, several smell detection approaches and tools have been proposed in the literature. However, so far, they allow the detection of predefined smells but the detection of new smells or smells adapted to the context of the analysed systems is possible only by implementing new detection algorithms manually. Moreover, previous approaches do not explain the transition from specifications of smells to their detection. Finally, the validation of the existing approaches and tools has been limited on few proprietary systems and on a reduced number of smells. In this paper, we introduce an approach to automate the generation of detection algorithms from specifications written using a domain-specific language. This language is defined from a thorough domain analysis. It allows the specification of smells using high-level domain-related abstractions. It allows the adaptation of the specifications of smells to the context of the analysed systems. We specify 10 smells, generate automatically their detection algorithms using templates, and validate the algorithms in terms of precision and recall on Xerces v2.7.0 and GanttProject v1.10.2, two open-source object-oriented systems. We also compare the detection results with those of a previous approach, iPlasma.     

VHDL语言在状态机电电路中的设计与实现

简要介绍了VHDL语言进行工程设计的优点,并详细说明了利用VHDL语言设计状态机电电路的过程,最后进行了仿真,仿真结果证明该设计能够实现状态机电路的功能。