Parikh’s theorem for infinite alphabets

Prelegent(ci)

Mohnish Pattathurajan

Afiliacja

MIM UW

Termin

17 marca 2021 14:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium „Teoria automatów”

---

We investigate commutative images (Parikh Images) of languages recognised by register automata and grammars. Semi-linear and rational sets can be naturally extended to this setting by allowing for orbit-finite unions instead of finite ones. We prove the following. 1. Parikh Images of one-register automata are not always semi-linear but are rational 2. We extend the above result to one-register context-free grammar. We also conjecture the same holds for automata and grammars for arbitrarily many registers. This is joint work with Piotr Hofman, Marta Juzepczuk, and Sławek Lasota.

---