In combinatorics, a squarefree word is a word (a sequence of symbols) that does not contain any squares. A square is a word of the form XX, where X is not empty. Thus, a squarefree word can also be defined as a word that avoids the pattern XX.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Quadratfreies Wort (de)
- Mot sans facteur carré (fr)
- Square-free word (en)
- Бесквадратное слово (ru)
|
| rdfs:comment
| - Unter einem quadratfreien Wort (englisch squarefree word) versteht man in der Theoretischen Informatik ein Wort, das kein (nicht-leeres) Quadrat eines anderen Wortes enthält. (de)
- In combinatorics, a squarefree word is a word (a sequence of symbols) that does not contain any squares. A square is a word of the form XX, where X is not empty. Thus, a squarefree word can also be defined as a word that avoids the pattern XX. (en)
- En combinatoire, et notamment en combinatoire des mots, un carré est un mot composé de deux parties égales consécutives, comme bonbon ou papa. En bio-informatique, un carré est appelé une répétition en tandem.Un mot sans facteur carré ou plus simplement un mot sans carré est un mot qui ne contient pas de facteur carré. Par exemple, le mot répétition contient le carré titi ; en revanche, le mot consécutivement est un mot sans carré. L'étude des mots sans carré fait partie, plus généralement, de l'étude des répétitions dans les mots, et de la possibilité de les éviter. On parle alors de répétitions évitables ou inévitables. (fr)
- Бесквадра́тное сло́во (англ. square-free word) — слово, в котором никакое подслово не повторяется подряд 2 раза (т.е. это слово нельзя представить в виде yxxz, где x, у и z — некоторые подслова). А. Туэ доказал, что бесконечные бесквадратные слова существуют над любыми алфавитами из по крайней мере 3 букв. Один из простейших примеров бесконечного бесквадратного слова над алфавитом из 3 букв можно построить, если начать с слова и далее из слова получать слово с помощью замен «a»->«abcab», «b»->«acabcb», «c»->«acbcacb». Каждое следующее слово будет содержать в себе предыдущее, что позволяет построить бесконечное слово «abcabacabcbacbcacbabcabacabcb…». (ru)
|
| foaf:depiction
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - Unter einem quadratfreien Wort (englisch squarefree word) versteht man in der Theoretischen Informatik ein Wort, das kein (nicht-leeres) Quadrat eines anderen Wortes enthält. (de)
- En combinatoire, et notamment en combinatoire des mots, un carré est un mot composé de deux parties égales consécutives, comme bonbon ou papa. En bio-informatique, un carré est appelé une répétition en tandem.Un mot sans facteur carré ou plus simplement un mot sans carré est un mot qui ne contient pas de facteur carré. Par exemple, le mot répétition contient le carré titi ; en revanche, le mot consécutivement est un mot sans carré. L'étude des mots sans carré fait partie, plus généralement, de l'étude des répétitions dans les mots, et de la possibilité de les éviter. On parle alors de répétitions évitables ou inévitables. Il existe des mots infinis sans carré sur tout alphabet d'au moins trois lettres, comme l'a prouvé Axel Thue. Sur un alphabet à deux lettres, un tel mot n'existe pas. Le mot de Prouhet-Thue-Morse contient des carrés, en revanche il est sans cube. Une méthode fréquemment utilisée par construire des mots infinis sans carré, sans cube ou sans puissance plus élevée est par itération d'un morphisme. Si ce morphisme a la propriété de transformer une mot fini sans carré, sans cube ou sans puissance plus élevée en un mot de même nature, on parle d'un morphisme sans carré, sans cube ou sans puissance plus élevée. (fr)
- In combinatorics, a squarefree word is a word (a sequence of symbols) that does not contain any squares. A square is a word of the form XX, where X is not empty. Thus, a squarefree word can also be defined as a word that avoids the pattern XX. (en)
- Бесквадра́тное сло́во (англ. square-free word) — слово, в котором никакое подслово не повторяется подряд 2 раза (т.е. это слово нельзя представить в виде yxxz, где x, у и z — некоторые подслова). А. Туэ доказал, что бесконечные бесквадратные слова существуют над любыми алфавитами из по крайней мере 3 букв. Один из простейших примеров бесконечного бесквадратного слова над алфавитом из 3 букв можно построить, если начать с слова и далее из слова получать слово с помощью замен «a»->«abcab», «b»->«acabcb», «c»->«acbcacb». Каждое следующее слово будет содержать в себе предыдущее, что позволяет построить бесконечное слово «abcabacabcbacbcacbabcabacabcb…». Число бесквадратных слов из трёх букв длины образует последовательность в OEIS. Она растёт экспоненциально от , а показатель экспоненты равен . (ru)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
