left to right (the way of reading in european languages). Hence, assigning a letter to each temporal object, as its identity, and using as many occurrences of this identity as it has points or interval bounds, it is possible to describe an atomic temporal relation between n **objects on the timeline, as**
far as there is no simultaneity, with a word on an n-alphabet (alphabet with n letters). Simultaneity requires to be able to write several letters inside a same box**. This is the aim of the theory of**
S-languages.

In this paper, we show how the S-languages framework allows to represent n**-ary qualitative**
temporal relations and to reason without any transitive tables.

In the next part, we recall the basis of formal languages, following [3,13], and S-languages, and we examine the usual operations of the relational algebra [21] in the context of S-languages.

We then provide two examples of how to reason without transitivity tables. The first one is a revisitation of the well-known unsatisfiable closed network of Allen [2] . The second one revisits the Manna-Pnuelli's problem of the allocation of a resource between several requesters [24]. This aims to show how a problem of concurrency for complex systems, written in modal temporal logic can be solved with the S-languages framework.

## 2. Formal Languages

Let us first recall some basis on formal languages.

## 2.1. Basis

An alphabet X is a finite nonempty set of symbols called letters. A word (of length k ≥ **0) over**
an alphabet X is a finite sequence x1**, . . . , x**k of letters in X. A word x1, . . . , xk **is usually written** x1 . . . xk. The unique word having no letter, **i.e.** of length zero, called the empty **word, is denoted by**
ε. The length of a word f is denoted by |f|**. The**
number of occurrences of a letter a **in the word**
f is denoted by |f|a**. The set of all words (resp.**
of length n) on X is denoted by X∗**(resp.** Xn).

Let us remark that X∗ =Sn≥0 Xn**. The set of all**
words on X is written X∗. A subset of X∗**is called**
a language. The empty set ∅ **is the least language**
and X∗**is the greatest language for the order of**
inclusion.

Let u and v be words in X∗. If u = u1 . . . ur and v = v1 . . . vs are words, then u.v **(usually written**
uv), called the concatenation of u and v**, is the**
word u1 . . . urv1 . . . vs. For instance let X = {**x, y**},
u = xx and v = yy**, then the concatenation is**
uv = xxyy. Let us notice that uv 6= vu**. We also**
have to set u 0 = {ε} , u 1 = u, u n+1 = uun**. One**
has v.ε = ε.v = v.

The concatenation can be extended to languages on X by setting L.L′ = {uv|u ∈ **L, v** ∈ L
′}**. This**
operation endows 2X∗**with a structure of noncommutative monoid. We also have** L
0 = {ε} ,
L
1 = u, L
n+1 = LLn, L
∗ =Sn≥0L
n.

u
∗ =Sn≥0 u n**. Even if** u
∗**is a set, it can be**
worked with like an element, so that we will take this alternative and use u
∗ **as a word or S-word.**
The shuffle is a very useful operator which is used in concurrency applications. The shuffle operator describes all possibilities of doing two concurrent sequences of actions in a sequential manner. Therefore, this is not a binary combination of X∗ **because, from two words, it provides a set**
of words, that is a language. Its definition is the following: Let u and v **be two words written on**
an alphabet X∗. The shuffle of u and v **is the**
language u∨∨v = {α1β1 . . . αkβk ∈ X∗|α1, βk ∈
X∗, α2, . . . , αk, β1, . . . , βk−1 ∈ X+, u = α1 **. . . α**k, v = β1 . . . βk}. For instance let X = {x, y}**, then**
xx∨∨yy = {**xxyy, xyxy, yxxy, xyyx, yxyx, yyxx**}.

The concatenation uv **means an order between**
u and v, this is a word of the language u∨∨v**. One**
has ε∨∨v = v∨∨ε = v for any word v of X∗**. The**
shuffle can be naturally extended to languages on X **by setting** L∨∨L
′ =Su∈L,v∈L′ u∨∨v. The shuffle endows 2X∗**with a structure of commutative**
monoid.

Words are read from left to right, so that the reading induces a natural arrow of Time. Any occurrence of a letter can be viewed as an instant numbered by its position inside the word. Traces languages or paths expressions [8] are used for such a purpose: planning the order of execution of events. But with these languages, it is not possible to differentiate two occurrences that are concurrent (i.e. one may be before, **at the same time** or after **the other) from those that must occur at the**
same time**: these two events are said to commute.**
It is presupposed that the granularity of the time measurement is fine enough to avoid the case at the same time.