# Tag Info

2

I recently had the same question in mind when reading Pager's work. I found the paper The Edge-Pushing LR(k) Algorithm by Chen and Pager, which seems to say that the two terms are indeed the same. Quoting that paper: The concepts of state, configuration and theads(α, k) used here are equivalent to “item set”, “item” and FIRSTk(α) correspondingly in some ...

7

Your trees are showing the same thing; you are just labeling each node by the call, and the Berkeley tutorial is labeling each node by the result of that call. Compare the two pictures of fibtree(3), noting that: $F(0) = 0$ $F(1) = 1$ $F(2) = 1$ $F(3) = 2$ You'll see there's no disagreement at all. Perhaps it would be informative to see the tree "grow&...

20

I would like to say both you and that Berkeley tutorial are correct. As commented by chepner, the trees in Berkeley tutorial and the trees you thought are the same semantically; only the labels of the nodes are different. Every node in all figures represents a call to compute the corresponding Fibonacci number. The difference is that you prefer to use ...

1

This is a trie that is truncated to two levels.

1

This definition from Wikipedia makes it simpler: Tight bounds An upper bound is said to be a tight upper bound, a least upper bound, or a supremum, if no smaller value is an upper bound. Similarly, a lower bound is said to be a tight lower bound, a greatest lower bound, or an infimum, if no greater value is a lower bound. https://en.wikipedia.org/wiki/...

Top 50 recent answers are included