For this reason, the number of times for repeating the same query is not taken into account in the complexity of their algorithm. According to this assumption, they assume that the complete set of all possible output sequences is given by the Teacher when applying an input sequence. , in which an algorithm for inferring ONFSMs, namely,, has been proposed based on the hypothesis that the complete testing assumption (called all-weather conditions assumption in ) is satisfied. The closest idea to our approach can be found in the work of El-Fakih et al. This means that, with the same pair of input and output sequences, an ONFSM cannot change to more than one state. An ONFSM could produce different answers to a given input sequence, but its state is uniquely determined by the observation of an input sequence and the corresponding output sequence. We consider here inference for the specific subclass of NFSMs, called observable NFSMs (ONFSMs), which have received much attention in a wide range of test generation methods (e.g., ). For example, residual finite state automata (RFSAs), unambiguous finite automata (UFAs), and parameterized finite state machines (PFSMs) are the subclasses that can be learned efficiently. Although it has been shown that learning the class of NFSMs and non-deterministic finite automata (NFAs) may be impossible, the case is not true for the whole class. The use of a non-deterministic finite state machine (NFSM) is preferred because it can specify both an input/output structure and nondeterminism in a more neutral manner.
Such nondeterminism could arise from the asynchronous communication between different components, as well as from unpredictable activities such as interleaving between components. While the bulk of research in has focused on deterministic models, nondeterminism is not unusual in certain systems that are composed of a number of components such as a communication system, a component-based system, and a service-oriented system. An equivalence query is asked to verify whether a hypothesized DFA is correct. A membership query is asked to investigate whether a given string is actually in the language of the target DFA. There are two types of queries in : membership and equivalence queries. As opposed to a passive learning approach (e.g., RPNI algorithm ), an active learning algorithm can choose and ask the expected queries to the so-called Teacher who is assumed to correctly answer them. Research into, is essentially an active learning procedure (i.e., learning by queries) for inferring a minimal deterministic finite state automaton (DFA). Among various techniques, Angluin’s algorithm has received much attention in many studies. There are many methods that have been reported in the literature for automata learning (see, e.g., evolutionary based algorithms, SAT-solver based algorithm, and ant-colony optimization-based algorithm ). The learning techniques are usually employed for inferring a formal model such as finite state automaton (FA) or finite state machine (FSM) (also called transducer) of a system whose internal behavior is unknown.
#Finite state automata clinical domain verification#
Over the past decade the use of automata learning techniques has become widespread in the domain of formal verification (e.g., ). In addition, experimental results demonstrate the practical efficiency of our approach.
We also present the theoretical time complexity analysis of. Moreover, the proof shows that our algorithm will eventually terminate no matter whether the assumption is fulfilled or not. We have proved that can infer the corresponding ONFSMs of the unknown systems when the number of tries for the same query is adequate to guarantee the complete testing assumption. Instead, it tries to observe the possible output sequences by asking the same query many times to the Teacher. Unlike the previous work, our approach does not require all possible output sequences in one answer. In this paper, we propose, a refined ONFSM learning algorithm that considers the amount for repeating the same query as one parameter. According to this assumption, with an input sequence (query), the complete set of all possible output sequences is given by the so-called Teacher, so the number of times for asking the same query is not taken into account in the algorithm. Recently, an algorithm for inferring observable NFSMs (ONFSMs), which are the potentially learnable subclass of NFSMs, has been proposed based on the hypothesis that the complete testing assumption is satisfied. We consider the problem of learning nondeterministic finite state machines (NFSMs) from systems where their internal structures are implicit and nondeterministic.
0 kommentar(er)
