Language and Automata Theory and Applications: 5th International Conference, LATA 2011 Tarragona, Spain, May 2631, 2011Proceedings

Lecture Notes in Computer Science 6638

Commenced Publication in 1973

Founding and Former Series Editors:

Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board

David Hutchison

Lancaster University, UK

Takeo Kanade

Carnegie Mellon University, Pittsburgh, PA, USA

Josef Kittler

University of Surrey, Guildford, UK

Jon M. Kleinberg

Cornell University, Ithaca, NY, USA

Alfred Kobsa

University of California, Irvine, CA, USA

Friedemann Mattern

ETH Zurich, Switzerland

John C. Mitchell

Stanford University, CA, USA

Moni Naor

Weizmann Institute of Science, Rehovot, Israel

Oscar Nierstrasz

University of Bern, Switzerland

C. Pandu Rangan

Indian Institute of Technology, Madras, India

Bernhard Steffen

TU Dortmund University, Germany

Madhu Sudan

Microsoft Research, Cambridge, MA, USA

Demetri Terzopoulos

University of California, Los Angeles, CA, USA

Doug Tygar

University of California, Berkeley, CA, USA

Gerhard Weikum

Max Planck Institute for Informatics, Saarbruecken, Germany

Adrian-Horia Dediu Shunsuke Inenaga

Carlos Martín-Vide (Eds.)

Language and

Automata Theory

and Applications

5th International Conference, LATA 2011

Tarragona, Spain, May 26-31, 2011

Proceedings

13

Volume Editors

Adrian-Horia Dediu

Carlos Martín-Vide

Universitat Rovira i Virgili

Research Group on Mathematical Linguistics

Avinguda Catalunya, 35

43002 Tarragona, Spain

E-mail: {adrian.dediu; carlos.martin}@urv.cat

Shunsuke Inenaga

Kyushu University, Department of Informatics

744 Motooka, Fukuoka, 819–0395 Japan

E-mail: [email protected]

ISSN 0302-9743 e-ISSN 1611-3349

ISBN 978-3-642-21253-6 e-ISBN 978-3-642-21254-3

DOI 10.1007/978-3-642-21254-3

Springer Heidelberg Dordrecht London New York

Library of Congress Control Number: Applied for

CR Subject Classification (1998): F.1, F.4, F.2, I.2, J.3, I.4, I.5

LNCS Sublibrary: SL 1 – Theoretical Computer Science and General Issues

© Springer-Verlag Berlin Heidelberg 2011

This work is subject to copyright. All rights are reserved, whether the whole or part of the material is

concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,

reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication

or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,

in its current version, and permission for use must always be obtained from Springer. Violations are liable

to prosecution under the German Copyright Law.

The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply,

even in the absence of a specific statement, that such names are exempt from the relevant protective laws

and regulations and therefore free for general use.

Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India

Printed on acid-free paper

Springer is part of Springer Science+Business Media (www.springer.com)

Preface

These proceedings contain the papers that were presented at the 5th Interna￾tional Conference on Language and Automata Theory and Applications (LATA

2011), held in Tarragona, Spain, during May 26–31, 2011.

The scope of LATA is rather broad, including: algebraic language theory;

algorithms for semi-structured data mining; algorithms on automata and words;

automata and logic; automata for system analysis and program verification; au￾tomata, concurrency and Petri nets; cellular automata; combinatorics on words;

computability; computational complexity; computational linguistics; data and

image compression; decidability questions on words and languages; descriptional

complexity; DNA and other models of bio-inspired computing; document engi￾neering; foundations of finite-state technology; fuzzy and rough languages; gram￾mars (Chomsky hierarchy, contextual, multidimensional, unification, categorial,

etc.); grammars and automata architectures; grammatical inference and algo￾rithmic learning; graphs and graph transformation; language varieties and semi￾groups; language-based cryptography; language-theoretic foundations of artificial

intelligence and artificial life; neural networks; parallel and regulated rewriting;

parsing; pattern recognition; patterns and codes; power series; quantum, chem￾ical and optical computing; semantics; string and combinatorial issues in com￾putational biology and bioinformatics; string processing algorithms; symbolic

dynamics; term rewriting; transducers; trees, tree languages and tree machines;

and weighted machines.

LATA 2011 received 91 submissions. Each one was reviewed by four Program

Committee members, many of whom consulted with external referees. After a

thorough and lively discussion phase, the committee decided to accept 36 papers

(which represents an acceptance rate of 39.56%). The conference program also

