Fysikkbygningen øst (kart)
Sem Sælands vei 24
The standard implementations for searching with regular expressions (e.g. grep) have exponential behavior on some input. For example, using ``numerical constraints'' it is easy to make grep one-liners that consume over 8 GB of memory. There are polynomial-time algorithms for a subset of regular expressions with numerical constraints. Is it possible to combine the (usually extremely efficient) optimisations and extensions done in grep with algorithms that do not have exponential behavior?
The Reliable Systems group PSY (formerly PMA) teaches the following courses: