General method of testing the compatibility of interacting automata with finite memory

A method is proposed for compatibility analysis of two interacting partial nondeterministic automata A and B specified in a first-order language with monadic predicates. In contrast to a method proposed earlier, no restrictions are imposed on the form of specification of the automaton B. These investigations were partially supported by INTAS grant 96-0760. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 25–37, November–December, 1999.     

A hybrid optimization approach to conformance testing of finite automata

Unique Input–Output sequences (UIOs) are quite commonly used in conformance testing. Unfortunately finding UIOs of minimal length is an NP hard problem. This study presents a hybrid approach to generate UIOs automatically on a basis of the finite state machine (FSM) specification. The proposed hybrid approach harnesses the benefits of hill climbing (Greedy search) and heuristic algorithm. Hill climbing, which exploits domain knowledge, is capable of quickly generating good result however it may get stuck in local minimum. To overcome the problem we used a set of parameters called the seed, which allows the algorithm to generate different results for a different seed. The hill climbing generates solutions implied by the seed while the Genetic Algorithm is used as the seed generator. We compared the hybrid approach with Genetic Algorithm, Simulated Annealing, Greedy Algorithm, and Random Search. The experimental evaluation shows that the proposed hybrid approach outperforms other methods. More specifically, we showed that Genetic Algorithm and Simulated Annealing exhibit similar performance while both of them outperform Greedy Algorithm. Finally, we generalize the proposed hybrid approach to seed-driven hybrid architectures and elaborate on how it can be adopted to a broad range of optimization problems.     

Simulation testing of automata

Although many transducer testing techniques can establish whether a system Imp correctly implements a specification Spec, the notion of 'correctness' used in this context is often rather weak, in that it fails to distinguish correctly between behaviours that are related functionally, but distinct as processes. By appealing to the process-theoretic notion of (strong) simulation, we develop a theory of transducer, process and FSM testing capable of establishing whether Imp is a full simulation of Spec. We show, moreover, that our approach is consistent with top–down integration-testing approaches. Received June 2004 Revised February 2005 Accepted March 2005 by M. Harmann and R. M. Herons     

A parsing automata approach to LR theory

Two simple but powerful tools are introduced in LR theory, viz. item grammars and parsing automata. Parsing automata are used to define a large class of correct prefix parsers operating in linear time. DeRemer's and Pager's parsing methods turn out to be special cases. LL and LC tests, as well as inclusion theorems for the classes of LL, LC, and LR grammars will be based on parsing automata, too.     

A state space approach to the finite automata

This paper proposes a state space approach for analyzing the finite automata. A Ψ-representation transforms a set of words into a formal power series for establishing the state equation of a finite automaton. We investigate the structure of the automaton via its corresponding state equation. It is shown that the solution of the state equation always exists and is unique. Furthermore, we prove that the solution field is a separable algebraic extension of the coefficient field. Finally, the concept of the substitution property of a partition is shown to be equivalent to that of invariant subspaces of the associated state space.     

A novel matrix approach to observability analysis of finite automata

In this paper, the observability of finite automata (acronym is FA) that contain both deterministic finite automata and non-deterministic finite automata is investigated under the framework of the semi-tensor product of matrices. For both initial state and current state cases, two different observability definitions with or without input information are considered, respectively. First, we show that how the observability problem of initial state of FA can be transformed to the construction problem of an initial state-outputs matrix that presents the relationship between initial state and outputs. Second, a current state-outputs matrix to verify the observability problem of current state is given. When two matrices are obtained, four theorems to verify the observability of initial state and current state are presented, respectively. In particular, compared with the existing approach, the proposed approach not only provides a unified verification for the two types of observability of both initial state and current state but also reduces the computational complexity considerably. An illustrative example is presented to show the theoretical results.     

The power of reachability testing for timed automata

The computational engine of the verification tool U consists of a collection of efficient algorithms for the analysis of reachability properties of systems. Model-checking of properties other than plain reachability ones may currently be carried out in such a tool as follows. Given a property φ to model-check, the user must provide a test automaton T_φ for it. This test automaton must be such that the original system S has the property expressed by φ precisely when none of the distinguished reject states of T_φ can be reached in the synchronized parallel composition of S with T_φ. This raises the question of which properties may be analysed by U in such a way. This paper gives an answer to this question by providing a complete characterization of the class of properties for which model-checking can be reduced to reachability testing in the sense outlined above. This result is obtained as a corollary of a stronger statement pertaining to the compositionality of the property language considered in this study. In particular, it is shown that our language is the least expressive compositional language that can express a simple safety property stating that no reject state can ever be reached.

Finally, the property language characterizing the power of reachability testing is used to provide a definition of characteristic properties with respect to a timed version of the ready simulation preorder, for nodes of τ-free, deterministic timed automata.     

A cost-effective approach to testing

A method for assessing the differential risk of failure among a system's modules is proposed. The procedure has three components: external-risk assessment, module exposure, and module-failure likelihood. External-risk assessment is a consideration of the system's environment, almost independent of the software's details. To estimate module exposure, the model relates individual modules and their potential faults to the external-failure modes and their economic consequences by reverse-engineering the specifications and analyzing each module's expected use. To estimate failure likelihood, the method uses a reliability model. The method constitutes theoretical foundation for the cost-effective development of software that attempts to reduce the risk of failure. Managers can use the failure-risk estimates to better determine how much testing effort can be economically justified     

An approach to testing specifications

An approach to testing the consistency of specifications is explored, which is applicable to the design validation of communication protocols and other cases of step-wise refinement. In this approach, a testing module compares a trace of interactions obtained from an execution of the refined specification (e.g., the protocol specification) with the reference specification (e.g., the communication service specification). Nondeterminism in reference specifications presents certain problems. Using an extended finite state transition model for the specifications, a strategy for limiting the amount of nondeterminacy is presented. An automated method for constructing a testing module for a given reference specification is discussed. Experience with the application of this testing approach to the design of a transport protocol and a distributed mutual exclusion algorithm is described.     

Finite automata for testing composition-based reconstructibility of sequences

Symbolic sequences uniquely reconstructible from all their substrings of length k compose a regular factorial language. We thoroughly characterize this language by its minimal forbidden words, and explicitly build up a deterministic finite automaton that accepts it. This provides an efficient on-line algorithm for testing the unique reconstructibility of the sequences.