Algebraic synchronization criterion and computing reset words

DOI10.1016/j.ins.2016.07.049zbMath1428.68192arXiv1412.8363OpenAlexW1782076687MaRDI QIDQ2282077

Marek Szykuła, Mikhail V. Berlinkov

Publication date: 6 January 2020

Published in: Information Sciences, Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.8363

zbMATH Keywords

prefix codeHuffman codereset wordČerný conjecturesynchronizing automatonrandom automaton

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Algebraic theory of languages and automata (68Q70) Prefix, length-variable, comma-free codes (94A45)

Related Items (17)

Strongly connected synchronizing automata and the language of minimal reset words ⋮ Unnamed Item ⋮ Some results concerning careful synchronization of partial automata and subset synchronization of DFA's ⋮ Synchronizing Automata with Extremal Properties ⋮ Synchronizing automata with coinciding cycles ⋮ Synchronizing sequences for road colored digraphs ⋮ New characterizations of primitive permutation groups with applications to synchronizing automata ⋮ Unnamed Item ⋮ Preimage problems for deterministic finite automata ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ A bound for the length of the shortest reset words for semisimple synchronizing automata via the packing number ⋮ Algebraic synchronization criterion and computing reset words ⋮ Analytic methods for reachability problems ⋮ An Extremal Series of Eulerian Synchronizing Automata ⋮ Experiments with Synchronizing Automata ⋮ Černý's conjecture and the road colouring problem ⋮ Sync-maximal permutation groups equal primitive permutation groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primitive digraphs with large exponents and slowly synchronizing automata
• The Černý conjecture for one-cluster automata with prime length cycle
• Shortest synchronizing strings for Huffman codes
• Synchronization
• An extremal problem for two families of sets
• Synchronizing finite automata on Eulerian digraphs.
• Approximating the minimum length of synchronizing words is hard
• Independent sets of words and the synchronization problem
• Černý's conjecture and the road colouring problem
• Algebraic synchronization criterion and computing reset words
• On the Probability of Being Synchronizable
• Experiments with Synchronizing Automata
• THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE
• On Two Algorithmic Problems about Synchronizing Automata
• Strong Inapproximability of the Shortest Reset Word
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• Approximating Minimum Reset Sequences
• A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
• Compact noncontraction semigroups of affine operators
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• Almost all complete binary prefix codes have a self-synchronizing string
• Slowly Synchronizing Automata and Digraphs
• The Complexity of Finding Reset Words in Finite Automata
• Shortest Synchronizing Strings for Huffman Codes
• A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
• On two Combinatorial Problems Arising from Automata Theory
• SYNCHRONIZING QUASI-EULERIAN AND QUASI-ONE-CLUSTER AUTOMATA

This page was built for publication: Algebraic synchronization criterion and computing reset words