Data Management Strategies for Space-Efficient Decoding and Planning

Several key computer science tasks are traditionally solved via dynamic programming and need to work within the constraints of low-memory devices. This talk presents two solutions that enhance space-efficiency in such tasks. First, we will show how to achieve space-efficient Viterbi decoding, used in speech recognition and probabilistic context-free grammar parsing. Second, we will outline how to make optimal planning decisions space-efficiently in a finite-horizon Markov Decision Process. Thereby, we will showcase how data management expertise can deliver solutions in other domains. Lastly, we will glimpse into alternative time-efficient strategies for those problems.