Regular and context-free pattern languages over small alphabets

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-f...

Full description

Bibliographic Details

Main Authors:	Daniel Reidenbach, Markus L. Schmid
Format:	Default Conference proceeding
Published:	2012
Subjects:	Other information and computing sciences not elsewhere classified Pattern languages Regular languages Context-free languages Information and Computing Sciences not elsewhere classified
Online Access:	https://hdl.handle.net/2134/10117
Tags:	Add Tag No Tags, Be the first to tag this record!