Invited Speakers
Jean-Paul Allouche
Jean-Paul Allouche is Emeritus Research Director at the CNRS, Institute Mathématique de Jussieu-PRG, Combinatoire et Optimisation group. He has a vast work in areas such as number theory, algebra, dynamical systems, topology, statistical mechanics, combinatorics, and automata theory. He is best known for his work on automatic sequences and related topics.
Morphic sequences versus automatic sequences
Two classical families of infinite sequences with some regularity properties are the families of morphic and of automatic sequences. After recalling their definitions, we survey some recent work trying to "separate" between them.
Henning Fernau
Henning Fernau is a Professor at the Department of Theoretical Computer Science at the University of Trier, Germany. His research interests focus on efficient graph algorithms, parameterized algorithms and complexity, approximation algorithms and complexity, formal languages and grammar induction. He is head of the Special Interest Group Automata and Formal Languages of the German Computer Science Society.
Parsimonious Computational Completeness
Throughout the history of Formal Languages, one of the research directions has always been to describe computational completeness using only a small amount of possibly scarce resources. We review some of these results in the form of an essay.
Michal Koucký
Michal Koucký is a Full Professor at the Computer Science Institute of the Charles University, in Prague. His expertise is in computational complexity, where he has worked in circuit complexity, randomized computation, pseudorandomness and lower bounds. His recent work on approximation algorithms for edit distance has earned him the best paper award at FOCS 2018.
Computing Edit Distance
Edit distance (or Levenshtein distance) is a measure of similarity of strings. The edit distance of two strings x, y is the minimum number of character insertions, deletions, and substitutions needed to convert x into y. It has numerous applications in various fields from text processing to bioinformatics so algorithms for edit distance computation attract lot of attention. In this talk I will survey recent progress on computational aspects of edit distance in several contexts: computing edit distance approximately, computing edit distance in streaming model, and exchanging similar strings in communication complexity model. I will point out many problems that are still open in those areas.
Alexandra Silva
Alexandra Silva is Professor of Algebra, Semantics, and Computation at the Programming Principles, Logic and Verification Group, University College London. She received a Ph.D in Computer Science by the Radboud University Nijmegen, The Netherlands, in 2010. Her research focuses on the modular development of specification languages and algorithms for models of computations, in particular using the coalgebra framework. Her many awards include the Presburger Award (EATCS, 2017) and the Royal Society Wolfson Award (2019).
Guarded Kleene Algebra with Tests
Guarded Kleene Algebra with Tests (GKAT) is an efficient fragment of KAT, as it allows for almost linear decidability of equivalence. In this talk, we will review the basics of GKAT and describe its (co)algebraic properties. We will describe two completeness results and an automaton model that plays a key role in their proof. We will show examples of different models of GKAT that can be used in program verification and discuss future directions of research.
Benjamin Steinberg
Benjamin Steinberg is a Professor in the Mathematics Department of the City College of New York and the CUNY Graduate Center. He received a Ph.D. at the University of California at Berkeley. He is an algebraist interested in a broad range of areas including semigroups, geometric group theory, algebraic combinatorics and representation theory; and applications to automata theory and computer science.
Pointlike sets and separation: a personal perspective
This is a personal survey about pointlike sets since their inception to roughly the present. Personal means that I make no attempt to be exhaustive, but rather to highlight things that have affected my research in the area or that I consider fundamental to the area. Pointlike sets, in the language of separation and covering problems, have become very popular now in Computer Science because of the truly amazing work of Place and Zeitoun on dot-depth and related hierarchies. I believe revisiting some of the older results will revive interest and provide perspective.