Synchronizing Automata with Extremal Properties

DOI10.1007/978-3-662-48057-1_26zbMath1465.68154arXiv1608.01268OpenAlexW3100488283MaRDI QIDQ2946348

Marek Szykuła, Andrzej P. 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)

Related Items (11)

On the Number of Synchronizing Colorings of Digraphs ⋮ Checking Whether an Automaton Is Monotonic Is NP-complete ⋮ Unnamed Item ⋮ A Linear Bound on the k-rendezvous Time for Primitive Sets of NZ Matrices ⋮ Reset Complexity of Ideal Languages Over a Binary Alphabet ⋮ Slowly synchronizing automata with fixed alphabet size ⋮ Extremal synchronizing circular automata ⋮ An Extremal Series of Eulerian Synchronizing Automata ⋮ Černý's conjecture and the road colouring problem ⋮ Attainable Values of Reset Thresholds ⋮ The Synchronizing Probability Function for Primitive Sets of Matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kadanoff sand pile model. Avalanche structure and wave shape
• The Černý conjecture for one-cluster automata with prime length cycle
• The complexity of reasoning about knowledge and time. I: Lower bounds
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Synchronizing finite automata on Eulerian digraphs.
• Černý's conjecture and the road colouring problem
• Algebraic synchronization criterion and computing reset words
• ON A CONJECTURE BY CARPI AND D'ALESSANDRO
• THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE
• A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
• Modifying the Upper Bound on the Length of Minimal Synchronizing Word
• Reset Thresholds of Automata with Two Cycle Lengths
• Synchronizing Automata and the Černý Conjecture
• Slowly Synchronizing Automata and Digraphs
• Synchronizing Automata with a Letter of Deficiency 2
• SYNCHRONIZING QUASI-EULERIAN AND QUASI-ONE-CLUSTER AUTOMATA
• An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture

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