Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Constructing minimal acyclic deterministic finite automata
Thesis (PhD)--University of Pretoria, 2010.
Saved in:
| Other Authors: | |
|---|---|
| Format: | Thesis |
| Published: |
University of Pretoria
2013
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613701005115393 |
|---|---|
| access_status_str | Open Access |
| author2 | Kourie, Derrick G. |
| author_browse | Kourie, Derrick G. |
| author_facet | Kourie, Derrick G. |
| collection | Thesis |
| dc_rights_str_mv | © 2010 University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. |
| description | Thesis (PhD)--University of Pretoria, 2010. |
| format | Thesis |
| id | oai:repository.up.ac.za:2263/23648 |
| institution | University of Pretoria (South Africa) |
| last_indexed | 2026-06-10T12:40:19.405Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UPSpace — University of Pretoria Institutional Repository |
| publishDate | 2013 |
| publishDateRange | 2013 |
| publishDateSort | 2013 |
| publisher | University of Pretoria |
| publisherStr | University of Pretoria |
| record_format | dspace |
| source_str | UPSpace — University of Pretoria Institutional Repository |
| spelling | oai:repository.up.ac.za:2263/23648 Constructing minimal acyclic deterministic finite automata Kourie, Derrick G. bruce@fastar.org Watson, Bruce William Acyclic finite automata Minimization Taxonomy Algorithmics Correctness-by-construction UCTD Thesis (PhD)--University of Pretoria, 2010. This thesis is submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Ph.D) in the FASTAR group of the Department of Computer Science, University of Pretoria, South Africa. I present a number of algorithms for constructing minimal acyclic deterministic finite automata (MADFAs), most of which I originally derived/designed or co-discovered. Being acyclic, such automata represent finite languages and have proven useful in applications such as spellchecking, virus-searching and text indexing. In many of those applications, the automata grow to billions of states, making them difficult to store without using various compression techniques — the most important of which is minimization. Results from the late 1950’s show that minimization yields a unique automaton (for a given language), and later results show that minimization of acyclic automata is possible in time linear in the number of states. These two results make for a rich area of algorithmics research; automata and algorithmics research are relatively old fields of computing science and the discovery/invention of new algorithms in the field is an exciting result. I present both incremental and nonincremental algorithms. With nonincremental techniques, the unminimized acyclic deterministic finite automaton (ADFA) is first constructed and then minimized. As mentioned above, the unminimized ADFA can be very large indeed — often even too large to fit within the virtual memory space of the computer. As a result, incremental techniques for minimization (i.e. the ADFA is minimized during its construction) become interesting. Incremental algorithms frequently have some overhead: if the unminimized ADFA fits easily within physical memory, it may still be faster to use nonincremental techniques. The presentation used in this thesis has a few unusual characteristics: <ul><li> Few other presentations follow a correctness-by-construction style for presenting and deriving algorithms. The presentations given here include correctness arguments or sketches thereof. </li><li> The presentation is taxonomic — emphasizing the similarities and differences between the algorithms at a fundamental level. </li><li> While it is possible to present these algorithms in a formal-language-theoretic setting, this thesis remains somewhat closer to the actual implementation issues. </li><li> In several chapters, new algorithms and interesting new variants of existing algorithms are presented. </li><li> It gives new presentations of many existing algorithms — all in a common format with common examples. </li><li> There are extensive links to the existing literature. </li></ul> Computer Science unrestricted 2013-09-06T15:43:20Z 2011-06-15 2013-09-06T15:43:20Z 2011-04-18 2010 2011-03-30 Thesis Watson, BW 2010, Constructing minimal acyclic deterministic finite automata, PhD thesis, University of Pretoria, Pretoria, viewed yymmdd < http://hdl.handle.net/2263/23648 > C11/90/ag http://hdl.handle.net/2263/23648 http://upetd.up.ac.za/thesis/available/etd-03302011-195620/ © 2010 University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. application/pdf University of Pretoria |
| spellingShingle | Acyclic finite automata Minimization Taxonomy Algorithmics Correctness-by-construction UCTD Constructing minimal acyclic deterministic finite automata |
| title | Constructing minimal acyclic deterministic finite automata |
| title_full | Constructing minimal acyclic deterministic finite automata |
| title_fullStr | Constructing minimal acyclic deterministic finite automata |
| title_full_unstemmed | Constructing minimal acyclic deterministic finite automata |
| title_short | Constructing minimal acyclic deterministic finite automata |
| title_sort | constructing minimal acyclic deterministic finite automata |
| topic | Acyclic finite automata Minimization Taxonomy Algorithmics Correctness-by-construction UCTD |
| url | http://hdl.handle.net/2263/23648 http://upetd.up.ac.za/thesis/available/etd-03302011-195620/ |