Reidenbach_Schmid_DLT_2012.pdf (335.22 kB)
Download file

Regular and context-free pattern languages over small alphabets

Download (335.22 kB)
conference contribution
posted on 25.07.2012, 13:44 by Daniel ReidenbachDaniel Reidenbach, Markus L. Schmid
Pattern languages are generalisations of the copy language, which is a standard textbook example of a context-sensitive and noncontext- free language. In this work, we investigate a counter-intuitive phenomenon: with respect to alphabets of size 2 and 3, pattern languages can be regular or context-free in an unexpected way. For this regularity and context-freeness of pattern languages, we give several sufficient and necessary conditions and improve known results.

History

School

  • Science

Department

  • Computer Science

Citation

REIDENBACH, D. and SCHMID, M.L., 2012. Regular and context-free pattern languages over small alphabets. IN: Yen, H.-C. and Ibarra, O.H. (eds.). Developments in Language Theory: 16th International Conference, DLT 2012 Taipei, Taiwan, August 14-17, 2012 Proceedings. Lecture Notes In Computer Science; 7410, pp.130-141.

Publisher

© Springer-Verlag Berlin Heidelberg 2012

Version

AM (Accepted Manuscript)

Publication date

2012

Notes

The final publication is available at www.springerlink.com.

ISBN

9783642316524

ISSN

0302-9743

eISSN

1611-3349

Book series

Lecture Notes In Computer Science; 7410

Language

en