TY - GEN

T1 - Commutative regular shuffle closed languages, noetherian property, and learning theory

AU - Akama, Yohji

PY - 2009

Y1 - 2009

N2 - To develop computational learning theory of commutative regular shuffle closed languages, we study finite elasticity for classes of (semi)group-like structures. One is the class of ANd + F such that A is a matrix of size e × d with nonnegative integer entries and F consists of at most k number of e-dimensional nonnegative integer vectors, and another is the class Xd k of AZd + F such that A is a square matrix of size d with integer entries and F consists of at most k number of ddimensional integer vectors (F is repeated according to the lattice AZd). Each class turns out to be the elementwise unions of k-copies of a more manageable class. So we formulate "learning time" of a class and then study in general setting how much "learning time" is increased by the elementwise union, by using Ramsey number. We also point out that such a standpoint can be generalized by using Noetherian spaces.

AB - To develop computational learning theory of commutative regular shuffle closed languages, we study finite elasticity for classes of (semi)group-like structures. One is the class of ANd + F such that A is a matrix of size e × d with nonnegative integer entries and F consists of at most k number of e-dimensional nonnegative integer vectors, and another is the class Xd k of AZd + F such that A is a square matrix of size d with integer entries and F consists of at most k number of ddimensional integer vectors (F is repeated according to the lattice AZd). Each class turns out to be the elementwise unions of k-copies of a more manageable class. So we formulate "learning time" of a class and then study in general setting how much "learning time" is increased by the elementwise union, by using Ramsey number. We also point out that such a standpoint can be generalized by using Noetherian spaces.

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

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

U2 - 10.1007/978-3-642-00982-2_8

DO - 10.1007/978-3-642-00982-2_8

M3 - Conference contribution

AN - SCOPUS:67649986872

SN - 9783642009815

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 93

EP - 104

BT - Language and Automata Theory and Applications - Third International Conference, LATA 2009, Proceedings

T2 - 3rd International Conference on Language and Automata Theory and Applications, LATA 2009

Y2 - 2 April 2009 through 8 April 2009

ER -