Synchronizing Automata with Extremal Properties

DOI10.1007/978-3-662-48057-1_26MaRDI QIDQ2946348zbMATH OpenOpenAlexFDO

Authors Marek Szykuła, Andrzej Kisielewicz

Publication date 16 September 2015

Published in Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We present a few classes of synchronizing automata exhibiting certain extremal properties with regard to synchronization. The first is a series of automata with subsets whose shortest extending words are of length $varTheta(n^2)$, where $n$ is the number of states of the automaton. This disproves a conjecture that every subset in a strongly connected synchronizing automaton is $cn$-extendable, for some constant $c$, and in particular, shows that the cubic upper bound on the length of the shortest reset words cannot be improved generally by means of the extension method. A detailed analysis shows that the automata in the series have subsets that require words as long as $n^2/4+O(n)$ in order to be extended by at least one element. We also discuss possible relaxations of the conjecture, and propose the image-extension conjecture, which would lead to a quadratic upper bound on the length of the shortest reset words. In this regard we present another class of automata, which turn out to be counterexamples to a key claim in a recent attempt to improve the Pin-Frankl bound for reset words. Finally, we present two new series of slowly irreducibly synchronizing automata over a ternary alphabet, whose lengths of the shortest reset words are $n^2-3n+3$ and $n^2-3n+2$, respectively. These are the first examples of such series of automata for alphabets of size larger than two.

Recommendations

• Synchronizing Automata and the Černý Conjecture
• Extremal synchronizing circular automata
• scientific article; zbMATH DE number 826076
• Synchronization and stability of finite automata
• Synchronization of finite automata
• Synchronizing automata with coinciding cycles
• scientific article; zbMATH DE number 1953272
• An extremal series of Eulerian synchronizing automata
• Synchronizing automata of bounded rank
• Synchronization of Regular Automata

Cites work

• scientific article; zbMATH DE number 846959 (Why is no real title available?)
• scientific article; zbMATH DE number 5593050 (Why is no real title available?)
• A note on a recent attempt to improve the Pin-Frankl bound
• A quadratic upper bound on the size of a synchronizing word in one-cluster automata
• An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Kadanoff sand pile model. Avalanche structure and wave shape
• Modifying the upper bound on the length of minimal synchronizing word
• On a conjecture by Carpi and D'Alessandro
• Slowly synchronizing automata and digraphs
• Synchronizing Automata and the Černý Conjecture
• Synchronizing Automata with a Letter of Deficiency 2
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing quasi-Eulerian and quasi-one-cluster automata
• The averaging trick and the Černý conjecture
• The complexity of reasoning about knowledge and time. I: Lower bounds
• The Černý conjecture for one-cluster automata with prime length cycle
• Černý's conjecture and the road colouring problem

Cited in

(33)

• Synchronizing automata with a letter of deficiency 2
• On the Number of Synchronizing Colorings of Digraphs
• On synchronizing unambiguous automata
• Reset complexity of ideal languages over a binary alphabet
• Hardly reachable subsets and completely reachable automata with 1-deficient words
• Semisimple synchronizing automata and the Wedderburn-Artin theory
• Slowly synchronizing automata and digraphs
• Dynamics of the independence number and automata synchronization
• Extensions to minimal synchronizing words
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• Attainable values of reset thresholds
• On randomized generation of slowly synchronizing automata
• Synchronizing Automata Preserving a Chain of Partial Orders
• Slowly synchronizing automata with fixed alphabet size
• Synchronizing Automata with a Letter of Deficiency 2
• Checking whether an automaton is monotonic is NP-complete
• Extremal synchronizing circular automata
• Synchronizing generalized monotonic automata
• Černý's conjecture and the road colouring problem
• Synchronizing times for \(k\)-sets in automata
• Deterministic synchronization of automata with bounded delay
• The Synchronizing Probability Function for Primitive Sets of Matrices
• Experiments with Synchronizing Automata
• Experiments on Synchronizing Automata
• An extremal series of Eulerian synchronizing automata
• scientific article; zbMATH DE number 1834666 (Why is no real title available?)
• Primitive digraphs with large exponents and slowly synchronizing automata
• Synchronizing quasi-Eulerian and quasi-one-cluster automata
• A series of slowly synchronizing automata with a zero state over a small alphabet
• A linear bound on the \(k\)-rendezvous time for primitive sets of NZ matrices
• Subset synchronization of transitive automata
• An improvement to a recent upper bound for synchronizing words of finite automata
• A tight linear bound on the synchronization delay of bijective automata

This page was built for publication: Synchronizing Automata with Extremal Properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946348)