Doctoral Degrees (Computer Science)

Permanent URI for this collection

Now showing 1 - 1 of 1

Generalised acceptance conditions for symmetric difference nondeterministic finite automata
(Stellenbosch : Stellenbosch University, 2018-03) Marais, Laurette; Van Zijl, Lynette; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences (Computer Science)
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.