Home

Пятница 09.12. Galina Jiraskova: " Self-Verifying Finite Automata"

Пятница, 9 декабря, ауд. 311. Начало в 16:00.

Докладчик: Galina Jiraskova (Mathematical Institute Slovak Academy of Sciences).

Тема: Self-Verifying Finite Automata.

Abstract

Consider a nondeterministic finite automaton $ M $ over an alphabet $ \Sigma $,
where the states can be either accepting, rejecting, or neutral. Let $ L_a(M) $ (resp., $ L_r(M) $) be the set of strings taking $ M $ from the start state to an accepting state (resp., rejecting state). Then $ M $ is said to be self-verifying
if $ L_a(M) \cup L_r(M) = \Sigma^* $ and $ L_a(M) \cap L_r(M) = \emptyset $.
That is, the strings reaching an accepting state and the strings reaching a rejecting state form a disjoint partition of $ \Sigma^* $. The language accepted by $ M $ is $ L_a(M) $.

Using a result of Moon, Moser [On cliques in graphs, Israel J. Math. 3, 23--28, 1965], we get an optimal simulation of self-verifying automata by deterministic finite automata. Then we study the complexity of regular operations on languages represented by self-verifying automata, and get the tight upper bounds for union ($ mn $), intersection ($ mn $), reversal ($ 2n+1 $), star ($ {3\over 4}2^n $), left quotient ($ 2^n-1 $), right quotient ($ 3^{n/3} $), and asymptotically tight upper bound for concatenation ($ 3^{m/3}2^n $). Next we prove that given a nondeterministic automaton $ M $ with accepting, rejecting, and neutral states, it is PSPACE-complete to determine if $ M $ is self-verifying. Finally, we study the complexity of the membership, emptiness, universality, and minimization problems for self-verifying automata.