Decision Trees for Binary Subword-Closed Languages

In this chapter, for arbitrary binary subword-closed languages, we investigate the depth of decision trees solving the recognition and the membership problems for words of the length n deterministically and nondeterministically. With the growth of n, the minimum depth of 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, with the growth of n, the minimum depth of decision trees is either bounded from above by a constant or grows linearly. We also 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.