Set systems: order types, continuous nondeterministic deformations, and quasi-orders
From MaRDI portal
Publication:653312
Abstract: By reformulating a learning process of a set system L as a game between Teacher (presenter of data) and Learner (updater of the abstract independent set), we define the order type dim L of L to be the order type of the game tree. The theory of this new order type and continuous, monotone function between set systems corresponds to the theory of well quasi-orderings (WQOs). As Nash-Williams developed the theory of WQOs to the theory of better quasi-orderings (BQOs), we introduce a set system that has order type and corresponds to a BQO. We prove that the class of set systems corresponding to BQOs is closed by any monotone function. In (Shinohara and Arimura. "Inductive inference of unbounded unions of pattern languages from positive data." Theoretical Computer Science, pp. 191-209, 2000), for any set system L, they considered the class of arbitrary (finite) unions of members of L. From viewpoint of WQOs and BQOs, we characterize the set systems L such that the class of arbitrary (finite) unions of members of L has order type. The characterization shows that the order structure of the set system L with respect to the set-inclusion is not important for the resulting set system having order type. We point out continuous, monotone function of set systems is similar to positive reduction to Jockusch-Owings' weakly semirecursive sets.
Recommendations
Cites work
- scientific article; zbMATH DE number 5294801 (Why is no real title available?)
- scientific article; zbMATH DE number 3957109 (Why is no real title available?)
- scientific article; zbMATH DE number 3677903 (Why is no real title available?)
- scientific article; zbMATH DE number 3777562 (Why is no real title available?)
- scientific article; zbMATH DE number 42059 (Why is no real title available?)
- scientific article; zbMATH DE number 67629 (Why is no real title available?)
- scientific article; zbMATH DE number 3641474 (Why is no real title available?)
- scientific article; zbMATH DE number 1216133 (Why is no real title available?)
- scientific article; zbMATH DE number 1233727 (Why is no real title available?)
- scientific article; zbMATH DE number 1324671 (Why is no real title available?)
- scientific article; zbMATH DE number 1351108 (Why is no real title available?)
- scientific article; zbMATH DE number 1515218 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- scientific article; zbMATH DE number 3248824 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Algebraic Theory of Automata and Languages
- Classical recursion theory. Vol. II
- Commutative Regular Shuffle Closed Languages, Noetherian Property, and Learning Theory
- Developments from enquiries into the learnability of the pattern languages from positive data
- Elements of automata theory. Translated from the French by Reuben Thomas
- From wqo to bqo, via Ellentuck's theorem
- Learning indexed families of recursive languages from positive data: A survey
- Logic, language and computation. Festschrift in Honor of Satoru Takasu
- Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data
- Mind change efficient learning
- Ordering by Divisibility in Abstract Algebras
- Ordinal mind change complexity of language identification
- Reverse mathematics and the equivalence of definitions for well and better quasi-orders
- Subsystems of second order arithmetic
- The theory of well-quasi-ordering: a frequently discovered concept
- Topological properties of concept spaces (full version)
Cited in
(2)
This page was built for publication: Set systems: order types, continuous nondeterministic deformations, and quasi-orders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q653312)
