论文标题
常规阶乘语言的决策树
Decision trees for regular factorial languages
论文作者
论文摘要
在本文中，我们通过有限字母$σ$研究了任意的常规阶乘语言。对于属于常规阶乘语言$ l $的长度$ n $的一组单词$ l（n）$，我们研究了决策树的深度，以确定性和非确定性地解决识别和成员资格问题。在识别问题的情况下，对于$ l（n）$的给定单词，我们应该使用查询每个$ i \ in \ {1，\ ldots，n \} $都会识别它，返回该单词的$ i $ i th字母。在会员问题的情况下，对于长度$ n $的字母$σ$上的给定单词，我们应该认识到它是否使用相同的查询属于集合$ l（n）$。对于给定的问题和树的类型，我们研究了$ l（n）$的最小深度$ h（n）$，而是研究$ l（n）$的问题，而是研究平滑的最小深度$ h（n）= \ max \ {h（m）：m \ le n \ n \} $。随着$ n $的增长，决策树的平滑最小深度确定性地解决了识别问题，要么以上面的限制，要么以对数或线性的方式成长为对数。对于其他案例（决策树以不确定的方式解决识别问题，决策树以确定性和非确定性解决会员问题解决），随着$ n $的增长，决策树的最小深度的增长是通过常数或线性增长的。作为获得结果的推论，我们研究了四种情况下决策树的平滑最小深度的联合行为，并描述了常规阶乘语言的五个复杂性类别。我们还通过字母$ \ {0,1 \} $调查了常规阶乘语言的类别，每个类别由一个禁止单词给出。
In this paper, we study arbitrary regular factorial languages over a finite alphabet $Σ$. For the set of words $L(n)$ of the length $n$ belonging to a regular factorial language $L$, we investigate the depth of decision trees solving the recognition and the membership problems deterministically and nondeterministically. In the case of recognition problem, for a given word from $L(n)$, we should recognize it using queries each of which, for some $ i\in \{1,\ldots ,n\}$, returns the $i$th letter of the word. In the case of membership problem, for a given word over the alphabet $Σ$ of the length $n$, we should recognize if it belongs to the set $L(n)$ using the same queries. 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 for $L(n)$, 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 (decision trees solving the problem of recognition nondeterministically, and decision trees solving the membership problem deterministically and nondeterministically), 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 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.
