Conference Papers / Poster Papers

download

TABASCO: a Taxonomy-based Domain Engineering Method

Loek Cleophas, Bruce W. Watson, Derrick G. Kourie and Andrew Boake 2005/09 - Conference Paper

Proceedings of SAICSIT 2005, Annual Conference of the South African Institute of Computer Scientists and Information Technologists, White River, Mpumalanga, South Africa, September 2005, pp. 38-47.

(show/hide) Abstract

We discuss TABASCO, a method for constructing Domain-Specific Toolkits (DSTs). We present TABASCO in the context of domain engineering and generative programming. We discuss the steps of TABASCO in detail, with a focus on the software construction side, giving examples based on actual applications of the method. In doing so, we show that TABASCO is a domain engineering method aimed at a particular kind of software domain, and how this method is applied in practice.

download

A missing link in root-to-frontier tree pattern matching

Loek G.W.A. Cleophas, Kees Hemerik and Gerard Zwaan 2005/08 - Conference Paper

Proceedings of the Prague Stringology Conference '05, Czech Technical University, Prague, Czech Republic, August 2005.

(show/hide) Abstract

Tree pattern matching (tpm) algorithms play an important role in practical applications such as compilers and XML document validation. Many tpm algorithms based on tree automata have appeared in the literature. For reasons of efficiency, these automata are preferably deterministic. Deterministic root-to-frontier tree automata (drftas) are less powerful than nondeterministic ones, and no root-to-frontier tpm algorithm using drftas has appeared so far. Hoffmann & O’Donnell [HO82] presented a root-to-frontier tpm algorithm based on an Aho-Corasick automaton recognizing tree stringpaths, but no relationship between this algorithm and algorithms using tree automata has been described. In this paper, we show that a specific drfta can be used for stringpath matching in a root-to-frontier tpm algorithm. This algorithm has not appeared in the literature before, and provides a missing link between tpm algorithms using stringpath automata and those using tree automata.

download

Reordering Finite Automata States for Fast String Recognition

Ernest Ketcha Ngassam, Derrick G. Kourie, Bruce W. Watson 2005/08 - Conference Paper

Proceedings of the Prague Stringology Conference '05, Czech Technical University, Prague, Czech Republic, August 2005.

(show/hide) Abstract

The spatial and temporal locality of reference on which cache memory relies to minimize cache swaps, is exploited to design a new algorithm for finite automaton string recognition. It is shown that the algorithm, referred to as the state reordering algorithm, outperforms the traditional table-driven algorithm for strings that tend to repeatedly access the same set of states.

download

Automaton-based sublinear keyword pattern matching

Loek Cleophas, Bruce W. Watson and Gerard Zwaan 2004/10 - Conference Paper

Proceedings of the the 11th International Symposium on String Processing and Information Retrieval (SPIRE 2004), University of Padova, Padova, Italy, October 5-8, 2004, Lecture Notes in Computer Science 3246, Springer, October 2004, pp. 18-30.

(show/hide) Abstract

We show how automaton-based sublinear keyword pattern matching (skpm) algorithms appearing in the literature can be seen as different instantiations of a general automaton-based skpm algorithm skeleton. Such algorithms use finite automata (FA) for efficient computation of string membership in a certain language. The algorithms were formally derived as part of a new skpm algorithm taxonomy, based on an earlier suffix-based skpm algorithm taxonomy [1]. Such a taxonomy is based on deriving the algorithms from a common starting point by successively adding algorithm and problem details and has a number of advantages. It provides correctness arguments, clarifies the working of the algorithms and their interrelationships, helps in implementing the algorithms, and may lead to new algorithms being discovered by finding gaps in the taxonomy. We show how to arrive at the general algorithm skeleton and derive some instantiations, leading to well-known factor- and factor oracle-based algorithms. In doing so, we show the shift functions used for them can be (strengthenings of) shift functions used for suffix-based algorithms. This also results in a number of previously undescribed factor-based skpm algorithm variants, whose performance remains to be investigated. [1] B. W. Watson and G. Zwaan. A taxonomy of sublinear multiple keyword pattern matching algorithms. Science of Computer Programming, 27(2):85-118, 1996.

download

A Framework for the Dynamic Implementation of Finite Automata for Performance Enhancement

Ernest Ketcha Ngassam, Bruce W. Watson and Derrick G. Kourie 2004/08 - Conference Paper

