✦ LIBER ✦

On the bound of the synchronization delay of a local automaton

✍ Scribed by Marie-Pierre Béal; Jean Senellart

Book ID: 104326671
Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 600 KB
Volume: 205
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(98)80011-x

No coin nor oath required. For personal study only.

✦ Synopsis

The synchronization delay of an N-state local automaton is known to be 0(N2). It has been conjectured by Kim et al. (1991) that, for deterministic local automata, it is O(N") on a twoletter alphabet and no less than O(N2) in the general case. We prove that this conjecture is false and that the synchronization delay is n(N*) in all cases.

📜 SIMILAR VOLUMES

In extremal combinatorial problem associ

In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton

✍ A. A. Klyachko; I. K. Rystsov; M. A. Spivak 📂 Article 📅 1987 🏛 Springer US 🌐 English ⚖ 783 KB

Bounds on the length of the diagnostic w

Bounds on the length of the diagnostic word of a finite automaton

✍ M. N. Sokolovskii 📂 Article 📅 1977 🏛 Springer US 🌐 English ⚖ 455 KB

The Synchronizing Probability Function o

The Synchronizing Probability Function of an Automaton

✍ Jungers, Raphaël M. 📂 Article 📅 2012 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 409 KB

Verification of synchronous-automaton pr

Verification of synchronous-automaton programs with the use of LTL

✍ S. V. Kubasov 📂 Article 📅 2010 🏛 Allerton Press Inc 🌐 English ⚖ 113 KB

On the attainable upper bound of the len

On the attainable upper bound of the length of the minimal adjustment experiment for a Moore automaton

✍ A. M. Bogomolov; I. S. Grunskii 📂 Article 📅 1973 🏛 Springer US 🌐 English ⚖ 119 KB

On synchronization of a forced delay dyn

On synchronization of a forced delay dynamical system via the Galerkin approximation

✍ Dibakar Ghosh; Papri Saha; A. Roy Chowdhury 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 761 KB

A forced scalar delay dynamical system is analyzed from the perspective of bifurcation and synchronization. In general first order differential equations do not exhibit chaos, but introduction of a delay feedback makes the system infinite dimensional and shows chaoticity. In order to study the dynam