depth first tree traversal
How do we know whether the algorithm can terminate successfully? One idea is to simulate all possible choices, so if one of them works we won’t miss it. This is more or less what we did for zeroeth order logic. The tree structure of the tableau keeps track of the possible choices for us. We can apply the same trick essentially any non-deterministic algorithm, using a tree to keep track of the choices. There are some complications though if there are sometimes infinitely many choices.
To check whether the algorithm could successfully terminate we have to visit every node in the tree, but there might be infinitely many. There are two standard ways to traverse a tree, depth first or breadth first. Depth first means visiting all of a node’s children before moving on to any of its siblings. Breadth first means visiting all of a node’s siblings before moving on to any of its children. The diagrams show both a depth first and a breadth first traversal of a binary tree with seven nodes, numbered in the order in which they are traversed. Depth first is usually easier to program, so if you’ve used a program which traverses a tree that’s probably what it did.
Depth first traversal will work, i.e. visit every node, on finite trees and some, but not all, infinite trees. Breadth first traversal will work, even on infinite trees, provided no node has infinitely many children. “Working” means that if what we’re looking for is there we will find it. If it’s not there the traversal will continue forever, unless the tree happened to be finite.
The trees in the tableau method for zeroeth order logic were finite, so either method works. The trees for Łukasiewicz have branches of finite length, but infinitely many children. Neither method works for this. The trees (of trees) for parsing usually have infinitely long branches but have only finitely many children, unless there are symbols with infinitely many tokens, so breadth first generally works and depth first generally doesn’t.
There are traversal methods which work even for trees with infinite branches and infinitely many children, provided the infinities aren’t too bad. When there are more than two children we can group them as the first one and the others, then create a new node for the others. The result is a binary tree containing all the nodes of the original tree, on which we can do breadth first traversal. This is illustrated in the two accompanying diagrams, but infinite children are hard to draw so we’ll have to make do with three. The first shows a non-binary tree and second shows the corresponding binary tree, with extra nodes added.
