Article ID Journal Published Year Pages File Type
428300 Information Processing Letters 2007 5 Pages PDF
Abstract

We show that the set of binary words containing overlaps is not unambiguously context-free and that the set of ternary words containing overlaps is not context-free. We also show that the set of binary words that are not subwords of the Thue–Morse word is not unambiguously context-free.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics