Пятница, 9 декабря, ауд. 311. Начало в 16:00.
Докладчик: Galina Jiraskova (Mathematical Institute Slovak Academy of Sciences).
Тема: Self-Verifying Finite Automata.
Abstract
Consider a nondeterministic finite automaton
![$ M $](../../../sites/default/files/tex/531315fe6334b9623bff610c29a78eb7de3c2451/index.png)
over an alphabet
![$ \Sigma $](../../../sites/default/files/tex/2a80f2ea35aa3a85d708471a06eb3604f323b8a2/index.png)
,
where the states can be either accepting, rejecting, or neutral. Let
![$ L_a(M) $](../../../sites/default/files/tex/89facea81daee88e8c8f4c06fb4a3ef86f7ab103/index.png)
(resp.,
![$ L_r(M) $](../../../sites/default/files/tex/d91b2f8e48d677f5b1f86831a0a0d840d30bcfdd/index.png)
) be the set of strings taking
![$ M $](../../../sites/default/files/tex/531315fe6334b9623bff610c29a78eb7de3c2451/index.png)
from the start state to an accepting state (resp., rejecting state). Then
![$ M $](../../../sites/default/files/tex/531315fe6334b9623bff610c29a78eb7de3c2451/index.png)
is said to be self-verifying
if
![$ L_a(M) \cup L_r(M) = \Sigma^* $](../../../sites/default/files/tex/990da805f3868efcbeb6e679930d9745bcbc9060/index.png)
and
![$ L_a(M) \cap L_r(M) = \emptyset $](../../../sites/default/files/tex/fd13e29a1455c6d165d1c7b256e4759019de984b/index.png)
.
That is, the strings reaching an accepting state and the strings reaching a rejecting state form a disjoint partition of
![$ \Sigma^* $](../../../sites/default/files/tex/984f70e66dc9024ccbbb7de1f5fd69b38a9e2829/index.png)
. The language accepted by
![$ M $](../../../sites/default/files/tex/531315fe6334b9623bff610c29a78eb7de3c2451/index.png)
is
![$ L_a(M) $](../../../sites/default/files/tex/89facea81daee88e8c8f4c06fb4a3ef86f7ab103/index.png)
.
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 $](../../../sites/default/files/tex/41539a351f76830a154c3f3f6056257e2289eba9/index.png)
), intersection (
![$ mn $](../../../sites/default/files/tex/41539a351f76830a154c3f3f6056257e2289eba9/index.png)
), reversal (
![$ 2n+1 $](../../../sites/default/files/tex/a46a74a73efe3872d56a7e3bc313306bae6ecbeb/index.png)
), star (
![$ {3\over 4}2^n $](../../../sites/default/files/tex/bf44c4bbcdc9179d0d6f16c090e81bc084850d8c/index.png)
), left quotient (
![$ 2^n-1 $](../../../sites/default/files/tex/d05c2f1dbc948ece1f70402dc08c755effad2df9/index.png)
), right quotient (
![$ 3^{n/3} $](../../../sites/default/files/tex/c7327ef98cf9de9f9f1d76de39d777bc3a41f8b6/index.png)
), and asymptotically tight upper bound for concatenation (
![$ 3^{m/3}2^n $](../../../sites/default/files/tex/71c4b0008457b38dbe76eab216543d6042253011/index.png)
). Next we prove that given a nondeterministic automaton
![$ M $](../../../sites/default/files/tex/531315fe6334b9623bff610c29a78eb7de3c2451/index.png)
with accepting, rejecting, and neutral states, it is PSPACE-complete to determine if
![$ M $](../../../sites/default/files/tex/531315fe6334b9623bff610c29a78eb7de3c2451/index.png)
is self-verifying. Finally, we study the complexity of the membership, emptiness, universality, and minimization problems for self-verifying automata.