Online Space Complexity

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

• Nathanaël Fijalkow, Laboratoire d'Informatique Algorithmique: Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7
• Friday 13 November 2015, 14:00-15:00
• FW26.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• FW26
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.