The re-pairing problem is a recently discovered combinatorial problem concerning Dyck words. We have first identified the re-pairing problem when studying an open question in automata theory, the complexity of translation of one-counter automata (OCA) on finite words into Parikh-equivalent nondeterministic finite automata (NFA). But it appears that the re-pairing problem has natural connections with other combinatorial problems arising in analysis of weak models of computation (e.g., black-and-white pebble games). We hope that more relations will be discovered in future. 

In the talk I will define the problem and give a survey of known results about it.

This is joint work with D. Chistikov.

Join Zoom Meeting Here!