Day_Reidenbach_Schmid_DLT14_final.pdf (316.96 kB)
Download fileClosure properties of pattern languages
conference contribution
posted on 2014-10-13, 13:14 authored by Joel DayJoel Day, Daniel Reidenbach, Markus L. SchmidPattern 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.
History
School
- Science
Department
- Computer Science
Published in
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)Volume
8633 LNCSPages
279 - 290Citation
DAY, 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 PublishingVersion
- AM (Accepted Manuscript)
Publisher statement
This 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/Publication date
2014Notes
This 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.ISBN
9783319096971ISSN
0302-9743eISSN
1611-3349Publisher version
Book series
Lecture Notes in Computer Science;8633Language
- en