Decision Trees for Regular Factorial Languages

In this chapter, for arbitrary regular factorial languages, we investigate the depth of decision trees solving the recognition and the membership problems for words of the length n deterministically and nondeterministically. For a given problem and type of trees, instead of the minimum depth h(n) of a decision tree of the considered type solving the problem, we study the smoothed minimum depth \(H(n)=\max \{h(m):m\le n\}\) . With the growth of n, the smoothed 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 cases, with the growth of n, the smoothed minimum depth of decision trees is either bounded from above by a constant or grows linearly. As corollaries of the obtained results, we study joint behavior of the smoothed minimum depths of decision trees for the considered four cases and describe five complexity classes of regular factorial languages. We also investigate the class of regular factorial languages over the alphabet \(\{0,1\}\) each of which is given by one forbidden word.