January 1, 1979Open Access

Deterministic CFL's are accepted simultaneously in polynomial time and log squared space

Key Points

Key points are not available for this paper at this time.

Abstract

We propose to prove the theorem in the title. Let PLOSS be the class of sets recognizable on a deterministic Turing machine simultaneously in polynomial time and log squared space. Using the notation of Bruss and Meyer 1, PLOSS = υk TISP(nk,k log2n).

Bookmark

View Full Paper

Cite This Study

Stephen Cook (Mon,) studied this question.

synapsesocial.com/papers/6a203ba824cb4701b18fd378 https://doi.org/https://doi.org/10.1145/800135.804426

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

1On parallelism in turing machines1976 · 121 citations
2Relationships between nondeterministic and deterministic tape complexities1970 · 1,362 citations
3On time-space classes and their relation to the theory of real addition1980 · 24 citations
4On time-space classes and their relation to the theory of real addition1978 · 9 citations
5The circuit value problem is log space complete for <i>P</i>1975 · 306 citations

Bookmark

View Full Paper