On the Time and Tape Complexity of Languages.

摘要

The author investigates the following:The relationship between the classes of languages accepted by deterministic and nondeterministic polynomial time bounded Turing machines;the relationship between the classes of languages accepted by deterministic and nondeterministic linear bounded automata;sufficient conditions for undecidability of linguistic predicates;and the time and space complexity of several predicates on the regular sets. (Modified author abstract)