Welcome to roadip.com on July 6 2009.
This is an internet experiment running to monitor browsing habbits of individuals through wikipedia contents.

Aperiodic finite state automaton

From Wikipedia, the free encyclopedia

Jump to: navigation, search

An aperiodic finite-state automaton is a finite-state automaton whose transition monoid is aperiodic.

[edit] Properties

A regular language is star-free if and only if it is accepted by an automaton with a finite and aperiodic transition monoid. This celebrated result of algebraic automata theory is due to Marcel-Paul Schützenberger.[1]

An aperiodic automaton satisfies the Cerny conjecture.[2]

[edit] References

  1. ^ Schützenberger, Marcel-Paul, "On finite monoids having only trivial subgroups," Information and Control, Vol 8 No. 2, pp. 190-194, 1965.
  2. ^ Trahtman. "The Cerny conjecture for aperiodic automata," Discrete Mathematics and Theoretical Computer Science, Vol 9 No. 2, pp. 133-138, 2007.
  This mathematics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org/wiki/Aperiodic_finite_state_automaton"
Personal tools
Visit joltnews for the latest headlines
Visit bloit.com for company information
Geed Media does computer consulting on long island.
This page viewed times. See Logs