New answers tagged

2

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.


6

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