Improved upper bounds on synchronizing nondeterministic automata

DOI10.1016/j.ipl.2009.05.007zbMath1200.68140OpenAlexW2014108239MaRDI QIDQ989550

Szabolcs Iván, Judit Nagy-György, Zsolt Gazdag

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.05.007

zbMATH Keywords

algorithmscombinatorial problems

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Formal languages and automata (68Q45)

Related Items (9)

Synchronization of Automata with One Undefined or Ambiguous Transition ⋮ Some results concerning careful synchronization of partial automata and subset synchronization of DFA's ⋮ Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Preset Distinguishing Sequences and Diameter of Transformation Semigroups ⋮ Semicomputable points in Euclidean spaces ⋮ Subset Synchronization and Careful Synchronization of Binary Finite Automata ⋮ Primitive Sets of Nonnegative Matrices and Synchronizing Automata ⋮ Distributed graph problems through an automata-theoretic Lens

Cites Work

• An extremal problem for two families of sets
• WORDS GUARANTEEING MINIMUM IMAGE
• On two Combinatorial Problems Arising from Automata Theory
• Theory Is Forever
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved upper bounds on synchronizing nondeterministic automata