Regular expressions for data words

Speaker(s)

Mikołaj Bojańczyk

Affiliation

MIM UW

Date

Nov. 4, 2020, 2:15 p.m.

Information about the event

Online

Seminar

Seminar Automata Theory

---

I will discuss a proposal (one of many others) for regular expressions that use infinite alphabets. The regular expressions describe exactly the languages that can be recognised by nondeterministic orbit-finite automata (equivalently, nondeterministic register automata). The basic idea is to consider expressions that describe not just words, but words with side effects that are atom permutations.

---