Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Commutative Regular Shuffle Closed Languages, Noetherian Property, and Learning Theory

Yohji Akama19 Contact Information

(19)  Mathematical Institute, Tohoku University (Japan Science and Technology Agency), Sendai Miyagi Japan, 980-8578
Abstract
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 A d  + 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 $\mathcal{X}^{d}_{k}$ of A d  + F such that A is a square matrix of size d with integer entries and F consists of at most k number of d-dimensional integer vectors (F is repeated according to the lattice A d ). 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.

Contact Information Yohji Akama
Email: akama@m.tains.tohoku.ac.jp
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.111 • Server: mpweb21
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)