Efficient streaming regular pattern matching

Regular pattern matching is comes up very often, both in theoretical frameworks and in practice and, as such, is a problem that has been studied a lot. The RAM model in which it is studied, however, does not always take into account the practical difficulties that arise with very large amount of data, which don’t fit in memory. For this reason, it makes sense to study efficient algorithms in a more realistic computational model, the streaming model. ...

October 30, 2023 · 12 min · jthulhu