On the context-freeness of the set of words containing overlaps

Simple item page
dc.creatorRampersad, Narad
dc.date2006-10-02
dc.date.accessioned2026-07-07T12:57:19Z
dc.date.available2026-07-07T12:57:19Z
dc.descriptionWe 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.
dc.description8 pages
dc.identifierhttps://arxiv.org/abs/math/0610067
dc.identifierhttp://arxiv.org/abs/math/0610067
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/224891
dc.subjectCombinatorics
dc.subjectFormal Languages and Automata Theory
dc.subject68R15
dc.titleOn the context-freeness of the set of words containing overlaps
dc.typetext

Files

Collections

arXiv