included three invited talks and two invited tutorials. Part of the success in

the management of such a large number of submissions is due to the excellent

facilities provided by the EasyChair conference management system.

We would like to thank all invited speakers and authors for their contri￾butions, the Program Committee and the reviewers for their cooperation, and

Springer for its very professional publishing work.

March 2011 Adrian-Horia Dediu

Shunsuke Inenaga

Carlos Mart´ın-Vide

Organization

LATA 2011 was organized by the Research Group on Mathematical Linguistics

(GRLMC), Rovira i Virgili University, Tarragona, Spain.

Program Committee

Andrew Adamatzky Bristol, UK

Cyril Allauzen New York, USA

Amihood Amir Ramat-Gan, Israel

Franz Baader Dresden, Germany

Marie-Pierre B´eal Marne-la-Vall´ee, France

Philip Bille Lyngby, Denmark

Mikl´os B´ona Gainesville, USA

Symeon Bozapalidis Thessaloniki, Greece

Vasco Brattka Cape Town, South Africa

Maxime Crochemore London, UK

James Currie Winnipeg, Canada

Jurgen Dassow Magdeburg, Germany ¨

Cunsheng Ding Hong Kong, China

Rodney Downey Wellington, New Zealand

Manfred Droste Leipzig, Germany

Enrico Formenti Nice, France

Amy Glen Perth, Australia

Serge Haddad Cachan, France

Shunsuke Inenaga (Co-chair) Fukuoka, Japan

Jesper Jansson Tokyo, Japan

Jarkko Kari Turku, Finland

Marek Karpinski Bonn, Germany

Maciej Koutny Newcastle, UK

Gregory Kucherov Lille, France

Markus Lohrey Leipzig, Germany

Benedikt L¨owe Amsterdam, The Netherlands

Salvador Lucas Valencia, Spain

Sebastian Maneth Sydney, Australia

Carlos Mart´ın-Vide (Co-chair) Brussels, Belgium

Giancarlo Mauri Milan, Italy

Alexander Meduna Brno, Czech Republic

Kenichi Morita Hiroshima, Japan

Sven Naumann Trier, Germany

Gonzalo Navarro Santiago, Chile

Mark-Jan Nederhof St. Andrews, UK

Joachim Niehren Lille, France

VIII Organization

Joakim Nivre Uppsala, Sweden

Kemal Oflazer Doha, Qatar

Alexander Okhotin Turku, Finland

Witold Pedrycz Edmonton, Canada

Dominique Perrin Marne-la-Vall´ee, France

Giovanni Pighizzini Milan, Italy

Alberto Policriti Udine, Italy

Lech Polkowski Warsaw, Poland

Helmut Prodinger Stellenbosch, South Africa

Mathieu Raffinot Paris, France

Philippe Schnoebelen Cachan, France

Ayumi Shinohara Sendai, Japan

Jamie Simpson Perth, Australia

Magnus Steinby Turku, Finland

James Storer Boston, USA

Jens Stoye Bielefeld, Germany

Andrzej Tarlecki Warsaw, Poland

Richard Thomas Leicester, UK

Gy¨orgy Vaszil Budapest, Hungary

Heiko Vogler Dresden, Germany

Pascal Weil Bordeaux, France

Damien Woods Pasadena, USA

Thomas Zeugmann Sapporo, Japan

External Reviewers

B

Giorgio Bacci

Florent Becker

Djamal Belazzougui

B´eatrice B´erard

Alberto Bertoni

Dietmar Berwanger

Benedikt Bollig

Luca Bortolussi

Patricia Bouyer-Decitre

Matthias Buchse

¨

Wojciech Buszkowski

C

Antonio Cau

Jean-Marc Champarnaud

Christian Choffrut

Vincenzo Ciancia

Alexander Clark

Francisco Claude

Stefano Crespi Reghizzi

D

St´ephane Demri

Alberto Dennunzio

Alexander Dikovsky

Michael Domaratzki

Frank Drewes

Marie Duflot

Jacques Duparc

E

P´eter L. Erd¨os

F

Jacques Farr´e

John Fearnley

Organization IX

Gabriele Fici

Emmanuel Filiot

Francesca Fiorenzi

Andrea Formisano

Kimmo Fredriksson

Christiane Frougny

G

Dora Giammarresi

Robert Giegerich

Hugo Gimbert

Valentin Goranko

Archontia Grammatikopoulou

Pierre Guillon

H

Christoph Haase

