11
Along with my comment above (noting that not even AC0 is in "StreamL"), let me say that that this class has been studied before; you just need to know what they used to call it.
Search for "one-way logspace" and you will find plenty of references. (Typically, past work treats it as a reducibility concept.) The papers that those papers reference should cover ...
answered Apr 24 '20 at 22:38
Ryan Williams
25.8k66 gold badges108108 silver badges157157 bronze badges
Only top voted, non community-wiki answers of a minimum length are eligible
Related Tags
space-bounded × 82cc.complexity-theory × 54
reference-request × 12
ds.algorithms × 11
complexity-classes × 10
space-complexity × 9
fl.formal-languages × 8
logspace × 7
nondeterminism × 6
automata-theory × 5
quantum-computing × 4
reductions × 4
circuit-complexity × 3
ds.data-structures × 3
sat × 3
lower-bounds × 3
turing-machines × 3
derandomization × 3
space-time-tradeoff × 3
graph-theory × 2
randomized-algorithms × 2
big-picture × 2
context-free × 2
grammars × 2
oracles × 2