Projects per year
Abstract
Presented is an algorithm (for learning a subclass of erasing regular pattern languages) which can be made to run with arbitrarily high probability of success on extended regular languages generated by patterns π of the form x_{0}α_{1}x_{1}...α_{m}x_{m} for unknown m but known c, from number of examples polynomial in m (and exponential in c), where x_{0},..., x_{m} are variables and where α_{1},..., α_{m} are each strings of constants or terminals of length c. This assumes that the algorithm randomly draws samples with natural and plausible assumptions on the distribution. The more general looking case of extended regular patterns which alternate between a variable and fixed length constant strings, beginning and ending with either a variable or a constant string is similarly handled.
Original language  English 

Title of host publication  ALT 2003: Algorithmic Learning Theory 
Number of pages  13 
Volume  2842 
Publisher  Springer Berlin Heidelberg 
Publication date  01.01.2003 
Pages  234246 
ISBN (Print)  9783540202912 
ISBN (Electronic)  9783540396246 
DOIs  
Publication status  Published  01.01.2003 
Event  14th International Conference on Algorithmic Learning Theory  Sapporo, Japan Duration: 17.10.2003 → 19.10.2003 Conference number: 133919 
Fingerprint
Dive into the research topics of 'Learning a Subclass of Regular Patterns in Polynomial Time'. Together they form a unique fingerprint.Projects
 1 Finished

Robust learning methods and data compression
01.01.04 → 31.12.08
Project: DFG Projects › DFG Individual Projects