| Property |
Value |
| dbo:abstract
|
- En mathématiques et en informatique théorique, et tout particulièrement en combinatoire des mots, une équation de mots ou une équation entre mots (en anglais word equation) est un couple de mots, usuellement écrit sous la forme d'une équation . Ici, et sont des mots composés de lettres qui sont des constantes ou des variables. Les constantes sont écrites en minuscules et les variables en majuscules, ou aussi fréquemment en minuscules d'« inconnues », comme etc. Par exemple, l'équation contient quatre occurrences de la variable , et des constantes et . Une solution d'une équation est un ensemble de mots sans variables, un pour chaque variable, tel que la substitution des mots aux variables rend les deux composantes de l’équation identiques. Par exemple, pour (et plus généralement pour avec , les deux côtés de l'équation précédentes deviennent égaux, à (et plus généralement à ). On considère le problème qui consiste à trouver une solution à équation de mots, ou plus généralement un ensemble d'équations de mots. Un célèbre théorème de Makanin établit que ce problème est décidable. En cela, les équations de mots se distinguent des équations diophantiennes pour lesquels l'existence de solutions est indécidable par le théorème de Matiiassevitch résolvant le dixième problème de Hilbert. Un problème lié est la description de toutes les solutions d'une équation donnée, sous forme paramétrée en général. La première étude systématique dans cette direction est faite par Hmelevskii. (fr)
- En mathématiques et en informatique théorique, et tout particulièrement en combinatoire des mots, une équation de mots ou une équation entre mots (en anglais word equation) est un couple de mots, usuellement écrit sous la forme d'une équation . Ici, et sont des mots composés de lettres qui sont des constantes ou des variables. Les constantes sont écrites en minuscules et les variables en majuscules, ou aussi fréquemment en minuscules d'« inconnues », comme etc. Par exemple, l'équation contient quatre occurrences de la variable , et des constantes et . Une solution d'une équation est un ensemble de mots sans variables, un pour chaque variable, tel que la substitution des mots aux variables rend les deux composantes de l’équation identiques. Par exemple, pour (et plus généralement pour avec , les deux côtés de l'équation précédentes deviennent égaux, à (et plus généralement à ). On considère le problème qui consiste à trouver une solution à équation de mots, ou plus généralement un ensemble d'équations de mots. Un célèbre théorème de Makanin établit que ce problème est décidable. En cela, les équations de mots se distinguent des équations diophantiennes pour lesquels l'existence de solutions est indécidable par le théorème de Matiiassevitch résolvant le dixième problème de Hilbert. Un problème lié est la description de toutes les solutions d'une équation donnée, sous forme paramétrée en général. La première étude systématique dans cette direction est faite par Hmelevskii. (fr)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 21788 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1976 (xsd:integer)
- 1977 (xsd:integer)
- 1993 (xsd:integer)
- 1995 (xsd:integer)
- 2002 (xsd:integer)
- 2004 (xsd:integer)
- 2013 (xsd:integer)
- 2015 (xsd:integer)
- 2019 (xsd:integer)
|
| prop-fr:arxiv
|
- 1507.032150 (xsd:double)
- 1702.007360 (xsd:double)
|
| prop-fr:auteur
|
- Volker Diekert (fr)
- Artur Jeż (fr)
- Gennadiĭ S. Makanin (fr)
- Wojciech Plandowski (fr)
- Youri I. Hmelevskii (fr)
- Yuri V. Matiyassevich (fr)
- Volker Diekert (fr)
- Artur Jeż (fr)
- Gennadiĭ S. Makanin (fr)
- Wojciech Plandowski (fr)
- Youri I. Hmelevskii (fr)
- Yuri V. Matiyassevich (fr)
|
| prop-fr:auteurOuvrage
|
- M. Lothaire (fr)
- M. Lothaire (fr)
|
| prop-fr:auteursOuvrage
|
- Natacha Portier et Thomas Wilke (fr)
- Natacha Portier et Thomas Wilke (fr)
|
| prop-fr:collection
|
- Lecture Notes in Computer Science (fr)
- Encyclopedia of Mathematics and its Applications (fr)
- Leibniz International Proceedings in Informatics (fr)
- Lecture Notes in Computer Science (fr)
- Encyclopedia of Mathematics and its Applications (fr)
- Leibniz International Proceedings in Informatics (fr)
|
| prop-fr:consultéLe
| |
| prop-fr:date
|
- février 2022 (fr)
- février 2022 (fr)
|
| prop-fr:doi
|
- 10.100700 (xsd:double)
- 10.101600 (xsd:double)
- 10.423000 (xsd:double)
|
| prop-fr:id
|
- M77 (fr)
- Die15 (fr)
- M77 (fr)
- Die15 (fr)
|
| prop-fr:isbn
|
- 2 (xsd:integer)
- 978 (xsd:integer)
|
| prop-fr:journal
|
- Theoretical Computer Science (fr)
- Math. Sbornik (fr)
- Soviet Math. Dokl. (fr)
- Theoretical Computer Science (fr)
- Math. Sbornik (fr)
- Soviet Math. Dokl. (fr)
|
| prop-fr:langue
| |
| prop-fr:langueOriginale
|
- ru-Latn (fr)
- ru-Latn (fr)
|
| prop-fr:lieu
|
- Paris (fr)
- Cambridge, Mass. (fr)
- Paris (fr)
- Cambridge, Mass. (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:mathReviews
|
- 393284 (xsd:integer)
- 470107 (xsd:integer)
|
| prop-fr:nom
|
- Matiiassevitch (fr)
- Plandowski (fr)
- Théorème de Lyndon-Schützenberger (fr)
- Matiiassevitch (fr)
- Plandowski (fr)
- Théorème de Lyndon-Schützenberger (fr)
|
| prop-fr:numéro
| |
| prop-fr:numéroChapitre
| |
| prop-fr:numéroDansCollection
|
- 90 (xsd:integer)
- 9270 (xsd:integer)
|
| prop-fr:pages
|
- 20 (xsd:integer)
- 122 (xsd:integer)
- 147 (xsd:integer)
- 330 (xsd:integer)
- 483 (xsd:integer)
|
| prop-fr:pagesTotales
|
- 270 (xsd:integer)
- 288 (xsd:integer)
- 307 (xsd:integer)
|
| prop-fr:passage
|
- 22 (xsd:integer)
- 233 (xsd:integer)
- 387 (xsd:integer)
|
| prop-fr:prénom
|
- Youri (fr)
- Wojciech (fr)
- Youri (fr)
- Wojciech (fr)
|
| prop-fr:présentationEnLigne
| |
| prop-fr:périodique
|
- Journal of Computer and System Sciences (fr)
- Journal of the Association for Computing Machinery (fr)
- Journal of Computer and System Sciences (fr)
- Journal of the Association for Computing Machinery (fr)
|
| prop-fr:sousTitre
|
- son indécidabilite (fr)
- son indécidabilite (fr)
|
| prop-fr:titre
|
- Equations in free semigroups (fr)
- The problem of solvability of equations in a free semigroup (fr)
- Hilbert’s Tenth Problem (fr)
- Le dixième problème de Hilbert (fr)
- Word equations in non-deterministic linear space (fr)
- On PSPACE generation of a solution set of a word equation and its applications (fr)
- Satisfiability of word equations with constants is in PSPACE. (fr)
- Equations in free semigroups (fr)
- The problem of solvability of equations in a free semigroup (fr)
- Hilbert’s Tenth Problem (fr)
- Le dixième problème de Hilbert (fr)
- Word equations in non-deterministic linear space (fr)
- On PSPACE generation of a solution set of a word equation and its applications (fr)
- Satisfiability of word equations with constants is in PSPACE. (fr)
|
| prop-fr:titreChapitre
|
- Makanin's Algorithm (fr)
- More than 1700 years of word equations (fr)
- Recompression: a simple and powerful technique for word equations (fr)
- Makanin's Algorithm (fr)
- More than 1700 years of word equations (fr)
- Recompression: a simple and powerful technique for word equations (fr)
|
| prop-fr:titreOuvrage
|
- 30 (xsd:integer)
- Algebraic Combinatorics on Words (fr)
- Conference on Algebraic Informatics (fr)
|
| prop-fr:url
| |
| prop-fr:volume
|
- 18 (xsd:integer)
- 51 (xsd:integer)
- 103 (xsd:integer)
- 123 (xsd:integer)
- 792 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:zbl
| |
| prop-fr:éditeur
|
- dbpedia-fr:MIT_Press
- Springer (fr)
- Cambridge University Press (fr)
- Masson (fr)
- American Mathematical Society, Proceedings of the Steklov Institute of Mathematics 107 (fr)
|
| prop-fr:énoncé
|
- L'équation dans le demi-groupe libre n'a que des solutions cycliques, c'est-à-dire qui sont puissances d'un même mot. (fr)
- L'équation dans le demi-groupe libre n'a que des solutions cycliques, c'est-à-dire qui sont puissances d'un même mot. (fr)
|
| dct:subject
| |
| rdfs:comment
|
- En mathématiques et en informatique théorique, et tout particulièrement en combinatoire des mots, une équation de mots ou une équation entre mots (en anglais word equation) est un couple de mots, usuellement écrit sous la forme d'une équation . Ici, et sont des mots composés de lettres qui sont des constantes ou des variables. Les constantes sont écrites en minuscules et les variables en majuscules, ou aussi fréquemment en minuscules d'« inconnues », comme etc. Par exemple, l'équation (fr)
- En mathématiques et en informatique théorique, et tout particulièrement en combinatoire des mots, une équation de mots ou une équation entre mots (en anglais word equation) est un couple de mots, usuellement écrit sous la forme d'une équation . Ici, et sont des mots composés de lettres qui sont des constantes ou des variables. Les constantes sont écrites en minuscules et les variables en majuscules, ou aussi fréquemment en minuscules d'« inconnues », comme etc. Par exemple, l'équation (fr)
|
| rdfs:label
|
- Équation entre mots (fr)
- Équation entre mots (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
