Stephen Melczer, University of Pennsylvania
Abstract: Just as the Chomsky–Schützenberger hierarchy allows one to define increasingly expressive formal languages, one can examine increasingly complex families of enumerative sequences based on algebraic and analytic properties of their generating functions. This talk examines the following question: given a sequence encoded by its generating function in some natural manner, when is it decidable to determine dominant asymptotics of the sequence? Current research centres around the new field of analytic combinatorics in several variables (ACSV), drawing from singularity theory, computational topology, and algebraic geometry. We give a survey of the techniques of ACSV, discuss recent complexity results on sequence asymptotics, and highlight applications, and examine remaining open problems.