In computer science, more precisely, in the theory of deterministic finite automata (DFA), a synchronizing word or reset sequence is a word in the input alphabet of the DFA that sends any state of the DFA to one and the same state. That is, if an ensemble of copies of the DFA are each started in different states, and all of the copies process the synchronizing word, they will all end up in the same state. Not every DFA has a synchronizing word; for instance, a DFA with two states, one for words of even length and one for words of odd length, can never be synchronized.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Conjetura de Černý (es)
- Mot synchronisant (fr)
- Palavra de sincronia (pt)
- Synchronizing word (en)
- Синхронизирующее слово (ru)
|
| rdfs:comment
| - En 1964 Jan Černý propuso que dado un AFD (Autómata finito determinista) sincronizable de estados, existe una palabra de sincronización(o palabra de reinicio) de longitud a lo sumo de .Este problema es uno de los más antiguos y famosos junto con Teorema del coloreo de carreteras en la teoría de Autómatas Finitos. Por otro lado, se ha visto que una cota superior en la longitud de la palabra de reinicio es de tamaño cúbico en , de donde la conjetura establecería que el tamaño de las cotas superiores de la longitud de dicha palabra, sería cuadrático (en ). (es)
- 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ý. (fr)
- In computer science, more precisely, in the theory of deterministic finite automata (DFA), a synchronizing word or reset sequence is a word in the input alphabet of the DFA that sends any state of the DFA to one and the same state. That is, if an ensemble of copies of the DFA are each started in different states, and all of the copies process the synchronizing word, they will all end up in the same state. Not every DFA has a synchronizing word; for instance, a DFA with two states, one for words of even length and one for words of odd length, can never be synchronized. (en)
- Em ciência da computação, mais precisamente, na teoria de autômato finito determinístico (AFD), uma palavra sincronizadora ou sequência de recomeço é uma palavra do alfabeto de entrada da AFD que envia qualquer estado da AFD para o mesmo e único estado. Isto é, se um conjunto de cópias de uma AFD são iniciadas em diferentes estados, e todas as cópias processam a palavra sincronizadora na mesma velocidade, elas irão no final alcançar o mesmo estado uma das outras, ao mesmo tempo. Nem toda AFD possui uma palavra sincronizadora; por exemplo, uma AFD com dois estados, um para palavras de tamanho par e outro para palavras de tamanho ímpar, jamais pode ser sincronizado. (pt)
- В информатике, точнее, в теории детерминированных конечных автоматов (ДКА), синхронизирующее слово (или сжимающая последовательность) во входном алфавите автомата отображает все его состояния в одно и то же состояние. То есть, если слово стартует на ансамбле всех состояний автомата, проходя все ориентированные дуги с одинаковой скоростью, все пути завершатся одновременно в одном и том же состоянии. Не у каждого ДКА есть синхронизирующее слово, например, ДКА с двумя состояниями и циклами длины два никогда не могут быть синхронизированы. (ru)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - En 1964 Jan Černý propuso que dado un AFD (Autómata finito determinista) sincronizable de estados, existe una palabra de sincronización(o palabra de reinicio) de longitud a lo sumo de .Este problema es uno de los más antiguos y famosos junto con Teorema del coloreo de carreteras en la teoría de Autómatas Finitos. Por otro lado, se ha visto que una cota superior en la longitud de la palabra de reinicio es de tamaño cúbico en , de donde la conjetura establecería que el tamaño de las cotas superiores de la longitud de dicha palabra, sería cuadrático (en ). (es)
- 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ý. (fr)
- In computer science, more precisely, in the theory of deterministic finite automata (DFA), a synchronizing word or reset sequence is a word in the input alphabet of the DFA that sends any state of the DFA to one and the same state. That is, if an ensemble of copies of the DFA are each started in different states, and all of the copies process the synchronizing word, they will all end up in the same state. Not every DFA has a synchronizing word; for instance, a DFA with two states, one for words of even length and one for words of odd length, can never be synchronized. (en)
- Em ciência da computação, mais precisamente, na teoria de autômato finito determinístico (AFD), uma palavra sincronizadora ou sequência de recomeço é uma palavra do alfabeto de entrada da AFD que envia qualquer estado da AFD para o mesmo e único estado. Isto é, se um conjunto de cópias de uma AFD são iniciadas em diferentes estados, e todas as cópias processam a palavra sincronizadora na mesma velocidade, elas irão no final alcançar o mesmo estado uma das outras, ao mesmo tempo. Nem toda AFD possui uma palavra sincronizadora; por exemplo, uma AFD com dois estados, um para palavras de tamanho par e outro para palavras de tamanho ímpar, jamais pode ser sincronizado. O problema de estimar o tamanho de palavras sincronizadoras possui uma longa história e vários autores propuseram-no independentemente, mas é comumente conhecido como a Conjectura de Černý . Em 1964 conjecturou que (n − 1)2 é o limitante superior para o comprimento da palavra sincronizadora mais curta para qualquer AFD completa de n estados (uma AFD com grafo de transição de estados completo). Se isso for verdade, seria ótimo: em um paper de 1964, Černý descreve uma classe de autômatos (indexados por seu número n de estados) para a qual as menores palavras sincronizadora possuem esse tamanho. O melhor limitante superior conhecido é (n 3 - n)/6, bem distante do limitante inferior.Para AFDs de n estados sob um alfabeto de entrada de k símbolos, um algoritmo de David Eppstein encontrou uma palavra sincronizadora de tamanho no máximo 11n3/48 + O(n2), que roda em complexidade de tempo O(n3+kn2). Este algoritmo nem sempre encontra a menor palavra sincronizadora possível para um dado autômato; como Eppstein também demonstra, o problema de achar a menor palavra sincronizadora é NP-completo. Entretanto, para uma classe especial de autômatos em que todas as transições de estados preservam a ordem cíclica dos estados, ele descreve um algoritmo diferente com tempo O(kn2) que sempre encontra a palavra sincronizadora mais curta, além de provar que tais autômatos necessariamente possuem uma palavra sincronizadora de tamanho máximo (n − 1)2 (o limite descrito pela conjectura de Černý), e exibe exemplos de autômatos com esse formato particular cujas palavras sincronizadora tem comprimento exato (n − 1)2. O problema da coloração de grafos é o problema de rotular cada aresta de um grafo regular dirigido com os símbolos de um alfabeto de tamanho k (em que k é o grau de saída de cada vértice) com o objetivo de formar uma AFD sincronizável. Foi conjecturado em 1970 por Benjamin Weiss e Roy Adler que qualquer digrafo fortemente conectado, aperiódico e regular pode ser rotulado dessa forma; a conjectura foi provada em 2007 por . (pt)
- В информатике, точнее, в теории детерминированных конечных автоматов (ДКА), синхронизирующее слово (или сжимающая последовательность) во входном алфавите автомата отображает все его состояния в одно и то же состояние. То есть, если слово стартует на ансамбле всех состояний автомата, проходя все ориентированные дуги с одинаковой скоростью, все пути завершатся одновременно в одном и том же состоянии. Не у каждого ДКА есть синхронизирующее слово, например, ДКА с двумя состояниями и циклами длины два никогда не могут быть синхронизированы. Проблема оценки длины синхронизирующего слова имеет долгую историю и была поставлена независимо несколькими авторами, но широко известной стала как гипотеза Черны. В 1964 году Ян Черны предположил, что (N — 1)2 является точной верхней границей для длины кратчайшего синхронизирующего слова для любого ДКА с N состояниями и К разноцветными исходящими ребрами из каждой вершины (ДКА с полным графом переходов). Черны еще в 1964 году нашел класс автоматов (с числом N состояний для любого натурального N), у которых кратчайшее синхронизирующее слово имеет эту длину. Лучшая известная верхняя граница для этой длины на сегодня равна (N3 — N) / 6 и далека от нижней границы. Для ДКА с N состояниями над алфавитом из K символов, алгоритм Дэвида Эпстайна находит синхронизирующее слово за время O(N3 + n2k) и с объемом памяти O(n2). В этой статье также доказана NP—полнота нахождения синхронизирующего слова минимальной длины. Проблема раскраски дорог является проблемой раскраски ребер регулярного ориентированного графа символами (цветами) входного алфавита из K символов, (где К является также полустепенью исхода каждой вершины) с целью формирования синхронизируемого ДКА. Бенджамин Вайсс и Рой Адлер в 1970 году высказали гипотезу, что у любого сильно связного орграфа с постоянной полустепенью исхода каждой вершины и равным единице наибольшим общим делителем длин всех циклов существует синхронизирующая раскраска. Их гипотеза была доказана в 2007 году Абрамом Трахтманом. (ru)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is differentFrom
of | |
| 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)
