2134/16055
Joel Day
Joel
Day
Daniel Reidenbach
Daniel
Reidenbach
Markus L. Schmid
Markus L.
Schmid
Closure properties of pattern languages
Loughborough University
2014
Pattern languages
Closure properties
Information and Computing Sciences not elsewhere classified
2014-10-13 13:14:56
Conference contribution
https://repository.lboro.ac.uk/articles/conference_contribution/Closure_properties_of_pattern_languages/9404873
Pattern languages are a well-established class of languages that is particularly popular in algorithmic learning theory, but very little is known about their closure properties. In the present paper we establish a large number of closure properties of the terminal-free pattern languages, and we characterise when the union of two terminal-free pattern languages is again a terminal-free pattern language. We demonstrate that the equivalent question for general pattern languages is characterised differently, and that it is linked to some of the most prominent open problems for pattern languages. We also provide fundamental insights into a well-known construction of E-pattern languages as unions of NE-pattern languages, and vice versa. © 2014 Springer International Publishing Switzerland.