View Related Documents

Abstract

The states of a finite automaton are ordered by height. This order is shown to be graduated, and the well-known Cerny problem on the minimal length of reset words can be formulated in terms of global height. The problem is proved for automata with four states.

finite automaton - linear automaton - ordered set - finite geometries - Cerny problem

Fulltext Preview

Image of the first page of the fulltext document