Narrow Results

The aim of this paper is to compare three efficient representations of the position automaton of a regular expression: the Thompson ∊-automaton, the -structure and the ℱ-structure, an optimization of the -structure. These representations are linear w.r.t. the size s of the expression, since their construction is in O(s) space and time, as well as the computation of the set δ(X,a) of the targets of the transitions by a of any subset X of states. The comparison is based on the evaluation of the number of edges of the underlying graphs respectively created by the construction step or visited by the computation of a set δ(X,a).

Based on recent results from extremal graph theory, we prove that every n-state binary deterministic finite automaton can be converted into an equivalent regular expression of size O(1.742ⁿ) using state elimination. Furthermore, we give improved upper bounds on the language operations intersection and interleaving on regular expressions.

We study the NFA reductions by invariant equivalences and preorders. It is well-known that the NFA minimization problem is PSPACE-complete. Therefore, there have been many approaches to reduce the size of NFAs in low polynomial time by computing invariant equivalence or preorder relation and merging the states within same equivalence class. Here we consider the nondeterminism reduction of NFAs by invariant equivalences and preorders. We, in particular, show that computing equivalence and preorder relation from the left is more useful than the right for reducing the degree of nondeterminism in NFAs. We also present experimental evidence for showing that NFA reduction from the left achieves the better reduction of nondeterminism than reduction from the right.

Developing and maintaining reliable object-oriented software requires a precise understanding of how individual classes must be used. Unfortunately, for many systems, especially those that are large, the available documentation is inadequate. Developers are left with incomplete information concerning the allowable set of call sequences that each class can accommodate. Techniques for reverse engineering this information and presenting it to developers in an intellectually scalable manner are critical.

In this paper, we present four contributions to address this challenge. First, we describe a runtime trace collection system for large C++ applications. Second, we present a methodology for reverse engineering interface protocols from collected trace data. Third, we present a scalable, tunable algorithm for generating compact specifications of these protocols. Finally, we present a detailed case study involving the Mozilla Necko library. We consider popular applications in common use constructed using this library. The results are promising both in terms of the performance of the approach and the utility of the identified protocols.

Several methods have been developed for identifying more or less complex RNA structures in a genome. All these methods are based on the search for conserved primary and secondary sub-structures. In this paper, we present a simple formal representation of a helix, which is a combination of sequence and folding constraints, as a constrained regular expression. This representation allows us to develop a well-founded algorithm that searches for all approximate matches of a helix in a genome. The algorithm is based on an alignment graph constructed from several copies of a pushdown automaton, arranged one on top of another. This is a first attempt to take advantage of the possibilities of pushdown automata in the context of approximate matching. The worst time complexity is O(krpn), where k is the error threshold, n the size of the genome, p the size of the secondary expression, and r its number of union symbols. We then extend the algorithm to search for pseudo-knots and secondary structures containing an arbitrary number of helices.