Sjötta málstofa haustsins verður föstudaginn 21. október kl 10:30 í Naustinu, húsi Endurmenntunar. Fyrirlesari er Anders Karl Claeson, Háskóla Íslands. Titill hans er Pattern rewriting systems. (Fyrirlesturinn er óbeint framhald að fyrirlestri í síðustu viku.)
Abstract. Linton, Propp, Roby and West (2012) initiated the systematic study of equivalence relations induced by pattern replacement. They considered three types of patterns: (i) unrestricted (classical) patterns; (ii) consecutive patterns (adjacent positions); and (iii) patterns in which both positions and values are required to be adjacent. We will focus on patterns of the third type and we call them Hertzsprung patterns (drawing on a problem posed by Hertzsprung in 1887). We introduce pattern-rewriting systems—a new formalism similar to the much studied string-rewriting systems—and using this formalism we solve a couple of open problems raised by Linton et al. To be more specific, we reduce the equivalence problem to counting permutations avoiding a set of Hertzsprung patterns. Moreover, using a variant of the Goulden-Jackson cluster method, we completely solve the avoidance problem. In fact, we determine the joint distribution of occurrences of any set of Hertzsprung patterns.