Solomon Marcus
Stoilow Institute of Mathematics
Romanian Academy
[email protected]
1 Bourbaki Mathematics and the Theory of Formal Languages Contrasts and Complementarity within Similarities
2 A. Salomaa and G. Rozenberg versus H.Cartan and A. Weil
3 Primacy of the Axiomatic-Deductive Approach
4 Primacy of Structure against Quantity
5 Past Dominated by Disorder, Low Level of Rigor, Atomistic View
Concomitant with the Emergence of Important New Trends
6 Link with the Fields of Social Sciences and the Humanities
7 Contrasting Attitudes towards Foundations and Mathematical Logic
8 Lack of Balance between the Discrete and the Continuous
9 The Rise of Cognitive Metaphors
10 And Now a Magic Event: Von Neumann, Watson-Crick, Salomaa
11 The Calculation-Observation Interplay and How History Repeats Itself
Bourbaki Mathematics and the
Theory of Formal Languages Contrasts and Complementarity
within Similarities
Bourbaki project starts in 1935 and aims to rewrite mathematics taking
into account the major developments which occurred in the period from
1890 until 1935:
● set theory,
● non-commutative algebra,
● linear representations of groups,
● general and algebraic topology,
● Lebesgue theory of measure and integral,
● functional analysis,
● theory of integral equations,
● spectral theory,
● Hilbert spaces,
● Lie groups and their representations.
Bourbaki project starts in 1935 and aims to rewrite mathematics taking
into account the major developments which occurred in the period from
1890 until 1935:
A Similar Change, concerning the effectiveness of the
mathematical thinking, occurred between 1930 and 1973, the year
of publication of the book Formal Languages by Arto Salomaa.
In this period, new domains and trends emerged, such as:
● the theory of recursive functions (Kleene, Gödel),
● mathematical logic,
● theory of algorithms (Markov),
● of computability (Turing),
● Post combinatorial systems,
● symbolic dynamics (Morse and Hedlund),
● combinatorics and algebra of semigroups and monoids
(a pioneer in this respect being Axel Thue),
● Shannon’s isomorphism between mathematical logic and
electric circuits,
● automata theory and its interaction with biology,
● computer science (von Neumann),
● cybernetics (Norbert Wiener),
● coding theory (Hamming),
● generative grammars (Chomsky),
● information theory (Shannon).
● etc.
A. Salomaa and G. Rozenberg
H.Cartan and A. Weil
Obviously, it was not possible for one person, under the name of
Nicolas Bourbaki, to monitor such a diversity and richness of ideas,
theories and results.
It was initially a group of about seven very young mathematicians, in
alphabetic order:
Chevalley Delsarte
Szolem René de
Dieudonné Mandelbrojt Possel
But later, some of them left the group and new scholars were added.
The project started in 1935.
Now we can say that Cartan and Weil proved to be the most creative
and perhaps the most active in this project.
With respect to the project started by the 1969 and 1973 books of Arto
Salomaa, we now can say that the series of works published by Arto
and his associates, culminating with the 1997 Handbook of Formal
Languages, is comparable with the series of fascicles published by
Bourbaki in the decades before and after the middle of the past
Moreover, we may claim that Arto and
Grzegorz proved to play in this project
the role Cartan and respectively Weil
played in the Bourbaki project.
I have personal reasons to believe this because I had the privilege to
read and to review the correspondence between Cartan and Weil, a
volume of about thousand pages.
Primacy of the
Axiomatic-Deductive Approach
Just like in the case of Bourbaki, whose project adopted the
axiomatic-deductive method as its basic approach, in the line of
achievements of the whole history, from the non-Euclidean
geometries, until Peano’s axiomatics of arithmetics and Hilbert’s
axiomatics of geometry, Salomaa and his associates adopted the
axiomatic-deductive approach, in full agreement with the
developments of the period 1930-1973, in the form of systems of
objects, behaving according to some explicit rules.
The reason for this choice is exactly the same one as it was for
Bourbaki: the need for rigor, for logical accuracy, the need to check
carefully the correctness of the inferences of various kinds, the
coherence of the statements.
In a period of emergence of new ideas, changing radically the
existing habits of our brain, the danger of penetration of wrong or
misleading statements is increasing.
For Bourbaki, the domination exerted in France, in the teaching of
mathematical analysis, by the treatise of Edouard Goursat, was
One of Bourbaki’s main aims was therefore to promote the rigor
introduced by Cauchy, Riemann and Weierstrass, and developed
further by the next generations.
In the field of formal languages, the literature published before
1973 counts more than thousand items, but it is full of obscurities,
while mistakes are frequent.
I will mention the case of the most important article and book,
Three Models for the Description of Language (1956) (2190
citations) and Syntactic Structures (1957), (15.452 citations) both
by Noam Chomsky.
In the presentation of the 1957 book, included on the web page of
Google Scholar, it is considered to be
“… the snowball which began the avalanche of the modern
«cognitive revolution». The cognitive perspective originated in the
17th century and now characterizes modern linguistics as part of
psychology and human biology”.
These pioneering Chomskian items are obviously cited already in
the first chapter of Salomaa’s book, as source of the generative
However, with respect to logical correctness, the proofs proposed
by Chomsky are wrong, as I have shown in two publications in
French (C.R. Acad. Sci. Paris 256, 1963, 17, 357-3574 and Cahiers
de Ling. Th. et Appl. 2, 1965, 146-164).
This fact seems to be symptomatic for many pioneering works.
Directing the attention towards something new is paid by failures in
other respects.
Primacy of Structure
against Quantity
However, axiomatic-deductive approach, very necessary, was not
In order to prove that mathematics is not a conglomerate of various
disparate fields, each of them on its own, but, on the contrary,
these apparently heterogeneous fields have a deep common
denominator, they are parts of a unique organism, there are some
patterns going across the whole mathematics, working as a
unification principle.
It was necessary to identify some basic types of structures, the
same for all mathematical fields.
Three types of structures were identified:
● Order Structures,
● Algebraic Structures
(the main in this respect being the Transformation Group,
introduced by Evariste Galois and playing a basic role in
Felix Klein’s Erlangen Programme)
● Topological Structures.
However, some mathematical fields proved to be unable to be
approached in this way and this was the price Bourbaki had to pay
in order to realize its structural unification.
These three types of structures, both general enough and specific
enough, provided the unification language developed by the
Bourbaki programme.
A similar need appeared in the project developed by Arto and his
Obviously, they took advantage from the types of structures
promoted by Bourbaki project.
But the structural protagonists in their approach, as in most fields
under their examination, were different:
● the Semigroup
(with special attention to the Free Semigroup),
● the Monoid
● the Rewriting System
including, as particular cases, the Generative Formal Grammar,
the Analytic Grammar, the various types of Automaton, the
Formal System of various types, the Combinatorial System, etc.
5 and 5’
Past Dominated by Disorder,
Low Level of Rigor, Atomistic View
Concomitant with the Emergence
of Important New Trends
The similarity between the disorder of the period before 1935 and
the disorder of the period before 1973 was already pointed out.
This topic can be further investigated, with many examples of
● lack of rigor,
● mistakes, inaccuracies,
● inconsequence in definitions and in terminology and notation
● etc.
Link with the Fields of
Social Sciences and
the Humanities
Bourbaki’s project has been historically linked with the proliferation
of interest for structures, coming from exact and from natural
sciences (Galois’s group, chemical isomerism, the nature of
heredity), but mainly from social sciences (linguistics, economics,
anthropology) and from humanities (psychology – see Jean
Piaget’s book Le Structuralisme Presses Universitaires de France,
where the group structure is considered to have universal
relevance) and from visual arts (see the collaboration between
Escher and Coxeter), which are mostly interested in this notion.
Many literary and social events such as the French literary group
Oulipo, including the writer Italo Calvino, were developed in
solidarity with Bourbaki’s project.
See, for more, Amir D. Aczel - The Artist and the Mathematician –
The Story of Nicolas Bourbaki, the Genius Mathematician Who
Never Existed, London, High Stakes Publishing, 2007.
Formal languages have as one of their fundamental source the field
of linguistics.
The motivation guiding Noam Chomsky in the introduction of
generative grammars came from his interest in natural languages.
Only later, at the beginning of the 7th decade of the past century,
scholars interested in computer programming languages realized
that the generative grammars proposed by Chomsky for natural
languages are the right tool to investigate the syntax and the
semantics of programming languages.
So it happened that formal generative grammars revealed their new
face: their theory became just the theory of computer programming
But let us quote in this respect a stronger statement, from the
preface by Grzegorz Rozenberg and Arto Salomaa to the first
volume of the Handbook of Formal Languages:
“The theory of formal languages constitutes the stem or backbone
of the field of science now generally known as theoretical computer
science. In a very true sense, its role has been the same as that of
philosophy with respect to science in general”.
So, it is acknowledged the fact that computer programming
languages are structured according to natural languages and that
the whole field of computer science is build taking as a term of
reference the architecture of natural languages.
Obviously, these statements should not be interpreted in a trivial
way; it is well-known that the relevance of context free grammars
for natural languages (particularly for English) is still under debate,
after a long period when this question seemed to be clarified.
Many other faces of the interaction between formal languages and
the social field and the humanities could be considered and we
send the reader to Solomon Marcus: “Formal Languages:
Foundations, Prehistory, Sources and Applications” in Formal
Languages and Applications (Eds: Carlos Martin Vide, Victor
Mitrana, Gheorghe Paun), Number 148 in the series “Studies in
Fuzziness and Softcomputing”, Berlin, Springer, 2004, 11-53.
7 and 7’
Contrasting Attitudes
towards Foundations and
Mathematical Logic
It is interesting to observe that the structure of a semigroup was
investigated by algebraists before coming to be investigated by
computer scientists, but their books are very different because their
interests were completely different.
Here we have an aspect of the strong contrast between Bourbaki’s
project and Salomaa’s project.
Bourbaki ignored fields such as foundations, probability,
mathematical logic and combinatorics, just the fields of highest
relevance for Salomaa’s project and for the whole project related to
Here we realize again the complementarity of their projects.
8 and 8’
Lack of Balance
the Discrete and the Continuous
It is clear that Bourbaki favoured the continuous, according
to the whole tradition of the 19th century, while Arto’s project
involved mainly the discrete aspects.
In this respect their complementarity is almost total.
We need both of them, because we need the achievements
of both hemispheres of the brain, keeping a right balance
between them.
Bourbaki and Salomaa are brothers.
9 and 9’
The Rise of Cognitive Metaphors
We close our Bourbaki - Salomaa comparative analysis by referring
to their affinity for expressive, metaphorical terms.
Most mathematicians ignore that the today standard notation and
terminology in mathematics was introduced by Bourbaki:
► The notation for
● The empty set
● The natural numbers N
● The integers Z
● The rationals Q
● The reals R
● The complex numbers C
● The relations of inclusion
● The strict inclusion between sets
● The operations with sets:
union ; intersection ; difference \ (or –); Cartesian product
All of them are using the basic metonymic or metaphorical
procedures (see the similarity with signs used to express
relations between numbers),
► The expressive way to denote the basic terms in modern
algebra with reference to the authors of the respective notions
► Terms such as
● Injective,
● Bijective
● Surjective
All of them belong to Bourbaki.
A happy cognitive-creative metaphor, emerging from authors such as
Noam Chomsky – Marcel Paul Schutzenberger, Jean Berstel and I.
Boisson, is to call regular languages rational languages and contextfree languages algebraic languages
The link with the respective classes of real numbers proved to be
very strong and it is still open to interesting unanswered questions.
And Now a Magic Event,
involving Von Neumann,
Watson-Crick, Salomaa
Let us refer now to Salomaa’s Watson-Crick automata.
This creative metaphor acquires a new meaning if we take in
consideration what the Nobel laureate biologist Sydney Brenner
wrote in his book My Life in Science, London, Biomed Central
Limited, 2001.
Brenner was a close collaborator of Francis Crick, who, together
with James Watson, became Nobel laureates for their 1953
discovery of the double helix structure of DNA.
On the other hand, John von Neumann described a similar
mechanism in a paper published in 1951, in the Proceedings of the
Hixton Symposium on Cerebral Mechanism in Behaviour, held in
1948, in Pasadena, California.
Reading this paper, Brenner comments:
“You would say that Watson and Crick depended on von Neumann,
because von Neumann essentially tells you how it’s done. But of
course, no one knew anything about the other”.
On the other hand, Freeman Dyson noted that what today’s high
school students learn about DNA is what von Neumann discovered
purely by mathematics.
So Salomaa’s cognitive metaphor Watson-Crick Automata acquires
a deep meaning, as it is fully motivated by the historical
But, taking into account that what von Neumann described was just
a kind of automaton, we realize that the right name of Watson-Crick
Automata should be von Neumann- Watson-Crick Automata and it
is more than a metaphor, it is a historical restoration.
The Calculation-Observation
How History Repeats Itself
The whole story reminds another event, regarding the discovery of
the planet Neptune by pure mathematical calculations, made by
Urbain Le Verrier, who tried, in 1845, to explain the irregular orbit of
From these calculations, he deduced the existence of an unknown
planet, which was confirmed by observation, in 1846, by the
astronomer Johann G. Galle.
In our case, Von Neumann is Urbain Le Verrier, Johann G. Galle is
Watson-Crick while Arto Salomaa is the a posteriori Le Verrier.

Arto Salomaa_The Bourbaki of Formal Languages