DBpedia – Linked Data Fragments

Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Synchronizing_word> ?p ?o }

• Synchronizing_word abstract "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 which 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 at the same speed, they will all end up reaching the same state as each other, at the same time as each other. 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.The problem of estimating the length of synchronizing words has a long history and was posed independently by several authors, but it is commonly known as the Černý conjecture. In 1964 Jan Černý conjectured that (n − 1)2 is the upper bound for the length of the shortest synchronizing word for any n-state complete DFA (a DFA with complete state transition graph). If this is true, it would be tight: in his 1964 paper, Černý exhibited a class of automata (indexed by the number n of states) for which the shortest reset words have this length. The best upper bound known is (n 3 - n)/6, far from the lower bound. For n-state DFAs over a k-letter input alphabet, an algorithm by David Eppstein finds a synchronizing word of length at most 11n3/48 + O(n2), and runs in time complexity O(n3+kn2). This algorithm does not always find the shortest possible synchronizing word for a given automaton; as Eppstein also shows, the problem of finding the shortest synchronizing word is NP-complete. However, for a special class of automata in which all state transitions preserve the cyclic order of the states, he describes a different algorithm with time O(kn2) that always finds the shortest synchronizing word, proves that these automata always have a synchronizing word of length at most (n − 1)2 (the bound given in Černý's conjecture), and exhibits examples of automata with this special form whose shortest synchronizing word has length exactly (n − 1)2.The road coloring problem is the problem of labeling the edges of a regular directed graph with the symbols of a k-letter input alphabet (where k is the outdegree of each vertex) in order to form a synchronizable DFA. It was conjectured in 1970 by Benjamin Weiss and Roy Adler that any strongly connected and aperiodic regular digraph can be labeled in this way; their conjecture was proven in 2007 by Avraham Trahtman.".
• Synchronizing_word thumbnail Road_coloring_conjecture.svg?width=300.
• Synchronizing_word wikiPageExternalLink tarragona_volkov2008.pdf.
• Synchronizing_word wikiPageID "13667880".
• Synchronizing_word wikiPageLength "6060".
• Synchronizing_word wikiPageOutDegree "21".
• Synchronizing_word wikiPageRevisionID "692091490".
• Synchronizing_word wikiPageWikiLink Aperiodic_graph.
• Synchronizing_word wikiPageWikiLink Avraham_Trahtman.
• Synchronizing_word wikiPageWikiLink Big_O_notation.
• Synchronizing_word wikiPageWikiLink Category:Finite_automata.
• Synchronizing_word wikiPageWikiLink Computer_science.
• Synchronizing_word wikiPageWikiLink Cyclic_order.
• Synchronizing_word wikiPageWikiLink David_Eppstein.
• Synchronizing_word wikiPageWikiLink Degree_(graph_theory).
• Synchronizing_word wikiPageWikiLink Deterministic_finite_automaton.
• Synchronizing_word wikiPageWikiLink Directed_graph.
• Synchronizing_word wikiPageWikiLink Jan_Černý_(mathematician).
• Synchronizing_word wikiPageWikiLink NP-completeness.
• Synchronizing_word wikiPageWikiLink Regular_graph.
• Synchronizing_word wikiPageWikiLink Road_coloring_theorem.
• Synchronizing_word wikiPageWikiLink Roy_Adler.
• Synchronizing_word wikiPageWikiLink State_diagram.
• Synchronizing_word wikiPageWikiLink Strongly_connected_component.
• Synchronizing_word wikiPageWikiLink Time_complexity.
• Synchronizing_word wikiPageWikiLink Upper_and_lower_bounds.
• Synchronizing_word wikiPageWikiLink File:Road_coloring_conjecture.svg.
• Synchronizing_word wikiPageWikiLinkText "Synchronizing word".
• Synchronizing_word wikiPageWikiLinkText "synchronizing word".
• Synchronizing_word wikiPageUsesTemplate Template:Citation.
• Synchronizing_word wikiPageUsesTemplate Template:Cite_journal.
• Synchronizing_word wikiPageUsesTemplate Template:For.
• Synchronizing_word wikiPageUsesTemplate Template:Math.
• Synchronizing_word wikiPageUsesTemplate Template:Merge_from.
• Synchronizing_word wikiPageUsesTemplate Template:Reflist.
• Synchronizing_word wikiPageUsesTemplate Template:Unsolved.
• Synchronizing_word subject Category:Finite_automata.
• Synchronizing_word hypernym Word.
• Synchronizing_word type Food.
• Synchronizing_word type Conjecture.
• Synchronizing_word type Redirect.
• Synchronizing_word type Statement.
• Synchronizing_word type Statement.
• Synchronizing_word comment "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 which 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 at the same speed, they will all end up reaching the same state as each other, at the same time as each other.".
• Synchronizing_word label "Synchronizing word".
• Synchronizing_word sameAs Q7662204.
• Synchronizing_word sameAs Conjetura_de_Černý.
• Synchronizing_word sameAs xd7x94xd7xa9xd7xa2xd7xa8xd7xaa_xd7xa6xd7xa8xd7xa0xd7x99.
• Synchronizing_word sameAs Palavra_de_sincronia.
• Synchronizing_word sameAs m.03cdlxy.
• Synchronizing_word sameAs Синхронизируемое_слово.
• Synchronizing_word sameAs Q7662204.
• Synchronizing_word wasDerivedFrom Synchronizing_word?oldid=692091490.
• Synchronizing_word depiction Road_coloring_conjecture.svg.
• Synchronizing_word isPrimaryTopicOf Synchronizing_word.