Combinatorical and Algebraic Structures Seminar

Date:	22.11.2011
Speaker:	Galina Jirásková, MU, Slovenská akadémia vied
Title:	SVFA-to-DFA Conversion and Maximal Cliques in Graphs
Abstract:	In a self-verifying finite automaton (SVFA), computation paths can give three types of answers: yes, no, and I do not know. On every input string, at least one path must give answer yes or no. Furthermore, on the same string, two paths cannot give contradictory answers. SVFAs are as powerful as deterministic finite automata (DFAs); in particular, the standard subset construction can be used to convert them to DFAs. It has been known that every $n$-state SVFA can be simulated by a DFA with $O(2^n/\sqrt{n})$ states. We deepen this result by showing that such an upper bound can be lowered to a function $g(n)$ which grows like $3^{n/3}$ (we give the exact value of the function). To get this upper bound, we use a result from graph theory stating the number of possible maximal cliques in a graph (Moon-Moser, Israel J. Math. 1965). Next we prove the optimality of the new upper bound by showing that for every $n$, there exists a binary language accepted by an n-state SVFA, such that the minimal equivalent DFA must have exactly $g(n)$ states. In the unary case, this upper bound cannot be met.

Return to index.

last update: 27.9.2007, webmaster: Petr Ambrož