| dbo:abstract
|
- In computer science, the complexity function of a word or string (a finite or infinite sequence of symbols from some alphabet) is the function that counts the number of distinct factors (substrings of consecutive symbols) of that string. More generally, the complexity function of a formal language (a set of finite strings) counts the number of distinct words of given length. (en)
- La complexité combinatoire d'un mot ou plus simplement la complexité d'un mot ou d'une suite est un moyen de mesurer, en combinatoire et en mathématique, et spécialement en combinatoire des mots, divers paramètres d'un mot qui expriment combien il est « compliqué ». La complexité combinatoire est une mesure différente de la complexité algorithmique ou complexité de Kolmogorov. Ici, on considère le plus souvent la complexité en facteurs (en anglais « subword complexity »). Parmi les mots distingués dans les diverses mesures de complexité combinatoire, il y a ceux dont la complexité est particulièrement basse. Un mot de faible complexité est un mot infini dont la fonction de complexité est « à croissance lente »; on entend par là une fonction qui croît linéairement, ou polynomialement, en tout cas nettement moins vite qu'une exponentielle. Il existe de nombreuses familles de mots infinis, comme les mots automatiques, les mots morphiques, les mots sturmiens et les mots épisturmiens, qui ont une croissance lente en ce sens. Une application importante de l'étude des mots infinis à croissance lente est à la théorie des nombres : les mots infinis qui représentent le développement d'un nombre sont à croissance lente si le nombre est rationnel ou transcendant, et plus rapide si le nombre est algébrique irrationnel. On dispose ainsi d'un moyen assez général pour construire des nombres transcendants. La complexité d'un mot fini ou infini peut se mesurer aussi par le nombre de palindromes; on parle alors de complexité palindromique. Ces deux notions de complexité combinatoire sont liées. Encore une autre mesure de complexité est la complexité abélienne d'un mot. (fr)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10348 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In computer science, the complexity function of a word or string (a finite or infinite sequence of symbols from some alphabet) is the function that counts the number of distinct factors (substrings of consecutive symbols) of that string. More generally, the complexity function of a formal language (a set of finite strings) counts the number of distinct words of given length. (en)
- La complexité combinatoire d'un mot ou plus simplement la complexité d'un mot ou d'une suite est un moyen de mesurer, en combinatoire et en mathématique, et spécialement en combinatoire des mots, divers paramètres d'un mot qui expriment combien il est « compliqué ». La complexité combinatoire est une mesure différente de la complexité algorithmique ou complexité de Kolmogorov. Ici, on considère le plus souvent la complexité en facteurs (en anglais « subword complexity »). (fr)
|
| rdfs:label
|
- Complexity function (en)
- Complexité d'un mot (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