Vesa Halava

Yo-Sub Han

Reiko Heckel

Jos´e Hern´andez-Orallo

Larry Holder

I

Daisuke Ikegami

Chuzo Iwamoto

J

Florent Jacquemard

Artur Je˙z

Timo Jolivet

K

Antonios Kalampakas

Tomi K¨arki

Victor Khomenko

Bakhadyr Khoussainov

Nguyen Kim

Daniel Kirsten

Felix Klaedtke

Bartek Klin

Vladimir Komendantsky

Eryk Kopczynski

Manfred Kufleitner

Orna Kupferman

Alexander Kurz

Dietrich Kuske

Temur Kutsia

L

Martin Lange

Jia Lee

Tommi Lehtinen

Aur´elien Lemay

Richard S. Lemence

Christof L¨oding

Sylvain Lombardy

Violetta Lonati

Jack Lutz

M

Andreas Maletti

Eleni Mandrali

Radu Mardare

Wim Martens

Miguel A. Mart´ınez-Prieto

Ingmar Meinecke

Neeldhara Misra

Benjamin Monmege

Niall Murphy

N

Turlough Neary

Kim Nguyen

Cyril Nicaud

Lasse Nielsen

Christos Nomikos

Dirk Nowotka

O

Friedrich Otto

P

Miguel Palomino

Christophe Papazian

Madhusudan Parthasarathy

David Pearce

Dominique Perrin

Tamar Pinhas

X Organization

Thomas Place

Franck Pommereau

Anne Preller

Q

Karin Quaas

R

Tomasz Radzik

George Rahonis

Narad Rampersad

Sarah Rees

Klaus Reinhardt

Andrei Romashchenko

Paolo Rosso

S

Carlo Sartiani

Sylvain Schmitz

Stefan Schwoon

G´eraud S´enizergues

Fr´ed´eric Servais

Jeffrey Shallit

Otakar Smrˇz

Christian Soltenborn

Andrei ¸Stef˘anescu

Howard Straubing

Mari Carmen Su´arez-Figueroa

Nathalie Sznajder

T

Kohtaro Tadaki

Jean-Marc Talbot

D. Gnanaraj Thomas

Jakob Thomsen

C˘at˘alin Tˆırn˘auc˘a

Cristina Tˆırn˘auc˘a

German Tischler

Sophie Tison

Alexandru I. Tomescu

Tayssir Touili

U

Irek Ulidowski

V

Camille Vacher

W

Thomas W¨achter

Dominic Welsh

Anthony Widjaja To

Roland Wittler

Ronald De Wolf

Paul Wollan

Z

Marc Zeitoun

Charalampos Zinoviadis

Organizing Committee

Adrian-Horia Dediu, Tarragona

Shunsuke Inenaga, Fukuoka (Co-chair)

Carlos Mart´ın-Vide, Brussels (Co-chair)

Bianca Truthe, Magdeburg

Florentina-Lilica Voicu, Tarragona

Table of Contents

Invited Talks

Green’s Relations and Their Use in Automata Theory ................ 1

Thomas Colcombet

Automatic Structures and Groups.................................. 22

Bakhadyr Khoussainov

Vector Addition System Reachability Problem: A Short Self-contained

Proof ........................................................... 41

J´erˆome Leroux

Abstract Numeration Systems ..................................... 65

Narad Rampersad

Regular Papers

Rule Formats for Distributivity .................................... 80

Luca Aceto, Matteo Cimini, Anna Ingolfsdottir,

Mohammad Reza Mousavi, and Michel A. Reniers

Mutation Systems................................................ 92

Dana Angluin, James Aspnes, and Raonne Barbosa Vargas

Classification of String Languages via Tiling Recognizable Picture

Languages ...................................................... 105

Marcella Anselmo, Dora Giammarresi, and Maria Madonia

A Simple and Efficient Universal Reversible Turing Machine ........... 117

Holger Bock Axelsen and Robert Gluck

¨

The Parameterized Complexity of Chosen Problems for Finite

Automata on Trees............................................... 129

Agata Barecka and Witold Charatonik

Recognizing Shuffled Languages.................................... 142

Martin Berglund, Henrik Bj¨orklund, and Johanna H¨ogberg

Unary Pattern Avoidance in Partial Words Dense with Holes .......... 155

Francine Blanchet-Sadri, Kevin Black, and Andrew Zemke

Characterizing Compressibility of Disjoint Subgraphs with NLC

Grammars ...................................................... 167

