The Tape Comilexity of Some Classes of Szilard Languages

Abstract

In this paper we discuss lower and upper bounds for the tape complexity of Turing machines which recognize some classes of Szilard languages. The main results are as follows: $\log n$ is the optimal tape bound for on-line deterministic Turing machines which recognize Szilard languages of context-free grammars, and it is also the optimal tape bound for off-line deterministic Turing machines which recognize leftmost Szilard languages of phrase structure grammars. The Szilard language of an arbitrary phrase structure grammar is a deterministic context-sensitive language.