Formal concept analysis applied to pattern matching and automata

Simple item page
dc.contributor.advisorWatson, B. W.en_ZA
dc.contributor.advisorKourie, D. G.en_ZA
dc.contributor.authorVenter, Frederick Johannesen_ZA
dc.contributor.otherStellenbosch University. Faculty of Arts and Social Sciences. Dept. of Information Science.en_ZA
dc.date.accessioned2021-03-08T13:11:45Z
dc.date.accessioned2021-04-21T14:32:37Z
dc.date.available2021-03-08T13:11:45Z
dc.date.available2021-04-21T14:32:37Z
dc.date.issued2021-03
dc.descriptionThesis (DPhil)--Stellenbosch University, 2021.en_ZA
dc.description.abstractENGLISH 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.en_ZA
dc.description.abstractAFRIKAANSE 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.af_ZA
dc.description.versionDoctoral
dc.format.extentxv. 207 pages : illustrationsen_ZA
dc.identifier.urihttp://hdl.handle.net/10019.1/109932
dc.language.isoen_ZAen_ZA
dc.publisherStellenbosch : Stellenbosch Universityen_ZA
dc.rights.holderStellenbosch Universityen_ZA
dc.subjectFormal Concept Analysisen_ZA
dc.subjectPattern Matchingen_ZA
dc.subjectFinite Automataen_ZA
dc.subjectOptical pattern recognitionen_ZA
dc.subjectArtificial intelligence (AI)en_ZA
dc.subjectFinite automataen_ZA
dc.subjectFormal methods (Computer Science)en_ZA
dc.subjectPattern perceptionen_ZA
dc.subjectComputer visionen_ZA
dc.subjectData miningen_ZA
dc.subjectDatabase managementen_ZA
dc.subjectElectronic data processingen_ZA
dc.subjectUCTD
dc.titleFormal concept analysis applied to pattern matching and automataen_ZA
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
venter_formal_2021.pdf
Size:
1.97 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Plain Text
Description:
Download
Collections
Doctoral Degrees (Information Science)