Search

Deterministic Finite Automaton (DFA) is widely employed in performing fast regular expression matching for numerous network applications. However, constructing DFA recognizing a set of regular expressions is time-consuming especially when the set is huge. In this paper, an improved approach is introduced to accelerate DFA construction based on the hierarchical merging method. The experiments demonstrate that the improved approach proposed in this paper performs about 1.6 to 3.4 times faster than the original hierarchical merging method, and 120 to 1500 times faster than the classical subset construction algorithm.

Regular expression matching is the state of the art in signature based intrusion detection systems. A regular expression matching algorithm used in intrusion detection systems is expected to process data at a speed linear in size of the incoming data and also to be able to run on network devices with limited memory. Traditional DFA and NFA based algorithms fail to meet either of these two requirements. The existing techniques try to either modify a DFA or a NFA, or combine both these to find a trade off between speed and memory requirements. The idea we propose in this paper is orthogonal to existing techniques. We propose a new approach to store a finite automaton in memory which otherwise is stored as a transition table. Our approach can be used by existing algorithms to further reduce the memory requirements with a minimal increase in the processing speed.

Regular expression matching is widely used in many network applications to analyze suspicious traffic against predefined signatures, and to discover anomalous events. Deterministic Finite Automaton (DFA), which recognizes a set of regular expressions, is the basic data structure to scan input traffic byte by byte. Though DFA meets the requirement of real-time processing of network traffic, constructing a combined DFA for a set of regular expression signatures is very time-consuming, especially when the signature set is large. To attack this problem, we propose new strategies to accelerate DFA construction. The basic idea of our method is to construct the combined DFA by hierarchical merging of the DFAs of each single regular expression. Our method runs in $O(|Q| |\Sigma|\ln n)$ time, which is substantially superior to the time complexity $O(|Q| |\Sigma|(\overset{n}{\underset{i=1}{\sum}}|Q_i|)^2)$of classical subset construction algorithm\cite{Aho1986}. Experiment on real signatures from open-source systems, such as L7-filter, BRO and SNORT, demonstrates that our method performs 45 times faster than the subset construction algorithm on average.

In this paper, we discuss the need for efficient approximate string matching. We present the well-known Aho-Corasick automaton for locating multiple patterns and discuss an approach for fuzzification of this automaton. Along with some motivational examples, we propose and illustrate a novel algorithm for automaton construction.

One of the most important issues in top-down cooperative control of multi-agent systems is to decompose the global specification in order to design the local supervisors such that the fulfilment of these sub-specifications by each individual agent, results in the satisfaction of the global specification as a team. Given the global desired behavior, represented as an automaton, and the distribution of its events into local plants, the question is whether it is always possible to decompose the task automaton into a finite number of sub-automata such that the parallel composition of sub-automata is bisimilar to the original task automaton, and if not, what are the necessary and sufficient conditions for such decomposability. It is shown that it is not always possible to do so. We then present the necessary and sufficient conditions for decomposability of a given task automaton such that the parallel composition of these local task automata bisimulates the original task automaton. It is found that the task automaton is decomposable if and only if it satisfies some symmetry properties, representing independence of the order and the choice of private events from different local event sets, and some properties on the interleaving of strings that share the same first appearing common event. This result will help to design the local controllers from the global logical specification, to be used in the top-down cooperative control of distributed systems.

This paper presents the comparison between algorithms used to find inexact motifs (transformed into a set of exact sub-sequences) in a DNA sequence. The MFA algorithm builds an automaton that searches for the set of exact sub-sequences by building a finite automaton in a similar way to the KMP algorithm. This algorithm is compared against the traditional automaton using the basic idea of the subset construction. This traditional algorithm is implemented using some characteristics to increase its performance which will end in an algorithm that can be proven to have the optimal number of states.

We solve the longstanding open problems of the blow-up involved in the translations (when possible) of a nondeterministic B\"uchi word automaton (NBW) to a nondeterministic co-B\"uchi word automaton (NCW)and to a deterministic co-B\"uchi word automaton (DCW). For the NBW to NCW translation, the currently known upper bound is $2^{O(n \log n)}$ and the lower bound is $1.5n$. We improve the upper bound to $n2^n$ and describe a matching lower bound of$2^{\Omega(n)}$. For the NBW to DCW translation, the currently known upper bound is $2^{O(n \log n)}$. We improve it to $2^{O(n)}$, which is asymptotically tight. Both of our upper-bound constructions are based on a simple subset construction, do not involve intermediate automata with richer acceptance conditions, and can be implemented symbolically. We point to numerous applications of the new constructions. In particular, they imply a simple subset-construction based translation(when possible) of LTL to deterministic B\"uchi word automata.

The present paper considers the problem of digital hazards that are present in combinatorial logic structures. My work is focused not on eliminating these hazards but on how to avoid and eventually use this unwanted feature when we are designing a digital automaton. The idea is to theoretically trace the output of the circuit implementing the next state functions of the automaton, determine the time frames when these outputs are logically correct and use those specific moments of time to provoke the automaton's evolution towards the next correct state (according to the automaton's states transitions graph). By doing so we shall drastically improve the working speed of the automaton we design.

A finite automaton consists of a finite set of states and a set of transitions from state to state that occur on input symbols. When the states of a finite automaton are characterized by fuzzy sets, the outputs and transitions are facilitated by appropriate relation, then this finite automaton is called a fuzzy automaton. Two states of fuzzy automaton have similarity relation as they have the similar degree from itself to the final state for any arbitrary input symbol. Based on the clustering technique, we present an algorithm to minimize the states of fuzzy automaton.

Given a timed automaton G accepting the language L/sup T/, a finite state machine G' can be constructed, known as the region automaton, which accepts the untimed language ut(L/sup T/). We construct an alternative finite state machine which also accepts the language ut(L/sup T/), but has fewer states than G'. This is shown for languages of both finite and infinite traces given that the time jump in the transition is strictly positive.

Approximate string matching is a sequential problem and therefore it is possible to solve it using finite automata. A nondeterministic finite automaton is constructed for string matching with k differences. It is shown, how dynamic programming and "shift-and" based algorithms simulate this nondeterministic finite automaton. The corresponding deterministic finite automaton have O((k+2)/sup m-k/*(k+1)!) states, where m is the length of the pattern and k is the number of differences. The time complexity of algorithms based on such deterministic finite automaton is O(n), where n is the length of text.

There are languages which can be recognized by a deterministic (k + 1)-headed oneway finite automaton but which cannot be recognized by a k-headed one-way (deterministic or non-deterministic) finite automaton. Furthermore, there is a language accepted by a 2-headed nondeterministic finite automaton which is accepted by no k-headed deterministic finite automaton.