Improved upper bounds on synchronizing nondeterministic automata

DOI10.1016/J.IPL.2009.05.007zbMATH Open1200.68140OpenAlexW2014108239MaRDI QIDQ989550FDOQ989550

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

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

Recommendations

• Synchronizing non-deterministic finite automata
• On monogenic nondeterministic automata
• scientific article; zbMATH DE number 2106356
• scientific article; zbMATH DE number 2016847
• An improvement to a recent upper bound for synchronizing words of finite automata

zbMATH Keywords

algorithmscombinatorial problems

Mathematics Subject Classification ID

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

Cites Work

• An extremal problem for two families of sets
• On two Combinatorial Problems Arising from Automata Theory
• Title not available (Why is that?)
• WORDS GUARANTEEING MINIMUM IMAGE
• On monogenic nondeterministic automata
• Theory Is Forever
• Directable nondeterministic automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata
• Title not available (Why is that?)

Cited In (12)

• Synchronizing non-deterministic finite automata
• Preset distinguishing sequences and diameter of transformation semigroups
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• On monogenic nondeterministic automata
• Primitive sets of nonnegative matrices and synchronizing automata
• Subset synchronization and careful synchronization of binary finite automata
• Some results concerning careful synchronization of partial automata and subset synchronization of DFA's
• Distributed graph problems through an automata-theoretic Lens
• Synchronization of automata with one undefined or ambiguous transition
• Distributed graph problems through an automata-theoretic lens
• Semicomputable points in Euclidean spaces
• An improvement to a recent upper bound for synchronizing words of finite automata

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

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