Proceedings of the Prague Stringology Conference '04, Czech Technical University, Prague, Czech Republic, August 2004.

(show/hide) Abstract

The aim of this work is to provide a model for the dynamic implementation of finite automata for enhanced performance. Investigations have shown that hardcoded finite automata outperforms the traditional table-driven implementation up to some threshold. Moreover, the kind of string being recognized plays a major role in the overall processing speed of the string recognizer. Various experiments are depicted to show when the advantages of using hardcoding as basis for implementing finite automata (instead of using the classical table-driven approach) become manifest. The model, a dynamic algorithm that combines both hardcoding and table-driven is introduced.

download

Combining regular expressions with (near-)optimal Brzozowski automata

Michiel Frishert and Bruce W. Watson 2004/07 - Poster Paper

Proceedings of the 9th International Conference on Implementation and Application of Automata (CIAA 2004), Kingston, ON, Canada, July 22-24, 2004, Lecture Notes in Computer Science 3317, Springer, December 2004, pp. 319-320.

(show/hide) Abstract

Derivatives of regular expressions were first introduced by Brzozowski in [1]. By recursively computing all derivatives of a regular expression, and associating a state with each unique derivative, a deterministic finite automaton can be constructed. Convergence of this process is guaranteed if uniqueness of regular expressions is recognized modulo associativity, commutativity, and idempotence of the union operator. Additionaly, through simplification based on the identities for regular expressions, the number of derivatives can be further reduced. [1] J.A. Brzozowski. Derivatives of regular expressions. Communications of the ACM,11:481-494, 1964.

download

FIRE Station: An environment for manipulating finite automata and regular expression views

Michiel Frishert, Loek Cleophas and Bruce W. Watson 2004/07 - Conference Paper

Proceedings of the 9th International Conference on Implementation and Application of Automata (CIAA 2004), Kingston, ON, Canada, July 22-24, 2004, Lecture Notes in Computer Science 3317, Springer, December 2004, pp. 125-133.

(show/hide) Abstract

We discuss a new tool, FIRE Station, for the visualization, exploration and manipulation of regular languages and their various representations, including regular expressions and finite state automata.

download

Constructing Factor Oracles

Loek Cleophas, Gerard Zwaan, and Bruce W. Watson 2003/09 - Conference Paper

M. Simanek (ed.), Proceedings of the Prague Stringology Conference '03, Czech Technical University, Prague, Czech Republic, September 2003, pp. 37-50.

(show/hide) Abstract

A factor oracle is a data structure for weak factor recognition. It is an automaton built on a string p of length m that is acyclic, recognizes at least all factors of p, has m+1 states which are all final, and has m to 2m-1 transitions. In this paper, we give two alternative algorithms for its construction and prove the constructed automata to be equivalent to the automata constructed by the algorithms in [1]. Although these new O(m^2) algorithms are practically inefficient compared to the O(m) algorithm given in [1], they give more insight into factor oracles. Our first algorithm constructs a factor oracle based on the suffixes of p in a way that is more intuitive. Some of the crucial properties of factor oracles, which in [1] need several lemmas to be proven, are immediately obvious. Another important property however becomes less obvious. A second algorithm gives a clear insight in the relationship between the trie or dawg recognizing the factors of p and the factor oracle recognizing a superset thereof. We conjecture that an O(m) version of this trie-based algorithm exists. [1] Cyril Allauzen, Maxime Crochemore, and Mathieu Raffinot. Efficient Experimental String Matching by Weak Factor Recognition. In Proceedings of the 12th conference on Combinatorial Pattern Matching, volume 2089 of LNCS, pages 51-72, 2001.

download

Hardcoding Finite State Automata Processing

E. Ketcha Ngassam, Bruce W. Watson and Derrick G. Kourie 2003/09 - Conference Paper

Proceedings of SAICSIT 2003, Annual Conference of the South African Institute of Computer Scientists and Information Technologists, Fourways, South Africa, September 2003, pp. 111-121.

(show/hide) Abstract

To hardcode and algorithm means to build into it the data that it requires. In this paper, we present various experiments in hardcoding the transition table of a finite state machine directly into string-recognizing code. Experiments are carried out in two phases. The first phase is limited to the analysis of the hardcoded behavior in relation to acceptance or rejection of a single symbol in some arbitrary state of some finite automaton. Then follows a simulation of the analysis of some hardcoded solution for recognizing an entire string. Measurements are provided to show the time efficiency gains by various hardcoded versions over the traditional table-driven approach.

