Synchronizing Automata with Extremal Properties

DOI10.1007/978-3-662-48057-1_26zbMATH Open1465.68154arXiv1608.01268OpenAlexW3100488283MaRDI QIDQ2946348FDOQ2946348

Authors: Marek Szykuła, Andrzej Kisielewicz 

Publication date: 16 September 2015

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

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.

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

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

Cited In (32)

• Synchronizing automata with a letter of deficiency 2
• On the Number of Synchronizing Colorings of Digraphs
• Reset complexity of ideal languages over a binary alphabet
• On synchronizing unambiguous automata
• 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
• Synchronizing Automata with a Letter of Deficiency 2
• Slowly synchronizing automata with fixed alphabet size
• 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
• The Synchronizing Probability Function for Primitive Sets of Matrices
• Synchronizing times for \(k\)-sets in automata
• Deterministic synchronization of automata with bounded delay
• Experiments with Synchronizing Automata
• Experiments on Synchronizing Automata
• An extremal series of Eulerian synchronizing automata
• Title not available (Why is that?)
• Synchronizing quasi-Eulerian and quasi-one-cluster automata
• 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 series of slowly synchronizing automata with a zero state over a small alphabet
• 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)