14 votes
Accepted

Solve the recurrence $f(n) = f(n-1) + f(n - \log n)$

@Chandra, @Emil, and myself solved the question in the comments. The solution is $$f(n) = 2^{\Theta(n \log \log n / \log n)} \ .$$ To see the lower bound, apply the recurrence definition $\log n$ ...
greg's user avatar
  • 1,101
12 votes
Accepted

Growth rate of primitive recursive functions

The answer is no, there is no exponential bound on PR. PR contains Knuth's up-arrow functions, Elementary functions, etc. PR is equal to the union of Grzegorczyk hierarchy. Exponential functions ...
Kaveh's user avatar
  • 21.6k
7 votes

Conservative Approximation of Kleene-Mycroft Iteration for Polymorphic Recursion?

You should have a look at the following paper -- and the previous work by Gori and Levi: On Polymorphic Recursion, Type Systems, and Abstract Interpretation Marco Comini, Ferruccio Damiani, Samuel ...
gasche's user avatar
  • 2,040
7 votes
Accepted

Composition with recursion in functions between types

(I'm going to try to write an answer for functional programmers, with Haskell-like code.) First, you should know that using higher-order functions, recursive definitions can be turned into fixed-point ...
Lê Thành Dũng Nguyễn's user avatar
6 votes
Accepted

Termination checking for Scott-encodings in System F with positive-recursive types

I'll first point you to Types for the Scott Numerals by Plotkin, Cardelli and Abadi, where they show how to encode Scott numerals in plain old system F. This at least shows that you can write the "...
cody's user avatar
  • 13.8k
4 votes

What is the relationship between tail recursion with other recursions?

From the point of view of lambda-calculus "tail call optimization" means take a CPS converted version the program, and eta-reduce continuations of the form $\lambda x. k\;x$ to $k$ Since eta-...
Neel Krishnaswami's user avatar
4 votes

Termination checking for Scott-encodings in System F with positive-recursive types

(Sorry for the blatant self-advertisement that follows!) In addition to what was already said, you should really check out our recent TOPLAS paper (https://doi.org/10.1145/3285955), which deals with ...
Rodolphe Lepigre's user avatar
4 votes

Extension of primitive recursion, that is as powerful as System-T

If you're just talking about the expressiveness of functions $\mathbb{N}\rightarrow\mathbb{N}$, then you can extend primitive recursion to allowing a recursive call over a Cantor normal form, where ...
cody's user avatar
  • 13.8k
4 votes
Accepted

Is any computational complexity question solved by injury priority method except Post problem?

Priority method gets used a lot in computability theory - see some of the later chapters of Soare's book on computability. Buhrman and Torenvliet use a resource-bounded priority method to build an ...
Joshua Grochow's user avatar
4 votes

Reference for automatically deriving dynamic programming algorithms from recursive algorithms?

There's actually two questions here! The transformation you ask about is called the tupling transformation. Basically, if your recursive calls follow a fixed pattern of overlap, a memo-table can be ...
Neel Krishnaswami's user avatar
3 votes
Accepted

Linear regression as a hylomorphism

You can indeed see linear regression as arising from a fixed point computation, but it is better to think of it as related to transitive closure computations than to folds or unfolds. Regression is ...
Neel Krishnaswami's user avatar
3 votes
Accepted

Time complexity for multiplying two lower triangular matrices

With the expert hints of Mr Emil, I could find a reduction of general matrix multiplication to triangular matrix multiplication. If we wish to multiply two $n \times n$ matrices $A$ and $B$, I can ...
Pranav Bisht's user avatar
2 votes
Accepted

Why can a Predictive Parser contain E' -> TE' | ε

... is not valid since we have "left recursion" (a variable that calls itself). That's not what a left recursion is. That's simply recursion. Direct left recursion is when a rule $A \to A\alpha$ ...
orlp's user avatar
  • 825
2 votes

Definitional equality of recursive function definition by "infinite unfolding"

Your predd2 is not a fixpoint; you could replace the Fixpoint by Definition. And the fact ...
xavierm02's user avatar
  • 556
2 votes

What is formal definition of non-deterministic algorithm in context of primitive/general recursion?

You could easily make Kleene's $\mu$-recursive programs nondeterministic. A $\mu$-recursive program consists of a sequence of function symbols, each defined from previous ones by composition, ...
Siddharth's user avatar
  • 823
1 vote

Bad Cycles in Interaction Nets

Quoting from the paper: It is possible to define rules which lead to non-terminating computations, [...] but further constraints on nets can ensure that when a sequence of reductions terminates, the ...
D.W.'s user avatar
  • 12k
1 vote

Composition with recursion in functions between types

The theory behind recursion schemes is that algebraic data types are initial algebras. 1. Recursive types and folds The programmer's point of view is that, given a recursive type, ...
Li-yao Xia's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible