Improved upper bounds on synchronizing nondeterministic automata

DOI10.1016/j.ipl.2009.05.007zbMath1200.68140MaRDI 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

algorithms; combinatorial problems

Mathematics Subject Classification ID

68R05: Combinatorics in computer science

68Q45: Formal languages and automata

Related Items

Semicomputable points in Euclidean spaces, 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, Some results concerning careful synchronization of partial automata and subset synchronization of DFA's, Distributed graph problems through an automata-theoretic lens, Preset Distinguishing Sequences and Diameter of Transformation Semigroups, Subset Synchronization and Careful Synchronization of Binary Finite Automata, Synchronization of Automata with One Undefined or Ambiguous Transition, Primitive Sets of Nonnegative Matrices and Synchronizing Automata

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