download

Stretching and Jamming of Automata

Noud de Beijer, Bruce W. Watson and Derrick G. Kourie 2003/09 - Conference Paper

Proceedings of SAICSIT 2003, Annual Conference of the South African Institute of Computer Scientists and Information Technologists, Fourways, South Africa, September 2003, pp. 1-10.

(show/hide) Abstract

In this paper we present two transformations on automata, called stretching and jamming. These transformations will, under certain conditions, reduce the size of the transition table, and under other conditions reduce the string recognition time. Given a deterministic finite automaton, we can stretch it by transforming each single transition into two or more sequential transitions, thereby introducing additional intermediate states. Jamming is the opposite transformation, in which two or more successive transitions are transformed into a single transition, thereby removing redundant intermediate states. We will present formal definitions of stretching and jamming. We will give algorithms for stretching and jamming and we will calculate theoretical bounds, when stretching/jamming is effective in terms of memory consumption and string recognition time.

download

The Effect of Rewriting Regular Expressions on Their Accepting Automata

Michiel Frishert, Loek G. Cleophas, and Bruce W. Watson 2003/07 - Poster Paper

Oscar H. Ibarra and Zhe Dang (eds.), Proceedings of the 8th International Conference on Implementation and Application of Automata (CIAA 2003), Santa Barbara, California, USA, July 16-18, 2003, Lecture Notes in Computer Science 2759, Springer, July 2003, pp. 304-305.

(show/hide) Abstract

Traditionally, regular expressions are transformed into (deterministic) finite automata, which are then used in, for example, searching and parsing. For every automaton, there is an infinite number of other automata that recognize exactly the same language, although memory usage and performance can differ. This has lead to the widespread use of automata minimization techniques. In the same way, for every regular expression, there exists an infinite number of equivalent regular expressions, some of which lead to smaller/faster automata. This paper compares automaton sizes constructed from 10 different regular expressions, both before and after the rewriting transformation. Rewriting is done based on a rule set directly derived from the regular expression language (i.e. Kleene Algebra) axioms.

download

Preliminary Experiments in Hardcoding Finite Automata

E. Ketcha Ngassam, Bruce W. Watson, and Derrick G. Kourie 2003/07 - Poster Paper

Oscar H. Ibarra and Zhe Dang (eds.), Proceedings of the 8th International Conference on Implementation and Application of Automata (CIAA 2003), Santa Barbara, California, USA, July 16-18, 2003, Lecture Notes in Computer Science 2759, Springer, July 2003, pp. 299-300.

(show/hide) Abstract

Various experiments in hardcoding a single row of a transition table of a finite state machine directly into symbol-recognizing code are presented. Measurements are provided to show the time efficiency gains by various hardcoded versions over the traditional table-driven algorithm.

download

An incremental DFA minimization algorithm

Bruce W. Watson 2001/08 - Conference Paper

Lauri Karttunen, Kimmo Koskenniemi and Gertjan van Noord (eds.), Proceedings of the Second International Workshop on Finite State Methods in Natural Language Processing, Helsinki, Finland, August 2001.

(show/hide) Abstract

In this paper, we present a new deterministic finite automata minimization algorithm. The algorithm is incremental---it may be halted at any time, yielding a partially-minimized automaton. All of the other (known) minimization algorithms have intermediate results which are not useable for partial minimization.

download

A new family of Commentz-Walter-style multiple keyword pattern matching algorithms

Bruce W. Watson 2000/09 - Conference Paper

Borivoj Melichar (ed.), Proceedings of the Fifth Prague Stringologic Workshop, Bratislava, Slovakia / Czech Technical University, Prague, Czech Republic, September 2000, pp. 71-76.

download

Directly Constructing Minimal DFAs: Combining Two Algorithms by Brzozowski

Bruce W. Watson 2000/07 - Conference Paper

Sheng Yu and Andre Paun (eds.), Proceedings of the Fifth Conference on Implementation and Application of Automata (CIAA 2000), London, Ontario, Canada, July 2000, Lecture Notes in Computer Science 2088, Springer, July 2000, pp. 311-317.

(show/hide) Abstract

