论文标题
二进制子字封闭式语言的决策树
Decision trees for binary subword-closed languages
论文作者
论文摘要
在本文中，我们在字母$ \ {0,1 \} $（二进制子单词封闭式语言）上研究任意子字关闭的语言。对于属于二进制子字封闭式语言$ l $的长度$ n $的一组单词$ l（n）$，我们研究了决策树的深度，以确定性和无确定性。在识别问题的情况下，对于$ l（n）$的给定单词，我们应该使用查询每个$ i \ in \ {1，\ ldots，n \} $都会识别它，返回该单词的$ i $ i th字母。对于会员问题，对于长度$ n $的字母$ \ {0,1 \} $上的给定单词，我们应该使用相同的查询来认识它是否属于集合$ l（n）$。随着$ n $的增长，决策树的最小深度确定性地解决了识别问题，要么以上面的态度以常数为界，要么以对数或线性形式成长。对于其他类型的树木和问题（决策树以无确定性解决问题，决策树以确定性和非确定性解决会员问题解决），随着$ n $的增长，决策树的最小深度是由上述界定的，或者是通过恒定或线性增长的。我们研究了被考虑的四种决策树的最小深度的联合行为，并描述了二进制子字封闭式语言的五个复杂性类别。
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 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 $\{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 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 decision trees is either bounded from above by a constant or grows linearly. We study joint behavior of minimum depths of the considered four types of decision trees and describe five complexity classes of binary subword-closed languages.
