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$
7
  • $\begingroup$ By what kind of machine? $\endgroup$
    – Peter Taylor
    May 29, 2011 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, 2011 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, 2011 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, 2011 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, 2011 at 14:59

2 Answers 2

Reset to default
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$
10
  • 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, 2011 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, 2011 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, 2011 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, 2011 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, 2011 at 13:09
0
$\begingroup$

Did you mean linear bounded automata?

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .