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?

$\endgroup$
  • $\begingroup$ By what kind of machine? $\endgroup$ – Peter Taylor May 29 '11 at 7:27
  • $\begingroup$ @Peter Taylor: For sake of concreteness: by program in SML language (as it has formal definition). Update. $\endgroup$ – Vag May 29 '11 at 8:21
  • 1
    $\begingroup$ 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) $\endgroup$ – mercio May 29 '11 at 14:18
  • $\begingroup$ @chandok: Yes, additional steps while addressing memory is an issue. I already mentioned SML in comments (update). $\endgroup$ – Vag May 29 '11 at 14:48
  • $\begingroup$ @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)). $\endgroup$ – Vag May 29 '11 at 14:59
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Vag May 28 '11 at 19:17
  • $\begingroup$ 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. $\endgroup$ – Raphael May 28 '11 at 22:01
  • $\begingroup$ @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". $\endgroup$ – Vag May 28 '11 at 22:05
  • $\begingroup$ @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. $\endgroup$ – Vag May 28 '11 at 22:06
  • 1
    $\begingroup$ @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. $\endgroup$ – Vag May 29 '11 at 13:09
0
$\begingroup$

Did you mean linear bounded automata?

$\endgroup$
  • 1
    $\begingroup$ LBA is too powerful because its program may be above O(n). $\endgroup$ – Vag May 29 '11 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.