for context-free grammars

Speaker(s)

Michał Skrzypczak

Affiliation

MIM UW

Date

March 8, 2023, 2:15 p.m.

Room

room 5050

Title in Polish

Binary counting is hard

Seminar

Seminar Automata Theory

---

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

---