Robert Brijder and Hendrik Blockeel

XII Table of Contents

Partial Derivatives of an Extended Regular Expression................ 179

Pascal Caron, Jean-Marc Champarnaud, and Ludovic Mignot

Automatic Learning of Subclasses of Pattern Languages .............. 192

John Case, Sanjay Jain, Trong Dao Le, Yuh Shin Ong,

Pavel Semukhin, and Frank Stephan

Finite Orbits of Language Operations............................... 204

Emilie Charlier, Mike Domaratzki, Tero Harju, and Jeffrey Shallit ´

Finitary Languages............................................... 216

Krishnendu Chatterjee and Nathana¨el Fijalkow

The Complexity of Request-Response Games ........................ 227

Krishnendu Chatterjee, Thomas A. Henzinger, and Florian Horn

Improved Alignment Based Algorithm for Multilingual Text

Compression .................................................... 238

Ehud S. Conley and Shmuel Tomi Klein

Singular Artin Monoids of Finite Coxeter Type Are Automatic ........ 250

Ruth Corran, Michael Hoffmann, Dietrich Kuske, and

Richard M. Thomas

Networks of Evolutionary Processors with Subregular Filters .......... 262

Jurgen Dassow, Florin Manea, and Bianca Truthe ¨

Decision Problems for Interval Markov Chains ....................... 274

Benoˆıt Delahaye, Kim G. Larsen, Axel Legay,

Mikkel L. Pedersen, and Andrzej W

asowski

Classifying Regular Languages via Cascade Products of Automata ..... 286

Marcus Gelderie

The Block Structure of Successor Morphisms ........................ 298

Jana Hadravov´a

Models for Quantitative Distributed Systems and Multi-Valued

Logics .......................................................... 310

Martin Huschenbett

A Local Greibach Normal Form for Hyperedge Replacement

Grammars ...................................................... 323

Christina Jansen, Jonathan Heinen, Joost-Pieter Katoen, and

Thomas Noll

Unique Small Subgraphs Are Not Easier to Find ..................... 336

Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell

Table of Contents XIII

Simplifying DPDA Using Supplementary Information ................. 342

Pavel Labath and Branislav Rovan

Normalization of Sequential Top-Down Tree-to-Word Transducers ...... 354

Gr´egoire Laurence, Aur´elien Lemay, Joachim Niehren,

Slawek Staworko, and Marc Tommasi

Planarity of Knots, Register Automata and LogSpace Computability ... 366

Alexei Lisitsa, Igor Potapov, and Rafiq Saleh

Tarski’s Principle, Categorial Grammars and Learnability ............. 378

Jacek Marciniec

Globally Deterministic CD-Systems of Stateless R(1)-Automata ........ 390

Benedek Nagy and Friedrich Otto

Bit-coded Regular Expression Parsing .............................. 402

Lasse Nielsen and Fritz Henglein

Descriptional Complexity of Unambiguous Nested Word Automata ..... 414

Alexander Okhotin and Kai Salomaa

Avalanche Structure in the Kadanoff Sand Pile Model ................ 427

K´evin Perrot and Eric R´emila

Well-Quasi-Ordering Hereditarily Finite Sets ........................ 440

Alberto Policriti and Alexandru I. Tomescu

On the Interval-Bound Problem for Weighted Timed Automata ........ 452

Karin Quaas

Finding Shuffle Words That Represent Optimal Scheduling of Shared

Memory Access .................................................. 465

Daniel Reidenbach and Markus L. Schmid

Syntactic Complexity of Ultimately Periodic Sets of Integers........... 477

Michel Rigo and Elise Vandomme ´

Undecidability of the State Complexity of Composed Regular

Operations ...................................................... 489

Arto Salomaa, Kai Salomaa, and Sheng Yu

Restarting Automata with Auxiliary Symbols and Small Lookahead .... 499

Natalie Schluter

Author Index .................................................. 511

Green’s Relations

and Their Use in Automata Theory

Thomas Colcombet

Liafa/Cnrs/Université Paris Diderot–Paris 7, France

[email protected]

Abstract. The objective of this survey is to present the ideal theory of

monoids, the so-called Green’s relations, and to illustrate the usefulness

of this tool for solving automata related questions.

We use Green’s relations for proving four classical results related to

automata theory: The result of Schützenberger characterizing star-free

languages, the theorem of factorization forests of Simon, the characteri￾zation of infinite words of decidable monadic theory due to Semenov,

and the result of determinization of automata over infinite words of

