Day_Reidenbach_Schmid_DLT14_final.pdf (316.96 kB)
0/0

Closure properties of pattern languages

Download (316.96 kB)
conference contribution
posted on 13.10.2014 by Joel 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.

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 LNCS

Pages

279 - 290

Citation

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 Publishing

Version

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

2014

Notes

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

9783319096971

ISSN

0302-9743

eISSN

1611-3349

Book series

Lecture Notes in Computer Science;8633

Language

en

Exports

Logo branding

Exports