Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Automata And Formal Languages

l-occurrences of avoidable patterns

Peter Roth1

(1)  Fachbereich Informatik, Johann Wolfgang Goethe-Universität, D - 6000 Frankfurt am Main, Federal Republic of Germany
Abstract
In this paper the concept of l-occurrences of patterns is introduced. Given a word wisinSgr*, we say that w contains a l-occurrence of a pattern pisinE* iff there exists a morphism h : E*rarrSgr* such that h(p) is a factor of w and |h(a)|gel for all aisinSgr.
We prove that a pattern p is avoidable iff there exists an infinite binary word that contains no l-occurrence of p for some l.

Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.110 • Server: mpweb18
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)