On the Time and Tape Complexity of Languages

Abstract

We investigate the following: (1) the relationship between the classes of languages accepted by deterministic and nondeterministic polynomial time bounded Turing machines; (2) the relationship between the classes of languages accepted by deterministic and nondeterministic linear bounded automata; (3) sufficient conditions for undecidability of linguistic predicates; and (4) the time and space complexity of several predicates on the regular sets. We show that the set $\{ R | R$ is a $(\cup, ^{.}, *, \caap)$ regular expression and $L(R) = \{0,1\}*\}$ is not recognizable by any polynomial space bounded Turing machine. We also find conditions which guarantee that any predicate on the regular sets satisfying them is as hard to decide as emptiness or equivalence.