A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [synchronization]

The tag has no usage guidance.

5 questions
Filter by
Sorted by
Tagged with
151 views

### A conjecture related to the Cerny conjecture - counterexample/reference request

The Cerny conjecture is the statement that any synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. The best current upper bound for the length of a ...
117 views

### Under what conditions is the Dining Philosophers Problem unsolvable?

The wikipedia article for the Dining Philosophers Problem lists some solutions which are dependent on external information, i.e.: Numbering of forks A waiter to act as mutex Messaging between ...
73 views

### Communication complexity of edit resilient synchronization

Supposing we have two strings $A$ and $B$ that are both edit distance $\tau$ from each other at two different sites is there a communication complexity model where synchronizing such strings have been ...
A deterministic automaton $\mathcal A = (X, Q, q_0, F, \delta)$ is called $k$-local for $k > 0$ if for every $w \in X^k$ the set $\{ \delta(q,w) : q \in Q \}$ contains at most one element. ...