Efficient automata constructions and approximate automata

Bruce W. Watson; Derrick G. Kourie; Tinus Strauss; Ernest Ketcha Ngassam; Loek G. Cleophas

doi:10.1142/S0129054108005619

Efficient automata constructions and approximate automata

Bruce W. Watson, Derrick G. Kourie, Tinus Strauss, Ernest Ketcha Ngassam, Loek G. Cleophas

Software Engineering and Technology

Research output: Contribution to journal › Article › Academic › peer-review

3 Citations (Scopus)

1 Downloads (Pure)

Abstract

In this paper, we present data structures and algorithms for efficiently constructing approximate automata. An approximate automaton for a regular language L is one which accepts at least L. Such automata can be used in a variety of practical applications, including network security pattern matching, in which false-matches are only a performance nuisance. The construction algorithm is particularly efficient, and is tunable to yield more or less exact automata.

Original language	English
Pages (from-to)	185-193
Number of pages	9
Journal	International Journal of Foundations of Computer Science
Volume	19
Issue number	1
DOIs	https://doi.org/10.1142/S0129054108005619
Publication status	Published - 2008

Access to Document

10.1142/S0129054108005619

Cite this

@article{b3c965252ff54c61b30565825facf6d2,

title = "Efficient automata constructions and approximate automata",

abstract = "In this paper, we present data structures and algorithms for efficiently constructing approximate automata. An approximate automaton for a regular language L is one which accepts at least L. Such automata can be used in a variety of practical applications, including network security pattern matching, in which false-matches are only a performance nuisance. The construction algorithm is particularly efficient, and is tunable to yield more or less exact automata.",

author = "Watson, {Bruce W.} and Kourie, {Derrick G.} and Tinus Strauss and Ngassam, {Ernest Ketcha} and Cleophas, {Loek G.}",

year = "2008",

doi = "10.1142/S0129054108005619",

language = "English",

volume = "19",

pages = "185--193",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific",

number = "1",

}

TY - JOUR

T1 - Efficient automata constructions and approximate automata

AU - Watson, Bruce W.

AU - Kourie, Derrick G.

AU - Strauss, Tinus

AU - Ngassam, Ernest Ketcha

AU - Cleophas, Loek G.

PY - 2008

Y1 - 2008

N2 - In this paper, we present data structures and algorithms for efficiently constructing approximate automata. An approximate automaton for a regular language L is one which accepts at least L. Such automata can be used in a variety of practical applications, including network security pattern matching, in which false-matches are only a performance nuisance. The construction algorithm is particularly efficient, and is tunable to yield more or less exact automata.

AB - In this paper, we present data structures and algorithms for efficiently constructing approximate automata. An approximate automaton for a regular language L is one which accepts at least L. Such automata can be used in a variety of practical applications, including network security pattern matching, in which false-matches are only a performance nuisance. The construction algorithm is particularly efficient, and is tunable to yield more or less exact automata.

U2 - 10.1142/S0129054108005619

DO - 10.1142/S0129054108005619

M3 - Article

SN - 0129-0541

VL - 19

SP - 185

EP - 193

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 1

ER -

Efficient automata constructions and approximate automata

Abstract

Access to Document

Fingerprint

Cite this