Day_Reidenbach_Schmid_DLT14_final.pdf (316.96 kB)
Closure properties of pattern languages
conference contributionposted on 2014-10-13, 13:14 authored by Joel DayJoel Day, Daniel Reidenbach, Markus L. Schmid
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.
- Computer Science
Published inLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages279 - 290
CitationDAY, J.D., REIDENBACH, D. and SCHMID, M.L., 2014. Closure properties of pattern languages. IN: Shur, A.M. and Volkov, M.V. (eds). Developments in Language Theory. Proceedings of the 18th International Conference DLT 2014, 26th-29th August 2014, Ekaterinburg, Russia. Lecture Notes in Computer Science, 8633, pp.279-290.
Publisher© Springer International Publishing
- AM (Accepted Manuscript)
Publisher statementThis work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/
NotesThis conference paper was published in the Lecture Notes of Computer Science series [© Springer International Publishing]. The definitive version is available at: http://www.springerlink.com.
Book seriesLecture Notes in Computer Science;8633