Language equivalence and inclusion are fundamental notions in automata theory, and everybody agrees they are worth studying. But other equivalences also have a robust mathematical background. One is bisimulation, already well recognised in our community. I'd like to shed light on another which can be very interesting, but seems to be less known in our community: multiplicity equivalence.

Two systems A and B are multiplicity equivalent if for every word w, A has the same number of accepting runs over w as B. It is finer than language equivalence and in some cases better behaved: for NFAs, deciding language equivalence is PSPACE-complete, while multiplicity equivalence reduces to the zeroness problem for weighted automata over the field Q(+,x), whether all words are mapped to zero, which can be solved with linear algebra in PTime.

The open problem I propose is deciding multiplicity equivalence for two context-free grammars. Language equivalence is undecidable for CFGs, but decidability of multiplicity equivalence is unclear. It was conjectured decidable back in the 80s or 90s (Danny Raz, 1993: "Deciding Multiplicity Equivalence for Certain Context-free Languages"). As for NFAs, the problem is equivalent to zeroness for weighted CFGs. The fundamental challenge is the algebraic structure: since words do not commute (ab ≠ ba), this connects to noncommutative algebra and may be deep and challenging. Understanding it, and a possible algorithm, could be very fruitful for automata theory.

The problem is also equivalent to language equivalence of probabilistic pushdown automata, shown by Forejt, Jancar, Kiefer and Worrell in 2014. Recent work towards the conjecture has made limited progress: decidability holds for BPP (a subclass of Petri nets) and for Integer VASS over a unary alphabet.

Proposal by Wojciech Czerwiński (University of Warsaw). Presentation by David Purser (University of Liverpool).