Parikh’s theorem for infinite alphabets

Speaker(s)

Mohnish Pattathurajan

Affiliation

MIM UW

Date

March 17, 2021, 2:15 p.m.

Information about the event

online

Seminar

Seminar Automata Theory

---

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.

---