The seminar is open to public and does not require any form of registration.
In this talk, I will speak about the Online Space Complexity of languages, which is an old topic (studied by Karp, Minsky, Hartmanis and others in the 60s) that I picked up recently. The main question is the following: given a language L, how many states does an automaton need to recognise L, as a function of the input length? This question is well-understood for regular languages, which are those recognised by finite automata, so we go beyond this case and study non-regular languages. This talk will be a gentle introduction to these questions; I will present some results about the online space complexity of probabilistic languages.
Based on a forthcoming paper at LFCS'2016.