McNaughton.

Introduction

In this lecture, we will establish several classical results related to automata

theory, respectively due to Schützenberger, Simon, Semenov, and McNaughton.

These problems are all related in a more or less direct way to language theory

and automata. Despite their obvious intrinsic interest, these results will be for us

excuses for presenting the approach via monoids and semigroups which allows

to uniformly apprehend these, a priori unrelated, questions. That is why this

lecture is structured as the interleaving of the proofs of the above results with

the necessary algebraic material.

We devote a particular attention to the theory of ideals in monoids, the so

called Green’s relations. When working in language theory using automata, sev￾eral tools comes naturally into play. A typical example is the use of the decom￾position of the graph of the automaton into strongly connected components, and

the use of the dag of the connected components for driving an induction in a

proof. The Green’s relations provide the necessary tools for using similar argu￾ments on the monoid rather than on the automaton. Since monoids are more

informative than automata, the resulting techniques are more powerful than the

corresponding ones on automata (this gain usually comes at the price of a worth

complexity in decision procedures and constructions). The Green’s relations are

well known, and presented in deep detail in several places, see for instance

[5,13]. For this reason we do not establish here the results related to this theory.

Supported by the project ANR 2010 BLAN 0202 02 FREC, and the ERC Starting

Grant GALE.

A.-H. Dediu, S. Inenaga, and C. Martín-Vide (Eds.): LATA 2011, LNCS 6638, pp. 1–21, 2011.

c Springer-Verlag Berlin Heidelberg 2011

2 T. Colcombet

We do not try either to be exhaustive in any way. Our goal is different. We are

interested in illustrating how to use this tool.

We use four classical results as illustrations. The first one is the theorem of

Schützenberger [17] characterizing the languages which can be described by star￾free expressions. The second one is the theorem of factorization forests of Simon

[19], which gives a form of generalized Ramsey argument for regular languages.

The third one is a theorem of Semenov [18] which gives a necessary and sufficient

condition for an infinite word to have a decidable monadic second-order theory.

The fourth theorem, due to McNaughton [9], states that automata over infinite

words can be made deterministic.

The lecture is structured as follows. We first briefly recall some basic defi￾nitions concerning semigroups and monoids in Section 1. We then present the

results of Schützenberger and Simon in Section 2 and 3 respectively. We then

introduce the framework of ω-semigroups in Section 4, and use it for establishing

the results of semenov and McNaughton in Sections 5 and 6 respectively.

1 Basics on Monoids

A monoid M is a set together with an associative binary operator · which has a

neutral element denoted 1 (such that 1x = x1 = x for all x). An element e such

that ee = e is called an idempotent. A monoid morphism from a monoid M to

another M is an application from M to M such that α(1) = 1, and α(ab) =

α(a)α(b) for all a, b in M.

A particular example is the free monoid generated by a set A, it is the set of

words over the alphabet A equipped with the concatenation product. The neutral

element is ε. An example of a finite monoid consists of the two elements a, b

equipped with the product aa = ab = ba = a, and bb = b.

A language L ⊆ A∗ is recognizable by a monoid (M, ·) if there exists a mor￾phism α from A∗ to M and a subset F ⊆ M such that L = α−1(F).

Theorem 1 (Rabin and Scott [16] with credit to Myhill). A language of

finite words over a finite alphabet is regular (i.e., accepted by some standard form

of finite state automaton) if and only if it is recognizable by a finite monoid.

Given a language L there is a particular, minimal, monoid which recognizes it,

the syntactic monoid. The syntactic monoid of a language L over the alphabet A

is an object gathering the minimal amount of information for each word that is

relevant for the language. This is obtained by a quotient of words by the so-called

syntactic congruence ∼L. Two words are equivalent for this relation if they are

undistinguishable by the language in any context. Formally, two words u and v

are equivalent for a language L is defined as:

u ∼L v if for all x, y ∈ A∗, xuy ∈ L iff xvy ∈ L .

If two words are equivalent for ∼L, this means that in any context, one can

safely exchange one for the other. In particular, as its name suggest, ∼L is a

Green’s Relations and Their Use in Automata Theory 3

congruence, i.e., u ∼L v and u ∼L v implies uu ∼L vv

. This means that

the equivalence classes for ∼L can be equipped with a product. The resulting

quotiented monoid ML = A∗/∼L is called the syntactic monoid of L. Further￾more, the application ηL which to a word associates its equivalence class is a

morphism, called the syntactic morphism.

