TY - JOUR

T1 - Set systems

T2 - Order types, continuous nondeterministic deformations, and quasi-orders

AU - Akama, Yohji

N1 - Funding Information:
The author sincerely thanks Dr. Matthew de Brecht, Hajime Ishihara, and anonymous referees. This work is partially supported by Grant-in-Aid for Scientific Research (C) (21540105) of the Ministry of Education, Culture, Sports, Science and Technology (MEXT).

PY - 2011/10/21

Y1 - 2011/10/21

N2 - 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 setinclusion. 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 quasiorders 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.

AB - 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 setinclusion. 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 quasiorders 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.

KW - Finite elasticity

KW - Finitely branching simulation

KW - Game

KW - Order type

KW - Ramsey's theorem

KW - Shuffle-closure

UR - http://www.scopus.com/inward/record.url?scp=84865735446&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84865735446&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2011.08.010

DO - 10.1016/j.tcs.2011.08.010

M3 - Article

AN - SCOPUS:84865735446

SN - 0304-3975

VL - 412

SP - 6235

EP - 6251

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 45

ER -