Constructing minimal acyclic deterministic finite automata

Show simple item record

dc.contributor.advisor Kourie, Derrick G. en
dc.contributor.postgraduate Watson, Bruce William en
dc.date.accessioned 2013-09-06T15:43:20Z
dc.date.available 2011-06-15 en
dc.date.available 2013-09-06T15:43:20Z
dc.date.created 2011-04-18 en
dc.date.issued 2011-06-15 en
dc.date.submitted 2011-03-30 en
dc.description Thesis (PhD)--University of Pretoria, 2011. en
dc.description.abstract 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> en
dc.description.availability unrestricted en
dc.description.department Computer Science en
dc.identifier.citation Watson, BW 2010, Constructing minimal acyclic deterministic finite automata, PhD thesis, University of Pretoria, Pretoria, viewed yymmdd < http://hdl.handle.net/2263/23648 > en
dc.identifier.other C11/90/ag en
dc.identifier.upetdurl http://upetd.up.ac.za/thesis/available/etd-03302011-195620/ en
dc.identifier.uri http://hdl.handle.net/2263/23648
dc.language.iso en
dc.publisher University of Pretoria en_ZA
dc.rights © 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. en
dc.subject Acyclic finite automata en
dc.subject Minimization en
dc.subject Taxonomy en
dc.subject Algorithmics en
dc.subject Correctness-by-construction en
dc.subject UCTD en_US
dc.title Constructing minimal acyclic deterministic finite automata en
dc.type Thesis en


Files in this item

This item appears in the following Collection(s)

Show simple item record