Home

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

  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-1 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-2 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-3 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-4 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-5 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-6 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-7 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-8 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-9 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-10 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-11 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-12 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-13 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-14 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-15 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-16 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-17 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-18 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-19 has been created.
  • The directory /tmp/drutex-84f07e637b420a0ea37d8d7db73def04-20 has been created.

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

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

Тема: Self-Verifying Finite Automata.

Abstract

Consider a nondeterministic finite automaton TeX Embedding failed! over an alphabet TeX Embedding failed!,
where the states can be either accepting, rejecting, or neutral. Let TeX Embedding failed! (resp., TeX Embedding failed!) be the set of strings taking TeX Embedding failed! from the start state to an accepting state (resp., rejecting state). Then TeX Embedding failed! is said to be self-verifying
if TeX Embedding failed! and TeX Embedding failed!.
That is, the strings reaching an accepting state and the strings reaching a rejecting state form a disjoint partition of TeX Embedding failed!. The language accepted by TeX Embedding failed! is TeX Embedding failed!.

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 (TeX Embedding failed!), intersection (TeX Embedding failed!), reversal (TeX Embedding failed!), star (TeX Embedding failed!), left quotient (TeX Embedding failed!), right quotient (TeX Embedding failed!), and asymptotically tight upper bound for concatenation (TeX Embedding failed!). Next we prove that given a nondeterministic automaton TeX Embedding failed! with accepting, rejecting, and neutral states, it is PSPACE-complete to determine if TeX Embedding failed! is self-verifying. Finally, we study the complexity of the membership, emptiness, universality, and minimization problems for self-verifying automata.