New answers tagged


This seems to be exactly the type of question studied by Moses Ganardi and coauthors in recent years. In particular this paper and this extension prove nice trichotomies.


It seems it would depend on your particular model, in particular what information you have access to. From what I infer, you are thinking of the following model: you have a memory $m$, for instance of size $O(\log n)$. at each step, you read a new letter $a\in\Sigma$ of your stream, and you are allowed to modify your memory $m$ you then have to say whether ...

Top 50 recent answers are included