This HTML5 document contains 186 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
n27http://csseminar.kadm.usu.ru/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-eshttp://es.dbpedia.org/resource/
n22http://g.co/kg/m/
dbpedia-hehttp://he.dbpedia.org/resource/
n19http://www.ics.uci.edu/~eppstein/pubs/
n8https://dmtcs.episciences.org/395/
dbpedia-ruhttp://ru.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n18https://www.jalc.de/issues/2019/issue_24_2-4/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
dbpedia-pthttp://pt.dbpedia.org/resource/
n10http://fr.dbpedia.org/resource/Modèle:
n28http://fr.dbpedia.org/resource/Fichier:
n7http://fr.dbpedia.org/resource/Modèle:Traduction/
n9http://commons.wikimedia.org/wiki/Special:FilePath/
wikipedia-frhttp://fr.wikipedia.org/wiki/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n25http://ma-graph.org/entity/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
n12http://ebooks.cambridge.org/ref/id/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbrhttp://dbpedia.org/resource/
n26http://dml.cz/bitstream/handle/10338.dmlcz/126647/
wikidatahttp://www.wikidata.org/entity/

Statements

Subject Item
dbpedia-fr:Mot_synchronisant
rdfs:label
Mot synchronisant
rdfs:comment
En informatique théorique, et plus particulièrement en théorie des automates finis déterministes, un mot synchronisant, en anglais aussi reset word, est un mot sur l'alphabet d'entrée d'un automate qui envoie tout état de l'automate sur le même état. En d'autres termes, si un ensemble de copies de l'automate démarre, simultanément chacune en un état différent, elles se trouvent toutes après la lecture du mot synchronisant en même temps dans le même état. Les automates finis ne possèdent pas tous un mot synchronisant. Par exemple, un automate à deux états réduit à un circuit de longueur 2 ne peut pas être synchronisé. Le problème majeur encore ouvert concerne la longueur des plus courts mots synchronisants, et est connu sous le nom de conjecture de Černý.
owl:sameAs
dbpedia-ru:Синхронизирующее_слово dbpedia-es:Conjetura_de_Černý dbpedia-he:השערת_צ'רני n22:03cdlxy dbr:Synchronizing_word n25:2780551793 dbpedia-pt:Palavra_de_sincronia wikidata:Q7662204
dbo:wikiPageID
11470647
dbo:wikiPageRevisionID
179319523
dbo:wikiPageWikiLink
dbpedia-fr:Journal_of_Automata,_Languages_and_Combinatorics dbpedia-fr:Majorant_ou_minorant dbpedia-fr:David_Eppstein dbpedia-fr:Automate_fini_déterministe dbpedia-fr:Degré_(théorie_des_graphes) dbpedia-fr:Coloriage_des_routes dbpedia-fr:Graphe_régulier dbpedia-fr:Valérie_Berthé dbpedia-fr:Avraham_Trahtman dbpedia-fr:Israel_Journal_of_Mathematics dbpedia-fr:Benjamin_Weiss dbpedia-fr:Complexité_en_temps dbpedia-fr:Discrete_Mathematics_&_Theoretical_Computer_Science dbpedia-fr:Informatique_théorique dbpedia-fr:Roy_Adler n28:Automate_des_paires_2.jpg n28:Automates_synchronisable_et_non_synchronisable.jpg n28:Automate_des_paires_1.jpg dbpedia-fr:Graphe_orienté category-fr:Combinatoire category-fr:Théorie_des_automates dbpedia-fr:SIAM_Journal_on_Computing dbpedia-fr:Problème_NP-complet category-fr:Problème_non_résolu_en_mathématiques dbpedia-fr:Information_and_Computation dbpedia-fr:Composante_fortement_connexe category-fr:Théorie_des_graphes n28:Road_coloring_conjecture.svg dbpedia-fr:Theoretical_Computer_Science
dbo:wikiPageExternalLink
n8:pdf n12:CBO9781139924733A060 n18:jalc-2019-343-365.php n19:Epp-SJC-90.pdf n26:MathSlov_14-1964-3_2.pdf n27:tarragona_volkov2008.pdf
dbo:wikiPageLength
13453
dct:subject
category-fr:Combinatoire category-fr:Théorie_des_graphes category-fr:Théorie_des_automates category-fr:Problème_non_résolu_en_mathématiques
prop-fr:wikiPageUsesTemplate
n7:Référence n10:Chapitre n10:Rouge n10:Article_détaillé n10:Théorème n10:Bleu n10:Ouvrage n10:Portail n10:Plume n10:Références n10:Article n10:,
prov:wasDerivedFrom
wikipedia-fr:Mot_synchronisant?oldid=179319523&ns=0
foaf:depiction
n9:Road_coloring_conjecture.svg n9:Automates_synchronisable_et_non_synchronisable.jpg n9:Automate_des_paires_1.jpg n9:Automate_des_paires_2.jpg
prop-fr:année
1970 1990 2008 2009 2019 2016 1964
prop-fr:arxiv
709.01
prop-fr:auteur
Avraham N. Trahtman Mikhail V. Volkov
prop-fr:collection
Encyclopedia of Mathematics and its Applications Lecture Notes in Computer Science Memoires of the American Mathematical Society
prop-fr:date
2008 2009 2007
prop-fr:doi
10.1016 10.1137 10.256 10.1017 10.1007
prop-fr:id
bp JC
prop-fr:isbn
978 9781107077027 9781139924733
prop-fr:journal
dbpedia-fr:Israel_Journal_of_Mathematics Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied dbpedia-fr:Journal_of_Automata,_Languages_and_Combinatorics dbpedia-fr:SIAM_Journal_on_Computing dbpedia-fr:Information_and_Computation
prop-fr:lienAuteur
Avraham Trahtman Benjamin Weiss
prop-fr:lireEnLigne
n8:pdf
prop-fr:nom
Trahtman Adler Volkov Béal Weiss Proposition Perrin Černý Conjecture de Černý Nicaud Eppstein Jürgensen
prop-fr:numéro
9 2 3 1 37
prop-fr:pages
51 43 3 343 3513 500 208 1033
prop-fr:pagesTotales
ii+48
prop-fr:passage
11 213
prop-fr:prénom
Marie-Pierre Mikhail V. Benjamen Roy L. Helmut Avraham N. Cyril David Dominique Ján
prop-fr:présentationEnLigne
n12:CBO9781139924733A060 n18:jalc-2019-343-365.php
prop-fr:périodique
dbpedia-fr:Discrete_Mathematics_&_Theoretical_Computer_Science dbpedia-fr:Theoretical_Computer_Science Fifth IFIP International Conference on Theoretical Computer Science
prop-fr:titre
The Černý Conjecture Holds with High Probability The Cerny Conjecture for Aperiodic Automata Poznámka k homogénnym experimentom s konečnými automatami The road coloring problem Synchronised automata Synchronizing road coloring Synchronization Synchronizing automata preserving a chain of partial orders Synchronizing Automata and the Černý Conjecture Similarity of automorphisms of the torus Reset Sequences for Monotonic Automata
prop-fr:titreOuvrage
Combinatorics, Words and Symbolic Dynamics Language and Automata Theory and Applications
prop-fr:url
n19:Epp-SJC-90.pdf n27:tarragona_volkov2008.pdf n26:MathSlov_14-1964-3_2.pdf
prop-fr:volume
206 410 172 24 19 14 9 273
prop-fr:éditeur
Cambridge University Press Springer-Verlag
prop-fr:auteursOuvrage
Valérie Berthé et Michel Rigo
prop-fr:numéroChapitre
7
prop-fr:numéroDansCollection
135 98 5196
prop-fr:mathReviews
168429 257315
prop-fr:hal
966534
prop-fr:énoncé
Un automate apériodique synchronisable à états possède un mot synchronisant de longueur au plus . Tout automate fini déterministe complet synchronisable à états possède un mot synchronisant de longueur au plus .
dbo:thumbnail
n9:Road_coloring_conjecture.svg?width=300
foaf:isPrimaryTopicOf
wikipedia-fr:Mot_synchronisant
dbo:namedAfter
wikidata:Q57974125
dbo:abstract
En informatique théorique, et plus particulièrement en théorie des automates finis déterministes, un mot synchronisant, en anglais aussi reset word, est un mot sur l'alphabet d'entrée d'un automate qui envoie tout état de l'automate sur le même état. En d'autres termes, si un ensemble de copies de l'automate démarre, simultanément chacune en un état différent, elles se trouvent toutes après la lecture du mot synchronisant en même temps dans le même état. Les automates finis ne possèdent pas tous un mot synchronisant. Par exemple, un automate à deux états réduit à un circuit de longueur 2 ne peut pas être synchronisé. Le problème majeur encore ouvert concerne la longueur des plus courts mots synchronisants, et est connu sous le nom de conjecture de Černý.