Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów


Composite automata

Prelegent: Ismaël Jecker

2021-12-01 14:15

A finite automaton A is called composite if there exist automata A1, A2, . . . , Ak smaller than A such that the language of A is equal to the intersection of the languages of the Ai. Otherwise, A is prime. This notion of primality was introduced by Orna Kupferman and Jonathan Mosheiff in 2015, but the exact complexity of the Decomposition Problem, that asks whether a given automaton is composite, is still open with a doubly-exponential gap between the upper and lower bounds. In this talk, I will present some recent results concerning primality of permutation automata (i.e. automata whose transition monoid is a group).