Learning a Subclass of Regular Patterns in Polynomial Time

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

doi:10.1007/978-3-540-39624-6_19

Learning a Subclass of Regular Patterns in Polynomial Time

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

Institute of Theoretical Computer Science

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₀α₁x₁...α_mx_m for unknown m but known c, from number of examples polynomial in m (and exponential in c), where x₀,..., x_m are variables and where α₁,..., α_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	234-246
ISBN (Print)	978-3-540-20291-2
ISBN (Electronic)	978-3-540-39624-6
DOIs	https://doi.org/10.1007/978-3-540-39624-6_19
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

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/978-3-540-39624-6_19

Cite this

@inproceedings{5a123823cc9b44919fa0b2423946acc6,

title = "Learning a Subclass of Regular Patterns in Polynomial Time",

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 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.",

author = "John Case and Sanjay Jain and R{\"u}diger Reischuk and Frank Stephan and Thomas Zeugmann",

year = "2003",

month = jan,

day = "1",

doi = "10.1007/978-3-540-39624-6_19",

language = "English",

isbn = "978-3-540-20291-2",

volume = "2842",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "234--246",

booktitle = "ALT 2003: Algorithmic Learning Theory",

note = "14th International Conference on Algorithmic Learning Theory <br/>, ALT 2003 ; Conference date: 17-10-2003 Through 19-10-2003",

}

Case, J, Jain, S, Reischuk, R, Stephan, F & Zeugmann, T 2003, Learning a Subclass of Regular Patterns in Polynomial Time. in ALT 2003: Algorithmic Learning Theory. vol. 2842, Lecture Notes in Computer Science, vol. 2842, Springer Berlin Heidelberg, pp. 234-246, 14th International Conference on Algorithmic Learning Theory
, Sapporo, Japan, 17.10.03. https://doi.org/10.1007/978-3-540-39624-6_19

TY - GEN

T1 - Learning a Subclass of Regular Patterns in Polynomial Time

AU - Case, John

AU - Jain, Sanjay

AU - Reischuk, Rüdiger

AU - Stephan, Frank

AU - Zeugmann, Thomas

N1 - Conference code: 133919

PY - 2003/1/1

Y1 - 2003/1/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-7444221857&origin=inward&txGid=a231805341dac1696fc7bc0d86386405

U2 - 10.1007/978-3-540-39624-6_19

DO - 10.1007/978-3-540-39624-6_19

M3 - Conference contribution

SN - 978-3-540-20291-2

VL - 2842

T3 - Lecture Notes in Computer Science

SP - 234

EP - 246

BT - ALT 2003: Algorithmic Learning Theory

PB - Springer Berlin Heidelberg

T2 - 14th International Conference on Algorithmic Learning Theory <br/>

Y2 - 17 October 2003 through 19 October 2003

ER -

Learning a Subclass of Regular Patterns in Polynomial Time

Abstract

UN SDGs

Access to Document

Other files and links

Fingerprint

Robust learning methods and data compression

Cite this

Learning a Subclass of Regular Patterns in Polynomial Time

Abstract

UN SDGs

Access to Document

Other files and links

Fingerprint

Projects

Robust learning methods and data compression

Cite this