Reidenbach_Schmid_TCS_Regular_and_context_free_pattern_languages.pdf (428.57 kB)
Download fileRegular and context-free pattern languages over small alphabets
journal contribution
posted on 2014-01-23, 14:00 authored by Daniel Reidenbach, Markus L. SchmidPattern languages are generalisations of the copy language, which is a standard
textbook example of a context-sensitive and non-context-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