Binary counting is hard

Prelegent(ci)

Michał Skrzypczak

Afiliacja

MIM UW

Termin

8 marca 2023 14:15

Pokój

p. 5050

Tytuł w języku angielskim

for context-free grammars

Seminarium

Seminarium „Teoria automatów”

---

Michaël Cadilhac recently (on Autoboz) asked the following problem: Take n > 0 and consider the alphabet A_n = { 2^i | i ≤ n }. Let L_n be the set of words over A_n that sum up to 2^n. What is the size of the minimal context-free grammar which recognises L_n? The problem is motivated by linear programs, compression algorithms, and some questions of automata with binary counters. Together with Michaël Cadilhac, Arka Ghosh, and Michał Pilipczuk we managed to provide a handy answer to the problem. During the talk I will just give you the meat, i.e. an argument for lower and upper bounds. In return, I will gladly learn about possible applications of the result :)

---