<p>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.</p>

<p>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 what you need.</p>

CC BY-SA 4.0
2020-04-25T02:04:20.540Z
Thank you for the answer. Indeed, the class is called $1L$ and is studied by Hartmanis and others, e.g. Hartmanis and Mahaney, 1981: Languages simultaneously complete for one-way and two-way log-tape automata. [Here](https://cstheory.stackexchange.com/questions/46449/is-l-subset-1nl-when-l-neq-nl?rq=1) is a related question.
Caleb Stanford
CC BY-SA 4.0
2020-04-24T22:38:04.417Z
2020-04-24T22:38:04.417Z
Ryan Williams
<p>Consider the class of problems <span class="math-container">$\mathsf{StreamL}$</span> which can be solved in logarithmic space reading the input in a single pass from left to right. In other words:</p>
<blockquote>
<p><span class="math-container">$L \in \mathsf{StreamL}$</span> if there exists a Turing machine <span class="math-container">$M$</span> which decides <span class="math-container">$L$</span>, where:</p>
<ul>
<li><p>There are two tapes, the read-only input tape and the working tape</p>
</li>
<li><p><span class="math-container">$M$</span> moves only to the left on the input tape, and uses at most <span class="math-container">$O(\log n)$</span> space on the working tape.</p>
</li>
</ul>
</blockquote>
<p>Has this class been studied?</p>
<hr />
<p>My assumption is that the answer is yes, but I'm not yet aware of a definition of the class in the literature.</p>
<p>Most literature on streaming algorithms that I am aware of considers the complexity of solving specific algorithmic problems, and does not tackle <em>structural</em> complexity i.e. defining classes such as the above and determining their relationships.</p>
<p>There is also a large body of work on <em>communication complexity classes</em>. In this domain there is a relevant class called <span class="math-container">$\mathsf{P}^{cc}$</span> (see Babai, Frankl, and Simon 1986: Complexity classes in communication
complexity theory), which contains functions of two variables <span class="math-container">$f(x,y)$</span> where they can be solved using a small amount of communication between <span class="math-container">$x$</span> and <span class="math-container">$y$</span>. This is related to <span class="math-container">$\mathsf{StreamL}$</span> above (for functions of two variables, <span class="math-container">$\mathsf{StreamL}$</span> is contained in <span class="math-container">$\mathsf{P}^{cc}$</span>), but the class above is not limited to functions of two variables and enforces a stricter computational requirement.</p>
<p>The obvious inclusions are <span class="math-container">$\mathsf{REG} \subseteq \mathsf{StreamL} \subseteq \mathsf{L}$</span>, and no apparent inclusion either way between <span class="math-container">$\mathsf{StreamL}$</span> and <span class="math-container">$\mathsf{NC}^1$</span>.</p>

CC BY-SA 4.0
2020-04-24T02:47:02.860Z
I don't think there are many studies on this. It seems to me that for most purposes, we still study the one-way communication complexity which can be applied to proving lower bound for streaming algorithms.
polar_bear_cheese
CC BY-SA 4.0
2020-04-24T07:23:38.917Z
Using the diajointness function (an AND of ORs) you can construct functions in NC1, even in AC0, that is not in StreamL (for communication complexity reasons). StreamL would be a very weak class indeed.
Ryan Williams
<cc.complexity-theory><reference-request><complexity-classes><space-bounded><streaming-algorithms>
Complexity class of efficient streaming algorithms
Caleb Stanford
# Complexity class of efficient streaming algorithms

(Asked by: username_0 on 2020-04-23)

Consider the class of problems $\mathsf{StreamL}$ which can be solved in logarithmic space reading the input in a single pass from left to right. In other words:

> $L \in \mathsf{StreamL}$ if there exists a Turing machine $M$ which decides $L$, where:
>
> * There are two tapes, the read-only input tape and the working tape
> * $M$ moves only to the left on the input tape, and uses at most $O(\log n)$ space on the working tape.

Has this class been studied?

---

My assumption is that the answer is yes, but I'm not yet aware of a definition of the class in the literature.

Most literature on streaming algorithms that I am aware of considers the complexity of solving specific algorithmic problems, and does not tackle *structural* complexity i.e. defining classes such as the above and determining their relationships.

There is also a large body of work on *communication complexity classes*. In this domain there is a relevant class called $\mathsf{P}^{cc}$ (see Babai, Frankl, and Simon 1986: Complexity classes in communication
complexity theory), which contains functions of two variables $f(x,y)$ where they can be solved using a small amount of communication between $x$ and $y$. This is related to $\mathsf{StreamL}$ above (for functions of two variables, $\mathsf{StreamL}$ is contained in $\mathsf{P}^{cc}$), but the class above is not limited to functions of two variables and enforces a stricter computational requirement.

The obvious inclusions are $\mathsf{REG} \subseteq \mathsf{StreamL} \subseteq \mathsf{L}$, and no apparent inclusion either way between $\mathsf{StreamL}$ and $\mathsf{NC}^1$.

**Tags:** cc.complexity-theory, reference-request, complexity-classes, space-bounded, streaming-algorithms

> **Comments:**
> **username_1**: I don't think there are many studies on this. It seems to me that for most purposes, we still study the one-way communication complexity which can be applied to proving lower bound for streaming algorithms.  
> **username_2**: Using the diajointness function (an AND of ORs) you can construct functions in NC1, even in AC0, that is not in StreamL (for communication complexity reasons). StreamL would be a very weak class indeed.  

---

## 1 answers

### Answer by username_2 on 2020-04-24. Score: 11 | Accepted answer

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 what you need.

> **Comments:**
> **username_0**: Thank you for the answer. Indeed, the class is called $1L$ and is studied by Hartmanis and others, e.g. Hartmanis and Mahaney, 1981: Languages simultaneously complete for one-way and two-way log-tape automata. [Here](https://cstheory.stackexchange.com/questions/46449/is-l-subset-1nl-when-l-neq-nl?rq=1) is a related question.  

---

