World Library  
Flag as Inappropriate
Email this Article

Aperiodic finite state automaton

Article Id: WHEBN0017995149
Reproduction Date:

Title: Aperiodic finite state automaton  
Author: World Heritage Encyclopedia
Language: English
Subject: Range concatenation grammars, Thread automaton, Embedded pushdown automaton, Regular grammar, Deterministic context-free language
Collection: Automata Theory, Finite Automata, Formal Languages
Publisher: World Heritage Encyclopedia

Aperiodic finite state automaton

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


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

A counter-free language is a regular language for which there is an integer n such that for all words x, y, z and integers mn we have xymz in L if and only if xynz in L. A counter-free automaton is a finite-state automaton which accepts a counter-free language. A finite-state automaton is counter-free if and only if it is aperiodic.

An aperiodic automaton satisfies the Černý conjecture.[2]


  1. ^
  2. ^
  • — An intensive examination of McNaughton, Papert (1971).
  • — Uses Green's relations to prove Schützenberger's and other theorems.

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.