Generalised acceptance conditions for symmetric difference nondeterministic finite automata
Date
2018-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
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.
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.
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.
Description
Thesis (PhD)--Stellenbosch University, 2018.
Keywords
Formal systems -- Descriptional complexity, Finite automata, Computer science -- Mathematics, Sequential machine theory, UCTD, Nondeterministic finite automaton, Symmetric difference automata