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