In this paper, we combine (and refine) two of Brzozowski's algorithms -- yielding a single algorithm which constructs a minimal deterministic finite automaton (DFA) from a regular expression.

A history of Brzozowski's DFA minimization algorithm

Bruce W. Watson 2000/07 - Poster Paper

Sheng Yu and Andre Paun (eds.), Proceedings of the Fifth Conference on Implementation and Application of Automata (CIAA 2000), London, Ontario, Canada, July 2000, Lecture Notes in Computer Science 2088, Springer, July 2000.

A taxonomy of algorithms for constructing minimal acyclic deterministic automata.

Bruce W. Watson 1999/07 - Conference Paper

Helmut Jürgensen (ed.), Proceedings of the Fourth Workshop on Implementing Automata (WIA 99), Potsdam, Germany, July 1999, Lecture Notes in Computer Science 2214, Springer, 2001, pp. 174-182.

The OpenFIRE initiative

Bruce W. Watson 1999/03 - Conference Paper

Jun-Ichi Aoe (ed.), Proceedings of the International Conference on Computer Processing of Oriental Languages, Tokushima, Japan, March 1999, volume 2, pp. 421-424.

A fast new semi-incremental algorithm for the construction of minimal acyclic DFAs

Bruce W. Watson 1998/09 - Conference Paper

Derick Wood and Denis Maurel (eds.), Proceedings of the Third Workshop on Implementing Automata (WIA 98), Rouen, France, September 1998, Lecture Notes in Computer Science 1660, Springer, 1999, pp. 91-98.

download

An early-retirement plan for the states

Bruce W. Watson 1998/09 - Conference Paper

Jan Holub (ed.), Proceedings of the Third Prague Stringologic Workshop, Czech Technical University, Prague, Czech Republic, September 1998, pp. 119-124.

(show/hide) Abstract

New applications of finite automata, such as NLP and asynchronous circuit simulation, can require automata of millions or even billions of states. All known construction methods (in particular, the interesting reachability-based ones that save memory, such as the subset construction, and simultaneously minimizing constructions, such as Brzozowski's) have intermediate memory usage much larger than the final automaton, thereby restricting the maximum size of the automata which can be built. In this paper, we present a reachability-based optimization which can be used in any one of the construction algorithms to reduce the intermediate memory requirements. The optimization is presented in conjunction with an easily understood (and implemented) canonical automaton construction algorithm.

Incremental Construction of Minimal Acyclic Finite State Automata and Transducers

Jan Daciuk, Bruce W. Watson, and Richard E. Watson 1998/06 - Conference Paper

Lauri Karttunen and Kemal Oflazer (eds.), Proceedings of the International Workshop on Finite State Methods in Natural Language Processing, Ankara, Turkey, June 1998, pp. 48-56.

Practical optimizations for automata

Bruce W. Watson 1997/09 - Conference Paper

Derick Wood and Sheng Yu (eds.), Proceedings of the Second Workshop on Implementing Automata (WIA 97), London, Ontario, Canada, September 1997, Lecture Notes in Computer Science 1436, Springer, 1998, pp. 232-240.

download

A Boyer-Moore (or Watson-Watson) type algorithm for regular tree pattern matching

Bruce W. Watson 1997/07 - Conference Paper

Jan Holub (ed.), Proceedings of the Second Prague Stringologic Workshop, Czech Technical University, Prague, Czech Republic, July 1997, pp. 33-38.

(show/hide) Abstract

In this paper, I outline a new algorithm for regular tree pattern matching. The Boyer-Moore family of string pattern matching algorithm sare considered to be among the most efficient. The Boyer-Moore idea of a shift distance was generalized by Commentz-Walter for multiple keywords, and generalizations for regular expressions have also been found. The existence of a further generalization to tree pattern matching was first mentioned in the statements accompanying my dissertation.

download

A new family of string pattern matching algorithms

Bruce W. Watson and Richard E. Watson 1997/07 - Conference Paper

Jan Holub (ed.), Proceedings of the Second Prague Stringologic Workshop, Czech Technical University, Prague, Czech Republic, July 1997, pp. 12-23.

(show/hide) Abstract

Even though the field of pattern matching has been well studied, there are still many interesting algorithms to be discovered. In this paper, we present a new family of single keyword pattern matching algorithms. We begin by deriving a common ancestor algorithm, which naively solves the problem. Through a series of correctness preserving predicate strengthenings, and implementation choices, we derive efficient variants of this algorithm. This paper also presents one of the first algorithms which could be used to do a minimal number of match attempts within the input string (by maintaining as much information as possible from each match attempt).

download

SPARE Parts: A C++ toolkit for String PAttern REcognition

Bruce W. Watson 1997/07 - Conference Paper

Jan Holub (ed.), Proceedings of the Second Prague Stringologic Workshop, Czech Technical University, Prague, Czech Republic, July 1997, pp. 47-60.

(show/hide) Abstract

In this paper, we consider the design and implementation of SPARE Parts, a C++ toolkit for pattern matching. SPARE Parts is the second generation string pattern matching toolkit from the Ribbit Software Systems Inc. and the Eindhoven University of Technology. The toolkit contains implementations of the well-known Knuth-Morris-Pratt, Boyer-Moore, Aho-Corasick and Commentz-Walter algorithms (and their variants).The toolkit is publicly available (though it is not in the public domain and it may not be redistributed) for noncommercial use. A totally re-implemented toolkit, known as SPARE Parts II, is available for commercial licensing from Ribbit Software Systems Inc. In addition to the functionality of SPARE Parts, itcontains approximate pattern matchers, regular pattern matchers, multi-dimensional pattern matchers, and a highly tuned set of foundation classes.

A new regular grammar pattern matching algorithm

Bruce W. Watson 1996/09 - Conference Paper

J. Diaz and M. Serna (eds.), Proceedings of the European Symposium on Algorithms, Barcelona, Spain, September 1996, Lecture Notes in Computer Science 1136, Springer, August 1996, pp. 364-377

download

A collection of new regular grammar pattern matching algorithms

Bruce W. Watson 1996/08 - Conference Paper

Jan Holub (ed.), Proceedings of the First Prague Stringologic Workshop, Czech Technical University, Prague, Czech Republic, August 1996, pp. 64-83.

(show/hide) Abstract

A number of new algorithms for regular grammar pattern matching is presented. The new algorithms handle patterns specified by regular grammars - a generalization of multiple keyword pattern matching and single keyword pattern matching, both considered extensively in and [14, Chapter 4] and in [18]. Among the algorithms is a Boyer-Moore type algorithm for regular grammar pattern matching, answering a variant of an open problem posed by A.V. Aho in 1980 [2, p. 342]. Like the Boyer-Moore and Commentz-Walter algorithms, the generalized algorithm makes use of shift functions which can be precomputed and tabulated. It appears that many of the new algorithms can be efficiently implemented. [2] A.V. Aho. Pattern matching in strings. In R.V. Book, ed., Formal Language Theory: Perspectives and Open Problems, pages 325-347, Academic Press, New York, 1980. [14] B.W. Watson. Taxonomies and Toolkits of Regular Language Algorithms. PhD thesis, Faculty of Computing Science, Eindhoven University of Technology, The Netherlands, September 1995. [18] B. W. Watson and G. Zwaan. A taxonomy of keyword pattern matching algorithms. Computing Science Report 92/27, Faculty of Computing Science, Eindhoven University of Technology, 1992.

The FIRE Lite: FAs and REs in C++

Bruce W. Watson 1996/08 - Conference Paper

Darrell Raymond, Derick Wood, and Sheng Yu (eds.), Proceedings of the First Workshop on Implementing Automata (WIA 96), London, Ontario, Canada, August 1996, Lecture Notes in Computer Science 1260, Springer, August 1996, pp. 167-188

Implementing and using finite automata toolkits

Bruce W. Watson 1996/08 - Conference Paper

András Kornai (ed.), Proceedings of the Twelfth European Conference on Artificial Intelligence, Budapest, Hungary, August 1996, pp. 97-100.

The performance of single and multiple keyword pattern matching algorithms

Bruce W. Watson 1996/08 - Conference Paper

Nivio Ziviani, Ricardo Baeza-Yates, and Katia Guimaraes (eds.), Proceedings of the Third South American Workshop on String Processing, Recife, Brazil, August 1996, International Informatics Series 4, Carleton University Press, pp. 280-294.

A taxonomy of keyword pattern matching algorithms

Bruce W. Watson and Gerard Zwaan 1993/11 - Conference Paper

Harry Wijshoff (ed.), Proceedings of the Symposium on Computing Science in the Netherlands, Utrecht, The Netherlands, November 1993, pp. 25-39.