Composite automata

Prelegent(ci)

Ismaël Jecker

Afiliacja

MIM UW

Termin

1 grudnia 2021 14:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium „Teoria automatów”

---

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).

---