Composite automata

Speaker(s)

Ismaël Jecker

Affiliation

MIM UW

Date

Dec. 1, 2021, 2:15 p.m.

Information about the event

online

Seminar

Seminar Automata Theory

---

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

---