Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Generalised acceptance conditions for symmetric difference nondeterministic finite automata
Thesis (PhD)--Stellenbosch University, 2018.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2018
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613958230245376 |
|---|---|
| access_status_str | Open Access |
| author | Marais, Laurette |
| author2 | Van Zijl, Lynette |
| author_browse | Marais, Laurette Van Zijl, Lynette |
| author_facet | Van Zijl, Lynette Marais, Laurette |
| author_sort | Marais, Laurette |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (PhD)--Stellenbosch University, 2018. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/103471 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:44:24.894Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2018 |
| publishDateRange | 2018 |
| publishDateSort | 2018 |
| 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/103471 Generalised acceptance conditions for symmetric difference nondeterministic finite automata Marais, Laurette Van Zijl, Lynette Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences (Computer Science) Formal systems -- Descriptional complexity Finite automata Computer science -- Mathematics Sequential machine theory UCTD Nondeterministic finite automaton Symmetric difference automata Thesis (PhD)--Stellenbosch University, 2018. 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. 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. Doctoral 2018-02-23T06:47:58Z 2018-04-09T06:57:56Z 2018-02-23T06:47:58Z 2018-04-09T06:57:56Z 2018-03 Thesis http://hdl.handle.net/10019.1/103471 en_ZA Stellenbosch University x, 104 pages : illustrations application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Formal systems -- Descriptional complexity Finite automata Computer science -- Mathematics Sequential machine theory UCTD Nondeterministic finite automaton Symmetric difference automata Marais, Laurette Generalised acceptance conditions for symmetric difference nondeterministic finite automata |
| title | Generalised acceptance conditions for symmetric difference nondeterministic finite automata |
| title_full | Generalised acceptance conditions for symmetric difference nondeterministic finite automata |
| title_fullStr | Generalised acceptance conditions for symmetric difference nondeterministic finite automata |
| title_full_unstemmed | Generalised acceptance conditions for symmetric difference nondeterministic finite automata |
| title_short | Generalised acceptance conditions for symmetric difference nondeterministic finite automata |
| title_sort | generalised acceptance conditions for symmetric difference nondeterministic finite automata |
| topic | Formal systems -- Descriptional complexity Finite automata Computer science -- Mathematics Sequential machine theory UCTD Nondeterministic finite automaton Symmetric difference automata |
| url | http://hdl.handle.net/10019.1/103471 |
| work_keys_str_mv | AT maraislaurette generalisedacceptanceconditionsforsymmetricdifferencenondeterministicfiniteautomata |