Generalised acceptance conditions for symmetric difference nondeterministic finite automata

[摘要] ENGLISH ABSTRACT : Symmetric difference nondeterministic finite state automata (XNFA) are an instanceof generalised nondeterminism, of which the behaviour is represented by the symmetricdifference of all possible computation paths. We introduce the notion ofgeneralised acceptance for XNFA, and investigate descriptional complexity issuesrelated to two specific instances, namely self-verifying XNFA (SV-XNFA) and *-XNFA.For SV-XNFA, we apply self-verifying acceptance, originally defined for typicalnondeterministic finite state automata (NFA), to XNFA. Self-verification involvesdefining a set of accept states, as well as a set of reject states, and requires that theautomaton give an explicit accept or reject result on any input. We provide statecomplexity bounds for determinising unary and non-unary SV-XNFA.We define *-XNFA as XNFA with any finite number of final sets, while * representsa left-associative set operation on the language associated with each set offinal states. We investigate and compare the descriptional complexity of various languageoperations, namely intersection, union, relative complement (or difference),symmetric difference and complement, for unary XNFA and unary *-XNFA.

[发布机构] Stellenbosch University