Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Unavoidable_pattern> ?p ?o. }
Showing items 1 to 16 of
16
with 100 items 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.Let 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-unavoidable 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 wikiPageRevisionID "587845863".
- Unavoidable_pattern hasPhotoCollection Unavoidable_pattern.
- Unavoidable_pattern subject Category:Combinatorics_on_words.
- Unavoidable_pattern subject Category:Formal_languages.
- Unavoidable_pattern subject Category:Semigroup_theory.
- 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.Let A be an alphabet of letters and E a disjoint alphabet of pattern symbols or "variables". Elements of E+ are patterns.".
- Unavoidable_pattern label "Motif inévitable".
- Unavoidable_pattern label "Unavoidable pattern".
- Unavoidable_pattern sameAs Motif_inévitable.
- Unavoidable_pattern sameAs m.0nb6n_3.
- Unavoidable_pattern sameAs Q7882337.
- Unavoidable_pattern sameAs Q7882337.
- Unavoidable_pattern wasDerivedFrom Unavoidable_pattern?oldid=587845863.
- Unavoidable_pattern isPrimaryTopicOf Unavoidable_pattern.