Set systems : order types, continuous nondeterministic deformations, and quasi-orders
Set systems : order types, continuous nondeterministic deformations, and quasi-orders
复制标题
集合系统：阶次类型、连续非确定性变形和拟阶次
DOI：
10.1016/j.tcs.2011.08.010
复制
发表时间：
2011
影响因子：
1.1
通讯作者：
Yohji Akama
中科院分区：
文献类型：
--
作者：
Zi-Cai Li;Hung-Tsai Huang;Chien-Sen Huang;Tzon-Tzer Lu;Qing Fang;Yohji Akama
通过将集合系统L的学习过程表述为师生博弈，定义了L的订单型为博弈树的订单型，如果该树是良基的。L的序型特征是：(1)我们可以用上闭集的集合系统L来表示任何良拟序类(WQO)，使得WQO的最大序类等于DIML；(2)DIML是L的思想变化复杂性的上界，当L具有有限弹性时(简称FE)，其中，根据计算学习理论，如果一个指标递归语言族有FE，则它可以通过一个算法从正数据中学习。将集合系视为Cantor空间的子空间，证明了集合系的FE是由任何关于集合包含单调的连续函数保持的。通过它，我们证明了有限弹性被各种(非确定性)语言算子(Kleene-闭包、洗牌-闭包、并、积、交、…)所保持。。单调连续函数表示不确定性计算。如果单调连续函数有一棵计算树，每个结点后跟至多n个紧跟其后的计算树，且集合系统L的阶型为α，则L的直映像是至多为α的n进对角线Ramsey数的序型集合系统.此外，我们还给出了一个保序型逆变量嵌入到Cantor空间和单调连续函数之间具有Girard线性关系的完备子空间范畴中。
By reformulating a learning process of a set system L as a game between Teacher and Learner, we define the order type of L to be the order type of the game tree, if the tree is well-founded. The features of the order type of L (dimL in symbol) are (1) we can represent any well-quasi-order (wqo for short) by the set system L of the upper-closed sets of the wqo such that the maximal order type of the wqo is equal to dimL; (2) dimL is an upper bound of the mind-change complexity of L. dimL is defined iff L has a finite elasticity (fe for short), where, according to computational learning theory, if an indexed family of recursive languages has fe then it is learnable by an algorithm from positive data. Regarding set systems as subspaces of Cantor spaces, we prove that fe of set systems is preserved by any continuous function which is monotone with respect to the set-inclusion. By it, we prove that finite elasticity is preserved by various (nondeterministic) language operators (Kleene-closure, shuffle-closure, union, product, intersection, …). The monotone continuous functions represent nondeterministic computations. If a monotone continuous function has a computation tree with each node followed by at most n immediate successors and the order type of a set system L is α, then the direct image of L is a set system of order type at most n-adic diagonal Ramsey number of α. Furthermore, we provide an order-type-preserving contravariant embedding from the category of quasi-orders and finitely branching simulations between them, into the complete category of subspaces of Cantor spaces and monotone continuous functions having Girard’s linearity between them.