Generalised acceptance conditions for symmetric difference nondeterministic finite automata
| dc.contributor.advisor | Van Zijl, Lynette | en_ZA |
| dc.contributor.author | Marais, Laurette | en_ZA |
| dc.contributor.other | Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences (Computer Science) | en_ZA |
| dc.date.accessioned | 2018-02-23T06:47:58Z | |
| dc.date.accessioned | 2018-04-09T06:57:56Z | |
| dc.date.available | 2018-02-23T06:47:58Z | |
| dc.date.available | 2018-04-09T06:57:56Z | |
| dc.date.issued | 2018-03 | |
| dc.description | Thesis (PhD)--Stellenbosch University, 2018. | en_ZA |
| dc.description.abstract | ENGLISH ABSTRACT : Symmetric difference nondeterministic finite state automata (XNFA) are an instance of generalised nondeterminism, of which the behaviour is represented by the symmetric difference of all possible computation paths. We introduce the notion of generalised acceptance for XNFA, and investigate descriptional complexity issues related to two specific instances, namely self-verifying XNFA (SV-XNFA) and *- XNFA. For SV-XNFA, we apply self-verifying acceptance, originally defined for typical nondeterministic finite state automata (NFA), to XNFA. Self-verification involves defining a set of accept states, as well as a set of reject states, and requires that the automaton give an explicit accept or reject result on any input. We provide state complexity bounds for determinising unary and non-unary SV-XNFA. We define *-XNFA as XNFA with any finite number of final sets, while * represents a left-associative set operation on the language associated with each set of final states. We investigate and compare the descriptional complexity of various language operations, namely intersection, union, relative complement (or difference), symmetric difference and complement, for unary XNFA and unary *-XNFA. | en_ZA |
| dc.description.abstract | AFRIKAANSE OPSOMMING : Simmetriese verskil nie-deterministiese eindige outomate (XNFA) is ’n instansiëing van veralgemeende nie-determinisme, waarvan die gedrag gekenmerk word deur die simmetriese verskil van alle moontlike berekeningspaaie. Ons definieer veralgemeende aanvaarding vir XNFA en ondersoek aspekte van die beskrywingskompleksiteit van twee spesifieke instansi¨erings daarvan, naamlik self-verifiërende XNFA (SV-XNFA) en *-XNFA. Vir SV-XNFA pas ons self-verifiëring, wat oorspronklik vir tipiese nie-deterministiese eindige outomate (NFA) gedefinieer is, op XNFA toe. Self-verifiëring behels dat ’n versameling aanvaartoestande sowel as ’n versameling verwerpstoestande gedefinieer word, terwyl die vereiste is dat die outomaat enige invoer eksplisiet aanvaar of verwerp. Ons gee toestandskompleksiteitsgrense vir die determinering van unêre en nie-unˆere SV-XNFA. Ons definieer *-XNFA as XNFA met enige eindige aantal versamelings finale toestande, terwyl * enige links-assosiatiewe versamelingsoperasie op die tale wat met die verskeie versamelings aanvaartoestande verband hou, voorstel. Ons ondersoek en vergelyk die beskrywingskompleksiteit van verskeie taaloperasies, naamlik snyding, vereniging, relatiewe komplement (of verskil), simmetriese verskil en komplement, vir unêre XNFA en unêre *-XNFA. | af_ZA |
| dc.format.extent | x, 104 pages : illustrations | en_ZA |
| dc.identifier.uri | http://hdl.handle.net/10019.1/103471 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Stellenbosch : Stellenbosch University | en_ZA |
| dc.rights.holder | Stellenbosch University | en_ZA |
| dc.subject | Formal systems -- Descriptional complexity | en_ZA |
| dc.subject | Finite automata | en_ZA |
| dc.subject | Computer science -- Mathematics | en_ZA |
| dc.subject | Sequential machine theory | en_ZA |
| dc.subject | UCTD | en_ZA |
| dc.subject | Nondeterministic finite automaton | en_ZA |
| dc.subject | Symmetric difference automata | en_ZA |
| dc.title | Generalised acceptance conditions for symmetric difference nondeterministic finite automata | en_ZA |
| dc.type | Thesis | en_ZA |