Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Formal concept analysis applied to pattern matching and automata
Thesis (DPhil)--Stellenbosch University, 2021.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2021
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613893802590208 |
|---|---|
| access_status_str | Open Access |
| author | Venter, Frederick Johannes |
| author2 | Watson, B. W. |
| author_browse | Venter, Frederick Johannes Watson, B. W. |
| author_facet | Watson, B. W. Venter, Frederick Johannes |
| author_sort | Venter, Frederick Johannes |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (DPhil)--Stellenbosch University, 2021. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/109932 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:43:23.129Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2021 |
| publishDateRange | 2021 |
| publishDateSort | 2021 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/109932 Formal concept analysis applied to pattern matching and automata Venter, Frederick Johannes Watson, B. W. Kourie, D. G. Stellenbosch University. Faculty of Arts and Social Sciences. Dept. of Information Science. 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 Thesis (DPhil)--Stellenbosch University, 2021. 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. Doctoral 2021-03-08T13:11:45Z 2021-04-21T14:32:37Z 2021-03-08T13:11:45Z 2021-04-21T14:32:37Z 2021-03 Thesis http://hdl.handle.net/10019.1/109932 en_ZA Stellenbosch University xv. 207 pages : illustrations application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | 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 Venter, Frederick Johannes Formal concept analysis applied to pattern matching and automata |
| title | Formal concept analysis applied to pattern matching and automata |
| title_full | Formal concept analysis applied to pattern matching and automata |
| title_fullStr | Formal concept analysis applied to pattern matching and automata |
| title_full_unstemmed | Formal concept analysis applied to pattern matching and automata |
| title_short | Formal concept analysis applied to pattern matching and automata |
| title_sort | formal concept analysis applied to pattern matching and automata |
| topic | 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 |
| url | http://hdl.handle.net/10019.1/109932 |
| work_keys_str_mv | AT venterfrederickjohannes formalconceptanalysisappliedtopatternmatchingandautomata |