2
$\begingroup$

Is there name for class of languages exactly such that their words can be parsed in $O(n)$ by program in conventional Turing-complete language (SML)? (i.e. without backtracking)

Any references?

  • 0
    Mitch, by Rice's theorem there can be not algorithm who decides wether or not a given algorithm runs in linear time. But here, we ask for a class of languages; it does not matter wether it is decidable or not. I am not sure wether even the classical language classes are decidable. It depends on the input form, I guess.2011-05-29

2 Answers 2

1

I do not know of a specific name for this class of languages.

However, there are many results on grammar types. For example, LR(1) and LL(1) grammars can be parsed in linear time, but using different parsing strategies.

  • 0
    @Raphael: Well, at least I've tried to find it. So let it be so.2011-05-30
0

Did you mean linear bounded automata?

  • 1
    LBA is too powerful because its program may be above O(n).2011-05-29