University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Online Space Complexity

Online Space Complexity

Add to your list(s) Download to your calendar using vCal

  • UserNathana√ęl Fijalkow, Laboratoire d'Informatique Algorithmique: Fondements et Applications (LIAFA), Universit√© Paris Diderot - Paris 7 World_link
  • ClockFriday 13 November 2015, 14:00-15:00
  • HouseFW26.

If you have a question about this talk, please contact Ohad Kammar.

The Online Space Complexity of a language L (over finite words) is a complexity measure aiming at quantifying the amount of information (in terms of space consumption) needed to process words letter by letter and maintaining the answer to the Boolean query “is the word read so far in L?”.

The aim of this talk is to motivate the study of Online Space Complexity and to give an overview of the preliminary results we obtained so far. In particular, we’ll discuss the Online Space Complexity of Probabilistic Languages.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity