Set systems: order types, continuous nondeterministic deformations, and quasi-orders

Details Set systems: order types, continuous nondeterministic deformations, and quasi-orders Set systems: order types, continuous nondeterministic deformations, and quasi-orders

2011-06-27

arxiv.org/abs/1106.5294v1

Computer Science

Logic in Computer Science

Scientific paper

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 (dim L 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 dim L. (2) dim L is an upper bound of the mind-change complexity of L. dim L 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 {\alpha}, then the direct image of L is a set system of order type at most n-adic diagonal Ramsey number of {\alpha}. 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. Keyword: finite elasticity, shuffle-closure

Affiliated with

Also associated with

No associations

Rating

Set systems: order types, continuous nondeterministic deformations, and quasi-orders does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Set systems: order types, continuous nondeterministic deformations, and quasi-orders, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Set systems: order types, continuous nondeterministic deformations, and quasi-orders will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-637874