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
    By what kind of machine?2011-05-29
  • 0
    @Peter Taylor: For sake of concreteness: by program in SML language (as it has formal definition). Update.2011-05-29
  • 1
    Are you asking "what are the languages that are decidable with an algorithm that has linear complexity" ? Linear algorithmic complexity, unlike polynomial complexity, depends heavily on what is the machine you are using. For example, if you convert a multi-tape O(n) turing machine into a single-tape turing machine, the complexity bumps up to O(n²). So you need to provide a precise description of your language (like, if it knows integers, can it do arithmetic operations in constant time ? etc)2011-05-29
  • 0
    @chandok: Yes, additional steps while addressing memory is an issue. I already mentioned SML in comments (update).2011-05-29
  • 0
    @chandok: "can it do arithmetic operations in constant time?" This issue may be sidestepped by asserting that fixed width arithmetics must be O(1) while arbitrary precision operations O(log(n)).2011-05-29
  • 0
    Isn't this non-recursive by Rice's theorem? It's a non-trivial property of a TM (or whatever Turing complete formalism you have).2011-05-29
  • 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.

  • 1
    No, I've mean _maximal_ class, LR1/LL1 are proper CFGs; CFG is exactly PDA recognizable; PDA is one stack machine, but I mean conventional programs which use two stack machines. So, RE and DCFG and LL1/LR1 etc are not answers to my question.2011-05-28
  • 0
    What kind of "conventional program" uses two stack machines? By the way, please describe how a Turing machine simulates a PDA in linear time; if you can not, there is no reason to disregard the possibility that maybe the set you are looking for is in fact a subset of CFL.2011-05-28
  • 0
    @Raphael: "What kind of "conventional program" uses two stack machines": I meant two stack machines are Turing-complete so they are equivalent in power to "conventional languages".2011-05-28
  • 0
    @Raphael: "no reason to disregard the possibility that maybe the set you are looking for is in fact a subset of CFL" Where I did that? I did not disregard it! I just said RE,LL1,LR1 and DCFG are not answers because of one-stackness.2011-05-28
  • 0
    But they are subsets of Turing decidable languages!2011-05-29
  • 1
    @Raphael: CFL is too small because our class contains langauges like $a^n b^m c^n d^m e^{n+m} f^{|n-m|}$ which clearly are not context free. So what we're looking is not subset of CFL.2011-05-29
  • 0
    Turing machines can *not* parse the class you give in linear time, not even in the logarithmic cost model. Please specify more closely what cost model you want to employ. Also, you might want to consider that there is no name yet and the characterisation you give in your question is the only one (known).2011-05-29
  • 0
    @Raphael: "Please specify more closely.." Done. "..there is no name yet.." -- well, if someone know that it is no name nor papers on it he may put it in answer and it will suffice.2011-05-30
  • 0
    Wether some concept has never been conceived (and published) might be a (practically) undecidable problem. That is, you will most likely not receive an answer of that kind because nobody can say so with certainty.2011-05-30
  • 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