Editing Method of analytic tableaux (section)

===Reducing search===

The size of the search tree depends on the number of (children) tableaux that can be generated from a given (parent) one. Reducing the number of such tableaux therefore reduces the required search.

A way for reducing this number is to disallow the generation of some tableaux based on their internal structure. An example is the condition of regularity: if a branch contains a literal, using an expansion rule that generates the same literal is useless because the branch containing two copies of the literals would have the same set of formulae of the original one. This expansion can be disallowed because if a closed tableau exists, it can be found without it. This restriction is structural because it can be checked by looking at the structure of the tableau to expand only.
 
Different methods for reducing search disallow the generation of some tableaux on the ground that a closed tableau can still be found by expanding the other ones. These restrictions are called global. As an example of a global restriction, one may employ a rule that specifies which of the open branches is to be expanded. As a result, if a tableau has for example two non-closed branches, the rule specifies which one is to be expanded, disallowing the expansion of the second one. This restriction reduces the search space because one possible choice is now forbidden; completeness is however not harmed, as the second branch will still be expanded if the first one is eventually closed. As an example, a tableau with root <math>\neg a \land \neg b</math>, child <math>a \lor b</math>, and two leaves <math>a</math> and <math>b</math> can be closed in two ways: applying <math>(\land)</math> first to <math>a</math> and then to <math>b</math>, or vice versa. There is clearly no need to follow both possibilities; one may consider only the case in which <math>(\land)</math> is first applied to <math>a</math> and disregard the case in which it is first applied to <math>b</math>. This is a global restriction because what allows neglecting this second expansion is the presence of the other tableau, where expansion is applied to <math>a</math> first and <math>b</math> afterwards.