arXiv Open Access 2012

The Cerny conjecture for automata respecting intervals of a directed graph

M. Grech A. Kisielewicz

Lihat Sumber

Abstrak

The Černý's conjecture states that for every synchronizing automaton with n states there exists a reset word of length not exceeding (n-11)^2. We prove this conjecture for a class of automata preserving certain properties of intervals of a directed graph. Our result unifies and generalizes some earlier results obtained by other authors.

Topik & Kata Kunci

cs.FL

Penulis (2)

M. Grech

A. Kisielewicz

Format Sitasi

APA MLA BibTeX

Grech, M., Kisielewicz, A. (2012). The Cerny conjecture for automata respecting intervals of a directed graph. https://arxiv.org/abs/1207.2556

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2012
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