Formal concept analysis applied to pattern matching and automata
Date
2021-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
AFRIKAANSE OPSOMMING: In hierdie proefskrif word die gebruik van formele konsep analise (FKA) ondersoek om patroon passings probleme op te los wat gewoonlik opgelos word deur tegnieke gebaseer op eindige outomate (EO’s). Die probleme wat in detail bespreek is, is 2D-patroonpassing van reglynige objekte, patroon passing op veelvoudige sleutelwoorde en konstruksie van faalings-EO’s. Daarbenewens word bre FKA-gebaseerde benaderings vir die oplos van probleme voorgestel wat die reduksie van nie-deterministiese EO’s tot deterministiese EO’s aanspreek en wat asikliese deterministiese EO-patroon aanpassing aanspreek. Oor die algemeen illustreer die proefskrif dat baie van hierdie patroon passingsprobleme geskik is vir oplossings gebaseer op FKA. Die formele konseprooster wat gebou is om enige van hierdie probleme op te los, sal egter meer inligting bevat as wat nodig is om die betrokke probleem op te los. Alhoewel dit in terme van tyd en ruimte ondoeltreffend mag wees, mag dit ook ’n geleentheid bied wat vir verwante probleme ontgun kan word. Hierdie sake word egter nie empiries in die proefskrif ondersoek nie.
AFRIKAANSE OPSOMMING: In hierdie proefskrif word die gebruik van formele konsep analise (FKA) ondersoek om patroon passings probleme op te los wat gewoonlik opgelos word deur tegnieke gebaseer op eindige outomate (EO’s). Die probleme wat in detail bespreek is, is 2D-patroonpassing van reglynige objekte, patroon passing op veelvoudige sleutelwoorde en konstruksie van faalings-EO’s. Daarbenewens word bre FKA-gebaseerde benaderings vir die oplos van probleme voorgestel wat die reduksie van nie-deterministiese EO’s tot deterministiese EO’s aanspreek en wat asikliese deterministiese EO-patroon aanpassing aanspreek. Oor die algemeen illustreer die proefskrif dat baie van hierdie patroon passingsprobleme geskik is vir oplossings gebaseer op FKA. Die formele konseprooster wat gebou is om enige van hierdie probleme op te los, sal egter meer inligting bevat as wat nodig is om die betrokke probleem op te los. Alhoewel dit in terme van tyd en ruimte ondoeltreffend mag wees, mag dit ook ’n geleentheid bied wat vir verwante probleme ontgun kan word. Hierdie sake word egter nie empiries in die proefskrif ondersoek nie.
Description
Thesis (DPhil)--Stellenbosch University, 2021.
Keywords
Formal Concept Analysis, Pattern Matching, Finite Automata, Optical pattern recognition, Artificial intelligence (AI), Finite automata, Formal methods (Computer Science), Pattern perception, Computer vision, Data mining, Database management, Electronic data processing, UCTD