Decision Trees for Binary Subword-Closed Languages.

In this paper, we study arbitrary subword-closed languages over the alphabet {0,1} (binary subword-closed languages). For the set of words L(n) of the length n belonging to a binary subword-closed language L , we investigate the depth of the decision trees solving the recognition and the membership problems deterministically and nondeterministically. In the case of the recognition problem, for a given word from L(n), we should recognize it using queries, each of which, for some i∈{1,…,n}, returns the i th letter of the word. In the case of the membership problem, for a given word over the alphabet {0,1} of the length n , we should recognize if it belongs to the set L(n) using the same queries. With the growth of n , the minimum depth of the decision trees solving the problem of recognition deterministically is either bounded from above by a constant or grows as a logarithm, or linearly. For other types of trees and problems (decision trees solving the problem of recognition nondeterministically and decision trees solving the membership problem deterministically and nondeterministically), with the growth of n , the minimum depth of the decision trees is either bounded from above by a constant or grows linearly. We study the joint behavior of the minimum depths of the considered four types of decision trees and describe five complexity classes of binary subword-closed languages.