Learning a Subclass of Regular Patterns in Polynomial Time

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann


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 x0α1x1...αmxm for unknown m but known c, from number of examples polynomial in m (and exponential in c), where x0,..., xm 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 languageEnglish
Title of host publicationALT 2003: Algorithmic Learning Theory
Number of pages13
PublisherSpringer Berlin Heidelberg
Publication date01.01.2003
ISBN (Print)978-3-540-20291-2
ISBN (Electronic)978-3-540-39624-6
Publication statusPublished - 01.01.2003
Event14th International Conference on Algorithmic Learning Theory
- Sapporo, Japan
Duration: 17.10.200319.10.2003
Conference number: 133919


Dive into the research topics of 'Learning a Subclass of Regular Patterns in Polynomial Time'. Together they form a unique fingerprint.

Cite this