Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Unavoidable_pattern> ?p ?o }
Showing triples 1 to 38 of
38
with 100 triples per page.
- Unavoidable_pattern abstract "In mathematics and theoretical computer science, an unavoidable pattern is a pattern of symbols that must occur in any sufficiently long string over an alphabet. An avoidable pattern is one for which there are infinitely many words no part of which match the pattern.Zimin words are an example of unavoidable patterns. These are formed by inserting a new letter between two instances of the previous Zimin word, i.e., the first Zimin word A is used to create the second Zimin word ABA, which in turn creates ABACABA and then ABACABADABACABA and so on.It is unavoidable that any string, containing two unique characters, that is five or more characters long will contain a pattern of the form ABA (the second Zimin word). Using three unique characters any string containing 29 or more characters will contain a pattern of the form ABACABALet A be an alphabet of letters and E a disjoint alphabet of pattern symbols or \"variables\". Elements of E+ are patterns. For a pattern p, the pattern language is that subset of A∗ containing all words h(p) where h is a non-erasing semigroup morphism from the free monoid E∗ to A∗. A word w in A∗ matches or meets p if it contains some word in the pattern language as a factor, otherwise w avoids p.A pattern p is avoidable on A if there are infinitely many words in A∗ that avoid p; it is unavoidable on A if all sufficiently long words in A∗ match p. We say that p is k-unavoidable if it is unavoidable on every alphabet of size k and correspondingly k-avoidable if it is avoidable on an alphabet of size k.There is a word W(k) over an alphabet of size 4k which avoids every avoidable pattern with less than 2k variables.".
- Unavoidable_pattern wikiPageID "37477193".
- Unavoidable_pattern wikiPageLength "5808".
- Unavoidable_pattern wikiPageOutDegree "12".
- Unavoidable_pattern wikiPageRevisionID "630692750".
- Unavoidable_pattern wikiPageWikiLink American_Mathematical_Society.
- Unavoidable_pattern wikiPageWikiLink Cambridge_University_Press.
- Unavoidable_pattern wikiPageWikiLink Category:Combinatorics_on_words.
- Unavoidable_pattern wikiPageWikiLink Category:Formal_languages.
- Unavoidable_pattern wikiPageWikiLink Category:Semigroup_theory.
- Unavoidable_pattern wikiPageWikiLink Finite_difference.
- Unavoidable_pattern wikiPageWikiLink Free_monoid.
- Unavoidable_pattern wikiPageWikiLink Semigroup.
- Unavoidable_pattern wikiPageWikiLink Sesquipower.
- Unavoidable_pattern wikiPageWikiLink Springer_Science+Business_Media.
- Unavoidable_pattern wikiPageWikiLink Thue–Morse_sequence.
- Unavoidable_pattern wikiPageWikiLinkText "Unavoidable pattern".
- Unavoidable_pattern wikiPageWikiLinkText "Unavoidable pattern#Avoidability index".
- Unavoidable_pattern wikiPageWikiLinkText "unavoidable pattern".
- Unavoidable_pattern wikiPageUsesTemplate Template:Cite_book.
- Unavoidable_pattern wikiPageUsesTemplate Template:Main.
- Unavoidable_pattern wikiPageUsesTemplate Template:Reflist.
- Unavoidable_pattern subject Category:Combinatorics_on_words.
- Unavoidable_pattern subject Category:Formal_languages.
- Unavoidable_pattern subject Category:Semigroup_theory.
- Unavoidable_pattern hypernym Pattern.
- Unavoidable_pattern type Disease.
- Unavoidable_pattern type Language.
- Unavoidable_pattern type Combinatoric.
- Unavoidable_pattern type Language.
- Unavoidable_pattern comment "In mathematics and theoretical computer science, an unavoidable pattern is a pattern of symbols that must occur in any sufficiently long string over an alphabet. An avoidable pattern is one for which there are infinitely many words no part of which match the pattern.Zimin words are an example of unavoidable patterns.".
- Unavoidable_pattern label "Unavoidable pattern".
- Unavoidable_pattern sameAs Q7882337.
- Unavoidable_pattern sameAs Motif_inévitable.
- Unavoidable_pattern sameAs m.0nb6n_3.
- Unavoidable_pattern sameAs Q7882337.
- Unavoidable_pattern wasDerivedFrom Unavoidable_pattern?oldid=630692750.
- Unavoidable_pattern isPrimaryTopicOf Unavoidable_pattern.