Doctoral Degrees (Information Science)

Permanent URI for this collection

Now showing 1 - 1 of 1

Formal concept analysis applied to pattern matching and automata
(Stellenbosch : Stellenbosch University, 2021-03) Venter, Frederick Johannes; Watson, B. W.; Kourie, D. G.; Stellenbosch University. Faculty of Arts and Social Sciences. Dept. of Information Science.
ENGLISH ASBSTRACT: This thesis explores the use of formal concept analysis (FCA) to solve pattern matching problems conventionally solved by techniques based on finite au-tomata (FAs). The problems examined in some detail are 2D pattern matching of rectilinear objects, pattern matching on multiple keywords and construction of failure FAs. In addition, broad FCA based approaches to solving problems are proposed that address non-deterministic FA to deterministic FA reduction and that address acyclic deterministic FA pattern matching. Overall, the the-sis illustrates that many of these pattern matching problems are amenable to solutions based on FCA. However, the formal concept lattice built to solve any of these problems will invariably encapsulate more information than what is needed to solve the particular problem at hand. While this might be space/ time inefficient, it might also represent an opportunity to be exploited for associated problems. Neither of these matters are empirically explored in the thesis.