In particular, setting F = ηL(L), we have u ∈ L if and only if ηL(u) ∈ F. In

other words, the syntactic monoid ML recognizes L using the morphism ηL and

the subset F = ηL(L) ⊆ ML.

For instance, consider the language over the alphabet A = {a, b, c} consisting

of “all words which do not contain two consecutive occurrences of the letter a”.

The equivalence classes of the syntactic monoid are ε, a((b+c)+a)∗, (a(b+c)+)+,

((b+c)+a)+, (b+c)+(a(b+c)+)∗ and A∗aaA∗. We will denote them by 1, a, ab,

ba, b and 0 respectively. The notations 1 and 0 are conventional, and correspond

to the neutral and the absorbing element (absorbing means 0x = x0=0; such an

element is unique, but does not always exist). For the other congruence classes,

one fixes a word as representative. The product xy of any two elements x and y

of the monoid is given in the following table:

x\y 1 a ab ba b 0

1 1 a ab ba b 0

a a 0 0 a ab 0

ab ab a ab a ab 0

ba ba 0 0 ba b 0

b b ba b ba b 0

0 0 0 0 0 00

The language “no two consecutive occurrences of letter a” is recognized by this

monoid, together with the morphism which maps letter a to a and letters b and c

to b, and the subset F = {1, a, ab, ba, b}.

We see on this example that the table of product is not very informative for

understanding the structure of the monoid. Natural tools, such as the strongly

connected components of the graph of the automaton, are frequently used to

design proofs and constructions in automata theory. We do not see immediately

anything similar in monoids. The Green’s relations that we present below gives

such an insight in the structure of the monoid. Even better, since the syntactic

monoid is more informative than the minimal automaton (at a price: it is also

bigger), the structure of the syntactic monoid reveals even more information

than the analysis of the minimal automaton.

Furthermore, the syntactic monoid is something one can work with:

Proposition 1. The syntactic monoid is finite iff the language is regular. Fur￾thermore, the syntactic monoid of a regular language can be effectively computed

from any presentation of the language (by automata, regular expressions, etc...)

4 T. Colcombet

2 Schützenberger’s Characterization of Star-Free

Languages

Our first result concerns star-free languages. The star-free languages are the

languages of finite words which can be obtained from finite languages using

union, concatenation and complement (of course, intersection and set difference

can be derived from the union and complement).

An example is simply A∗ (for A the alphabet), which is star-free since it is the

complement of the empty language, which is itself finite. More generally, B∗ for

all subsets B of A is star-free since it can be written as A∗ \ (

c∈B A∗cA∗). Very

close is the language of words over A = {a, b, c} containing no two consecutive

occurrences of the letter a. It is star-free since it can be written as A∗ \(A∗aaA∗).

However, the language of words of even size is not star-free (we do not prove it

here). In general, all star-free languages are regular, but the converse does not

hold. This motivates the following question:

When is a regular language star-free? Is it decidable?

Schützenberger answered the above question as follows:

Theorem 2 (Schützenberger[17]). A regular language is star-free iff it is

recognized by a monoid which has only trivial subgroups1.

This famous result is now well understood and has been enriched in many ways.

In particular, star-free languages are known to coincide with first-order definable

languages as well as with the languages accepted by counter-free automata [10].

This result was the starting point of the very important literature aiming in

precisely classifying families of languages. See for instance [14].

This result in particular establishes the decidability of being star-free. Indeed,

if any monoid recognizing a language has only trivial subgroups, then its syntac￾tic monoid has only trivial subgroups. This yields a decision procedure: construct

the syntactic monoid of the language and check that all its subgroups are trivial.

The later can be done by an exhaustive check.

We will only prove here the right to left direction of Theorem 2, namely,

if a regular language is recognized by some (finite) monoid with only trivial

subgroups, then it is star-free. The interested reader can find good expositions

of the other directions in many places, see for instance [11]. We assume from

now and on that we are given a language L recognised by M, α, F, in which M

is a finite monoid which has only trivial subgroups.

The general approach of the proof is natural. For all elements a ∈ M, we

prove that the language La

def

= {u ∈ A : α(u) = a} is star-free. This concludes

the proof of the right to left direction of Theorem 2, since it yields that

L = α−1(F) =

a∈F

La is star-free.

1 Here, a subgroup is a subset of the monoid which is equipped of a group struc￾ture by the product of the monoid. This terminology is the original one used by

Schützenberger. It is natural in the general context of semigroup theory.