The star-free closure

A language of finite words is star-free when it can be built from letters using Boolean operations and concatenation. A well-known theorem of Schützenberger characterizes star-free languages as those recognized by an aperiodic monoid. Another theorem of Schützenberger gives an alternate definition: these are the languages that can be built using product, union, and, in a limited way, Kleene star (but complement is now disallowed).

These definitions can be rephrased using closure operators operating on classes of languages. In this talk, we investigate these operators and generalize the results of Schützenberger. This is joint work with Thomas Place.

Date and Venue

Start Date
Venue
Online Zoom meeting
End Date

Speaker

Marc Zeitoun

Speaker's Institution

University of Bordeaux, France

Files

Area

Semigroups, Automata and Languages

Financiamento