Skip to Main content Skip to Navigation
Book sections

Automata and expressions

J. Sakarovitch 1, 2
Abstract :

Not very many results in computer science are recognised as being as basic and fundamental as Kleene theorem. It was originally stated as the equality of two sets of objects, and is still so, even if the names of the objects have changed.

This chapter proposes a new look at this statement, in two ways. First, we explain how Kleene theorem can be seen as the conjunction of two results with distinct hypotheses and scopes. Second, we express the first of these two results as the description of algorithms that relate the symbolic descriptions of the objects rather than as the equality of two sets.

The main benefit of splitting Kleene theorem into two steps is to bring to light that the first one is a statement whose scope extends much beyond languages. It is first generalised to subsets of arbitrary monoids and then, with some precaution, to subsets with multiplicity, that is, to (formal power) series. This latter extension of the realm of Kleene's theorem is a matter for the same `splitting' and distinction between series on arbitrary monoids and series on f.g. free monoids.

Document type :
Book sections
Complete list of metadatas
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 4:04:40 PM
Last modification on : Wednesday, June 24, 2020 - 4:19:53 PM


  • HAL Id : hal-02286710, version 1



J. Sakarovitch. Automata and expressions. AutoMathA Handbook, European Mathematical Society, 2015. ⟨hal-02286710⟩



Record views