%0 Conference Paper %A Reidenbach, Daniel %A Schmid, Markus L. %D 2012 %T Regular and context-free pattern languages over small alphabets %U https://repository.lboro.ac.uk/articles/conference_contribution/Regular_and_context-free_pattern_languages_over_small_alphabets/9405251 %2 https://repository.lboro.ac.uk/ndownloader/files/17021963 %K Pattern languages %K Regular languages %K Context-free languages %K Information and Computing Sciences not elsewhere classified %X 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. %I Loughborough University