
<=<=
<=<=
<=
<=
<=<=
<=
<=
<= <=
<=
<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<=
<=
<=
<=
<=

<=

<=

<=
<=

<=

<=

<=
<=

<=

<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=
Universität Stuttgart

Fakultät Informatik

?

Institut für Informatik

Breitwiesenstraße 20-22

D-70565 Stuttgart

Some Identities Related

to Automata, Determinants,

and M?
obius Functions

Volker Diekert Yuji Kobayashi

Report Nr. 1997/05

15. Juni 1997



SOME IDENTITIES RELATED TO AUTOMATA,
DETERMINANTS, AND MÖBIUS FUNCTIONS

VOLKER DIEKERT1
Institut für Informatik, Universität Stuttgart
Breitwiesenstr. 20-22, D-70565 Stuttgart, Germany

YUJI KOBAYASHI
Toho University, Faculty of Science
Miyama 2-2-1, Funabashi 274, Japan

We define the Möbius function for a language S being closed under
factors as the formal inverse of the characteristic series over the set
S. We derive identities in commuting and non-commutating variables
characterizing this function as a quotient of polynomials which can
be expressed as certain determinants. These determinants in turn are
obtained by some matrix related to the minimal automaton recognizing S. 
Our contribution extends some recent work of Choffrut and
Goldwurm.

1 Introduction

Möbius functions play an important role in combinatorics. For monoids 
they were introduced by Cartier and Foata [3] leading to a 
generalization of MacMahon's Master Theorem. The spirit of this theorem 
is an expression of certain series as the formal inverse of some 
determinant. The work of Cartier and Foata led also to a systematic 
study of free partially commutative monoids. These monoids are of 
particular interest in computer science due to the possibility to model 
basic phenomena on concurrent processes [10, 7].
Recently Choffrut and Goldwurm have shown [4] that (an unambiguous 
lifting of) the Möbius function of a free partially commutative monoid 
can be expressed as the determinant of the minimal automaton recognizing 
the set of its lexicographic normal forms if and only if the 
independence relation has a transitive orientation. Taking a slightly 
different viewpoint this result is in fact a statement about languages 
defined by forbidden factors of length exactly two. The aim of this 
paper is a generalization to other classes of languages defined by 
forbidden factors. We define the Möbius function ?S for languages S = X? 
n X?FX? being closed under factors as the formal inverse of the 
characteristic series over S. The dream would be a general formula of 
the type

?S = Det(1 ?M)

1Acknowledgment: This work was done during a research visit by the first 
author to the Faculty of Science of Toho University, Japan. The 
hospitality and support of the university of Toho are gratefully 
acknowledged.

1


where M is a matrix related to the minimal automaton recognizing S. Such 
an identity fails in general, but we obtain a closely related identity. 
Informally, our main results can be stated as follows: (The precise 
meaning of the notations involved will be given below.)

Theorem Let F ? X? be a finite set of forbidden factors, 1 62 F , and 
let l = maxfjuj j u 2 Fg, l >= 2, the maximal length. Let S = X? n X?FX? 
and M be some n?n-matrix associated to the minimal finite automaton 
recognizing the language S. Then we find explicitly a polynomial D(S; l 
? 1) of degree at most n ? (l ? 1) ? maxf1; l ? 2g such that we have the 
following identity in commuting variables:
S ? Det(1 ?M) ?c D(S; l ? 1):

Moreover, we derive a graph theoretical criterion implying the following 
identity of formal power series:

S ? Det(1 ?M) = D(S; l ? 1):

Thus, the product
Det(1 ?M) ? D(S; l ? 1)?1

is an explicit description of the Möbius function of S, if the criterion 
is satisfied. It turns out that, if all forbidden factors are of the 
form ba for some letters a; b with a < b, then the polynomial D(S; l ?1) 
equals 1 and the criterion is satisfied. Since it is well-known that the 
set of lexicographic normal forms of a free partially commutative monoid 
has a description by forbidden factors of length two if and only if the 
independence relation is equipped with a transitive orientation, we 
obtain the setting of Choffrut and Goldwurm as a special case. The 
outline of the paper is as follows. In Sect. 2 we recall some well-known 
facts on formal power series, Möbius functions, and overlapping chains. 
Since our calculations involve determinants over a non-commutative ring 
(being perhaps not standard) we develop the necessary background in 
Sect. 3. The new results start with Sect. 4. In the final section we 
illustrate our method again by an example for some partial commutation 
over four letters.

2 Formal power series, M?
obius functions, and overlapping chains

Let X be a finite alphabet. The ring of formal power series ZhhXii is 
the set of mappings f : X? ?! Z where addition and multiplication are 
defined by:

(f + g)(w) = f(w) + g(w);

(f ? g)(w) =
X

uv=w
f(w) ? g(w):

2


It is easy to see that a power series f 2 ZhhX?ii has a formal inverse 
f?1 if and only if f(1) 2 f?1; +1g. A polynomial is a formal power 
series f with a finite support, i. e., the set fw 2 X? j f(w) 6= 0g is 
finite. The degree of a non-zero polynomial f is the maximal length of a 
word in the support, maxfjwj j f(w) 6= 0g.
By 1 we denote the empty word 1 2 X? and the unit element of ZhhXii (or 
any other ring). For ZhhXii the unit element is the characteristic 
series over f1g. The symbol 1 (written in boldface) is reserved to 
denote the (n ? n-)unit-matrix over some ring.
A subset S ? X? is frequently identified with its characteristic series, 
S = ?S, where:
?S(w) = 1 if w 2 S and ?S(w) = 0 otherwise:

By abuse of language, we say that two power series g; h 2 ZhhXii are 
equal in commuting variables, written as g ?c h, if g ? h is an element 
in the two-sided ideal generated by the series f ? a ? a ? f where a 2 X 
and f 2 ZhhXii. In particular, we have

f ? p ?c p ? f for all f; p 2 ZhhXii where p is a polynomial:

Definition 1 Let S be a non-empty language S ? X? being closed under 
factors, i.e., uvw 2 S implies v 2 S. The Möbius function ?S is defined 
to be the formal inverse of the characteristic series over S. Hence:

?S = (
X

w2S
w)?1 = S?1:

Remark 1 Let M be a quotient monoid of X? where the Möbius function ?M 
is defined in the sense of Cartier and Foata, see [3], and let S ? X? be 
a crosssection of M being closed under factors. (Such a set S ? X? 
always exists, e. g. take S to be the set of lexicographical normal 
forms.) Then ?S 2 ZhhXii is a lifting (or a representation ) of the 
Möbius function ?M.

Any non-empty language S ? X? being closed under factors can be defined 
by some set of forbidden factors F ? X? such that S = X? n X?FX?. Since 
S 6= ;, we have 1 62 F and we may assume that F is basis of the ideal 
X?FX?, i. e., X?FX? = X?F 0X? implies F ? F 0.

Definition 2 Let 1 2 S = X? n X?FX? and F be a basis of X?FX?. An 
overlapping chain is a sequence (w1; : : : ; wn) such that n >= 0, w1 2 
S \ X, wi 2 S, and wi?1wi 2 X?F n X?FX+ for 1 < i <= n.

The concept of overlapping chains appears in [1], see also [8, 9]. 
Independently it has been developed [6], too, where the following result 
is stated. A closely related result on Hilbert series can also be found 
in in [2, Thm. 5.1], where overlapping chains are called worms.

3


Proposition 2 ([6], Thm 4.4.2 ) Let C be the set of overlapping chains. 
Then we have
?s =
X

(w1;:::;wn)2C
(?1)nw1 ? ? ? wn:

Corollary 3 If the Möbius function ?S is a polynomial, then S is defined 
by some finite set F of forbidden factors. If F is finite, then ?S is a 
polynomial if and only if there is a maximal integer n where some (w1; : 
: : ; wn) 2 C exists.

Proof of Cor. 3: By [6, Lem. 4.4.1] two overlapping chains (w1; : : : ; 
wn) 2 C and (w0
1; : : : ; w0
n) 2 C are equal if and only if w1 ? ? ? wn = w0
1 ? ? ? w0
n denote the same
words. Hence, by Prop. 2 the power series ?S is a polynomial if and only 
if C is a finite set. The result follows since F n X is a subset of the 
support ?S and X is finite.

Example 1

i) Let F = fabbg, then we have

?S = 1 ?X + abb:

ii) Let F = fabag, then we have

C = f(1); (x); (a; ba); (a; ba; ba); : : : ; (a; ba; ba; : : : ; ba); : 
: : j x 2 Xg:

Hence

?S = 1 ?X ?
X

n>=1

(?1)na(ba)n

= 1 ?X n fag ? a(1 + ba)?1

= (1 ?X + (1 ?X n fag)ba)(1 + ba)?1:

Example 2 Let I ? X ?X be a symmetric (independence) relation and let ?I 
be the congruence generated by ab ?I ba for (a; b) 2 I. Let < be a total 
order of X and I+ = (I\ >). For w 2 X? let lex([w]) denote the 
lexicographically first element in the congruence class of w and let Lex 
be the set of lexicographical normal forms: Lex = flex([w]) j w 2 X?g.

i) Let I+ be transitive. Then Lex = X? n X?FX? where F is the finite set 
of forbidden factors F = fba j (b; a) 2 I+g. In this case:

?Lex =
X

(a1;:::;an)2C
(?1)na1 ? ? ? an:

Clearly, (a1; : : : ; an) 2 C if and only if a1 > ? ? ? > an and (ai; 
aj) 2 I for all i 6= j, 1 <= i; j <= n (since I+ is transitive).

In the terminology of [5] the function ?Lex is therefore an unambiguous 
lifting of the Möbius function of X?= ?I.

4


ii) If I+ is not transitive, then there are letters a; b; c 2 X such 
that (c; b) 2 I+, (b; a) 2 I+, but (c; a) 62 I+. Hence canb 62 Lex, 
since lex([canb]) = bcan. Every proper factor of the word canb belongs 
to Lex. Therefore we have fcanb j n >= 0g ? F and F must be infinite. As 
a consequence, ?Lex is no polynomial by Cor. 3.

3 Determinants over non-commutative rings

Let R be a ring with 1 being not necessarily commutative. There is no 
unique definition for the determinant of an n ? n matrix over a 
non-commutative ring. For our calculations the following definition is 
convenient:

Definition 3 Let A = (aij) be an n ? n matrix with coefficients in R, 
aij 2 R for 1 <= i; j <= n. Define the determinant of A by:

Det(A) =
X

ö
(?1)öaö(1);1 ? ? ? aö(n);n;

where the sum is taken over all permutations of f1; : : : ; ng and (?1)ö 
denotes the sign of the permutation ö.
The trace of the matrix A is defined as usual by the sum over the 
diagonal elements:

Trace(A) =
n
X

i=1
ai;i:

Remark 4 Taking the determinant of the transposed matrix we find the 
definition of a determinant as e.g. in [3, page 54].

Calculations with determinants over a non-commutative ring need some 
care. For example consider a matrix where two columns are equal. We 
have:

Det
a a
b b

!

= ab ? ba

which is not zero, unless ab = ba.
Moreover, determinants are not multiplicative, in general:

Det

  
a 0
0 b

!
c 0
0 d

!!

= acbd;

Det
a 0
0 b

!

Det
c 0
0 d

!

= abcd:

Nevertheless there are some general rules being used in the following.

5


Rule 1 The determinant is zero, if a row or a column is zero or if two 
rows are equal.

Proof: Clearly, if a row or a column is zero, then the determinant is 
zero. Let A be a matrix where the i-th and j-th row are equal, i 6= j. 
Let ? be the transposition with ?(i) = j. Then ö 7?! ? ffiö defines an 
involution without fixed points and we have

(?1)öaö(1);1 ? ? ? aö(n);n = ?(?1)?ffiöa?ffiö(1);1 ? ? ? a?ffiö(n);n

for all permutations ö. The result follows.

Rule 2 The determinant does not change its value if we add or subtract 
some row from another one.

Proof: The classical proof applies due to Rule 1.

For the rest of this section we fix the following notations: A denotes 
any n ? n matrix over R, n >= 2.
B and C denote matrices where all rows are equal: B = (bij) and bij = bj 
for some vector (b1; : : : ; bn) 2 Rn, C = (cij) and cij = cj for some 
vector (c1; : : : ; cn) 2 Rn. T denotes a matrix which is strictly upper 
triangular, T = (tij) and i >= j implies tij = 0.
D denotes a diagonal matrix where the diagonal elements are central in 
R. This means D = (dij), dij = 0 for i 6= j, dii = di for some vector 
(d1; : : : ; dn) 2 Rn such that dir = rdi for all r 2 R, i 2 f1; : : : ; 
ng.
Finally, 1 denotes the n ? n-unit-matrix, i. e., 1 is a diagonal matrix 
as above where di = 1 for 1 <= i <= n.
For a matrix A and J ? f1; : : : ; ng let AJ be the matrix obtained from 
A where all rows and columns from the index set J are canceled. We adopt 
the convention that Det(AJ) = 1 for J = f1; : : : ; ng.

Rule 3 We have

Det(D + A) =
X

J?f1;:::;ng

0

@
Y

j2J
dj

1

A Det
?
AJ
?
:

Proof: The classical proof applies since all di are central, 1 <= i <= 
n.

Combining Rules 1 and 3 together with the observation that Det(BJ) = 0 
for jJ j <= n ? 2, we obtain:

Rule 4 We have

Det(1 +B) = 1 + Trace(B) = 1 +
n
X

j=1
bj:

6


Rule 5 We have
Det(B ? T ) = b1t1;2 ? ? ? tn?1;n:

Proof: This follows by induction on n since by Rule 1 we have:

Det(B ? T ) = Det

0

B
B
B
B
@

b1 ? ? ? bn?1 ? t1;n?1 bn ? t1;n
...
. . .
...
...

b1 ? ? ? bn?1 bn ? tn?1;n
b1 ? ? ? bn?1 bn

1

C
C
C
C
A

= Det

0

B
B
B
B
@

b1 ? ? ? bn?1 ? t1;n?1 bn ? t1;n
...
. . .
...
...

b1 ? ? ? bn?1 bn ? tn?1;n
0 ? ? ? 0 tn?1;n

1

C
C
C
C
A

= Det

0

B
B
@

b1 ? ? ? bn?1 ? t1;n?1
...
. . .
...

b1 ? ? ? bn?1

1

C
C
A ? tn?1;n:

By Rules 3 and 5 we obtain:

Rule 6 We have

Det(D +B ? T ) =
X

i1<:::<ik
J=f1;:::;ngnfi1;:::;ikg

0

@
Y

j2J
dj

1

A bi1 ti1i2 ? ? ? tik?1ik :

Rule 7 We have

Det(1 +B ? T ) =
X

i1<:::<ik
bi1ti1i2 ? ? ? tik?1ik :

Recall that determinants are not multiplicative, in general. Thus, for 
the following rule we need a proof.

Rule 8 We have

Det((1 +B)(1 + C ? T )) = Det(1 +B) Det(1 + C ? T ):

Proof: Clearly:

(1 +B)(1 + C ? T ) = 1 + (B +BC ? BT + C) ? T

and B +BC ? BT + C is a matrix where all rows are equal. More precisely

(B +BC ?BT + C)ij = bj +
X

l
blcj ?
X

l<j
bltlj + cj =: ej:

7


By Rule 7 we obtain

Det((1 +B)(1 + C ? T )) = 1 +
X

i1<:::<ik
k>=1

ei1ti1i2 ? ? ? tik?1ik :

On the other hand we have:

Det(1 +B) = 1 +
X

l
bl;

Det(1 + C ? T ) = 1 +
X

i1<:::<ik
k>=1

ci1ti1i2 ? ? ? tik?1ik :

The assertion follows by some easy calculation showing that:

1 +
X

i1<:::<ik
k>=1

ei1ti1i2 ? ? ? tik?1ik = (1 +
X

l
bl)(1 +
X

i1<:::<ik
k>=1

ci1ti1i2 ? ? ? tik?1ik):

Remark 5 Let R = ZhhXii and A1; A2 be matrices with coefficients in 
ZhhXii where, in addition, the coefficients of A2 (or of A1) are 
polynomials. Then we always have an identity in commuting variables:

Det(A1 ? A2) ?c Det(A1) ? Det(A2):

4 Finite sets of forbidden factors

Let S ? X? denote a non-empty set being closed under factors, S = X? 
nX?FX? and F is a basis of the ideal X?FX?. From now on we shall assume 
that F is finite. In particular S is a regular language being local. By 
l we denote the maximal length of a forbidden factor:

l = maxfjf j j f 2 Fg:

In order to avoid trivial special cases we shall assume l >= 2 
throughout. For 0 <= p <= q let X [p;q] denote the set

X [p;q] = fw 2 X? j p <= jwj <= qg:

For u 2 X? we denote S(u) = fw 2 X? j uw 2 Sg. Then the minimal finite 
deterministic automaton is given by the state space Q0 = fS(u) j u 2 X?; 
S(u) 6= ;g. All states are final, the initial state is S(1), and for u; 
v 2 X?, a 2 X there exists a transition
S(u) a
?! S(v)

if and only if S(ua) = S(v) 6= ;.

8


[bb]
?>=

?<=
[ba]
?>=

?<=
[ab]
?>=

?<= Ä

b

ö
a

Ä

a

Y
b

j
a

Figure 1: The automaton recognizing fa; bg? n fa; bg?abbfa; bg?

For a word u 2 S \ X l?1 define

[u] = fv 2 X l?1 j S(u) = S(v)g:

Let Q = f[u] j u 2 S \ X l?1g then we have Q 6= ; and we may view Q ? Q0 
by the natural mapping [u] 7?! S(u). Note that for [u] 2 Q and a 
transition S(u) a
?! S(v) we may take v 2 S \ X l?1 such that ua 2 Xv. In particular, [v] 
2 Q and we may write [u] a
?! [v]. In the following we are concerned with the
sub-automaton only which is given by the set Q.

Remark 6 Let n = jQj and n0 = jQ0j. Then we have n <= n0, and the 
equality n = n0 is equivalent to the existence of some letter a 2 X such 
that F \aX? = ;. Indeed, if F \aX? = ;, then S(1) = S(al?1). Hence Q = 
Q0 in this case. For the converse let u 2 S \ X l?1, u = u0a for some a 
2 X. Let aw 2 F . Then w 2 S, hence w 2 S(1), but w 62 S(u). Hence [u] 
6= [1].

Example 3

i) Let S = Lex as in Ex. 2, i) ( I+ being transitive). Then n = n0 since 
the first letter w. r. t. < is never a prefix of a forbidden factor.

ii) For F = X l, we have n = 1 and n0 = l.

iii) For F = fabbg we have n = n0 = 3, and the automaton is given by 
Fig. 1.

iv) For F = fabag we have again n = n0 = 3, and the automaton is given 
by almost the same picture, see Fig. 2.

In the following we use a matrix representation for the sub-automaton 
generated by the set Q. Consider the following Q?Q-matrix M where the 
coefficients are subsets of X viewed as element of ZhhXii. The 
coefficient M ([u]; [v]), [u]; [v] 2 Q, is written as M [u; v], and 
defined as follows:

M [u; v] = fa 2 X j [ua] = [v]g:

9


[bb]
?>=

?<=
[ba]
?>=

?<=
[ab]
?>=

?<= Ä

b

ö a
Ä

a

ö b
*

b

Figure 2: The automaton recognizing fa; bg? n fa; bg?abafa; bg?

The symbol A is reserved to denote the following Q ? Q-matrix where all 
rows are equal:
A[u; v] := [v]:

Example 4 In both cases: F = fabbg (Fig. 1) and F = fabag (Fig. 2), we 
have:

[ab] 6= [aa] = [ba] 6= [bb] 6= [ab]:

Therefore Q = f[ab]; [ba]; [bb]g and for the representation as 3 ? 
3-matrix we may choose the ordering such that [ab] < [ba] < [bb]. Hence:

A =

0

B
@
ab aa + ba bb
ab aa + ba bb
ab aa + ba bb

1

C
A :

For F = fabbg we obtain:

M =

0

B
@
0 a 0
b a 0
0 a b

1

C
A :

For F = fabag we have:

M =

0

B
@
0 0 b
b a 0
0 a b

1

C
A :

The next lemma is an immediate consequence of the definitions above:

Lemma 7 Let the matrices M and A be defined as above:

M [u; v] = fa 2 X j [ua] = [v]g; A[u; v] = [v]:

Let k >= 0 and [u]; [v] 2 Q, then we have:

(AMk)[u; v] = fw 2 X(k+l?1) j w 2 (S \ X?[v])g

(A
X

k>=0
Mk)[u; v] = fw 2 X? j jwj >= l ? 1; w 2 (S \ X?[v])g:

10


Proposition 8 We have

Det(1 + A
X

k>=0
Mk) = S ? (S \ X[1;l?2]):

Proof: By Lem. 7 all rows of the matrix A
P
k>=0 Mk are equal, hence by Sect. 3,
Rule 4 we obtain:

Det(1 + A
X

k>=0
Mk) = 1 + Trace(A
X

k>=0
Mk)

= 1 +
X

[v]2Q
fw 2 X? j jwj >= l ? 1; w 2 (S \ X?[v])g:

Moreover, for jwj >= l ? 1 with w = w0v0 where jv0j = l ? 1 we have that 
w 2 (S \ X?[v]) implies [v] = [v0]. Hence the sum above is a partition 
of the set of words fw 2 S j jwj >= l ? 1g. The proposition follows.

Lemma 9 Let p >= 1. We have the following matrix identity:

(1 + A
X

k>=0
Mk)(1 ?Mp) = (1 + A(
p?1
X

k=0
Mk) ?Mp):

Remark 10 Since the coefficients of the matrix (1 ? Mp) are polynomials 
we obtain by Rem. 5 an identity in commuting variables:

Det(1 + A
X

k>=0
Mk) ? Det(1 ?Mp) ?c Det(1 + A(
p?1
X

k=0
Mk) ?Mp):

Definition 4 Let p >= 1. The p-th denominator polynomial of S is defined 
by

D(S; p) = Det(1 + A(
p?1
X

k=0
Mk) ?Mp) + (S \ X[1;l?2]) ? Det(1 ?Mp):

Theorem 11 Let p >= 1. We have the following identity in commuting 
variables:

i)
S ? Det(1 ?Mp) ?c D(S; p):

ii) Moreover, if

Det((1 + A
X

k>=0
Mk)(1 ?Mp)) = Det(1 + A
X

k>=0
Mk) ? Det(1 ?Mp);

then we have the following identity of formal power series:

S ? Det(1 ?Mp) = D(S; p):

11


Proof: This is a direct consequence of Prop. 8 and Lem. 9.

The polynomial D(S; p) looks complicated. However, we are mainly 
interested in the case p = l ? 1. Let us rewrite

R = A ?M l?1;

B = A ?
l?2
X

k=1
Mk:

Then we have for [u]; [v] 2 Q rather simple expressions

R[u; v] = fw 2 [v] j uw 62 Sg;

B[u; v] = fyw 2 S j 1 <= jyj <= l ? 2; w 2 [v]g:

Recall also that we have A[u; v] = [v]. Using these notations we have 
the interpretation:

D(S; l ? 1) = Det(1 +R +B) + (S \ X[1;l?2]) Det(1 ? A +R):

It makes sense to express the polynomial D(S; l ? 1) in this form since 
A and B are matrices where all rows are equal. Note that the degree of 
this polynomial is at most n ? (l ? 1) ? maxf1; l ? 2g: Moreover, for l 
= 2 the matrix B is zero yielding a drastic simplification:

D(S; 1) = Det(1 +R):

The degree is then at most n.

Example 5 i) Let F = X l, then M is the zero matrix. Hence

Det(1 + A) = 1 + Trace(A) = 1 +
X

juj=l?1
u

and therefore

D(S; p) = (
X

juj=l?1
u) + (S \ X[1;l?2]) = X[0;l?1]:

The identity above reduces to the trivial statement

S = X[0;l?1]:

ii) For F = fabbg we have:

D(S; 2) = 1 + a + b ? abb:

12


iii) For F = fabag we have:

D(S; 2) = (a + b)(1 + ab)(1 ? aa ? bb ? babb)

+(1 + ab)[(1 + ba)(1 + (a + b)bb) + (aa + ba + bb)a]

?c (1 + ab)(1 + a + b + ab + abb):

Corollary 12 Let l = 2 and F = F1 [ F2 where F1 ? X and ; 6= F2 ? XX. 
Assume that there is a total order < on X nF1 such that ba 2 F2; a; b 2 
X implies a < b. Then we have D(S; 1) = 1 and hence the Möbius function 
?S = S?1 is a polynomial of degree n <= jX n F1j given by following 
determinant:

?S = Det(1 ?M):

Proof: The matrix M is a Q ? Q matrix where Q = f[a] j a 2 X n F1g, [a] 
= fb 2 X n F1 j 8c 2 X : ac 2 F2 () bc 2 F2g, and n = jQj. Write Q = 
f[a1]; : : : ; [an]g for some a1; : : : ; an 2 X n F1 such that an < ? ? 
? < a1 and ai <= b for all b 2 [ai], 1 <= i <= n. We view M as an n ? n 
matrix with M [i; j] = M [ai; aj] for 1 <= i; j <= n. We claim that the 
matrix R is now strictly upper triangular. Indeed, let R[i; j] 6= ;. 
Then there are bibj 2 F2 with bi 2 [ai], bj 2 [aj]. Hence aibj 2 F2 
which implies aj <= bj < ai. Therefore i < j. Since R is strictly upper 
triangular we have D(S; 1) = D(1 + R) = 1. Moreover, Det((1 
+A+AM)(1?A+R)) = Det(1 +A+AM) ? Det(1 ?A+R) by Sect. 3, Rule 8. Hence 
ii) of the theorem above yields

S ? Det(1 ?M) = 1:

By definition of the Möbius function this shows the claim of the 
corollary

?S = Det(1 ?M):

In particular, Thm. 11 yields:

Corollary 13 ([4], Thm. 1) Let < be a linear order of some finite 
alphabet X, let I ? X ? X be a symmetric (independence) relation, and 
let ?I be the congruence generated by ab ?I ba for (a; b) 2 I. Moreover, 
let Lex ? X? be the set of lexicographically first elements in each 
congruence class and let M be the matrix (where coefficients are subsets 
of X) associated to the minimal deterministic finite automaton 
recognizing Lex. Then the determinant

Det(1 ?M)

is the formal inverse over the characteristic series over the regular 
set Lex if and only if the relation I+ = (I\ <) is transitive.

Proof: If I+ is transitive, then Lex is defined by the finite set F = 
fba j (a; b) 2 I+g, hence one direction by Cor. 12. For the other 
direction we observe that if I+ is not transitive, then Lex?1 is no 
polynomial, see Ex. 2 ii).

13


5 Combinatorial interpretation

In this section we give a graph theoretical criterion when the matrix R 
becomes upper triangular. This yields a combinatorial interpretation in 
some cases. Recall that M l?1[u; v] is a subset of [v] for all u; v 2 S 
\ X l?1 and that [v] ? S \ X l?1 . More precisely we have:

M l?1[u; v] = fw 2 [v] j uw 2 Sg:

Let us define two directed graphs associated with S. The vertex set of 
the graph b
G(S) is defined by b
Q = S \ X l?1. Its edge set is given by:

f(u; v) 2 b
Q? b
Q j uv 62 Sg:

The graph G(S) is defined as the quotient graph of b
G(S) with vertex set Q.
Hence its edge set is:

f([u]; [v]) 2 Q?Q j 9w 2 [v] : uw 62 Sg:

A directed graph is acyclic if and only if there are no infinite paths. 
It is said to be acyclic up to self-loops, if every infinite path 
eventually becomes stationary in a loop around a single vertex.

Lemma 14

i) The graph G(S) is acyclic if and only if b
G(S) is acyclic.

ii) If b
G(S) is acyclic up to self-loops, then G(S) shares the same property.

Proof: Since G(S) is a quotient graph of b
G(S), it is clear that if G(S) is acyclic,
then b
G(S) is acyclic. Hence, in order to show i) and ii) we may assume that 
G(S) has an infinite path:

[v1] ?! [v2] ?! ? ? ? ?! [vi] ?! [vi+1] ?! ? ? ? :

By definition there are words u0
i; ui 2 [vi] for all 1 <= i such that u0
i?1ui 62 S for
all 1 < i. However, since S(u0
i) = S(ui) we see that ui?1ui 62 S for 1 < i, too. We
obtain an infinite path of b
G(S):

u1 ?! u2 ?! ? ? ? ?! ui ?! ui+1 ?! ? ? ? :

Therefore i): graph G(S) is acyclic if and only if b
G(S) is acyclic.
Moreover, if b
G(S) is acyclic up to self-loops, then for some i and all j with i <= j 
we have ui = uj. This implies [vi] = [vj] for all i <= j, and G(S) is 
acyclic up to self-loops, too. This proves ii).

14


ab
?>=

?<=
aa
?>=

?<=

ba
?>=

?<=
bb
?>=

?<=
?

ZZZZZZZ

~ ?
-

Figure 3: The graph b
G(S) for F = fabbg.

ab
?>=

?<=
aa
?>=

?<=

bb
?>=

?<=

ba
?>=

?<=

Ä
-

?

k

Figure 4: The graph b
G(S) for F = fabag.

Example 6 Let F ? XX and let X be linearly ordered such that ba 2 F 
implies a < b. Then b
Q = X and b
G(S) and hence G(S) are acyclic.

Remark 15 Let F ? X l be overlap free (i. e. uv; vw 2 F implies v = 1), 
then G(S) is acyclic.

Proof: Assume by contradiction that b
G(S) has a cycle then by Lem. 14 there
exists a path (u1; u2; : : : ; um) in b
G(S) for arbitrary large m. Since F is overlap
free, the word u1u2 ? ? ? um contains a subword of length (m ? 1)l. 
However the length of u1u2 ? ? ? um is m(l ? 1) yielding a contradiction 
for m > l.

Example 7

i) Let F = fabbg, then G(S) is acyclic. The graph b
G(S) is given in Fig. 3.

ii) Let F = fabag, then both, b
G(S) and G(S), are acyclic up to self-loops.
They are depicted in Figs. 4 and 5

iii) Let F = X l. Then b
G(S) is the complete graph with jXjl?1 vertices whereas
G(S) is a one point graph being trivially acyclic up to self-loops. In 
particular, the converse of Lem. 14, ii) is false, in general.

15


[ab]
?>=

?<=

[bb]
?>=

?<=
[ba]
?>=

?<=

Ä

HHHHHH

j Ä

Figure 5: The graph G(S) for F = fabag.

5.1 The acyclic case: The main result

In Corollary 19 below we shall give a combinatorial interpretation for 
the identity of Thm. 11, ii) in the case that the graph G(S) is acyclic. 
Recall that we have

M l?1 = A ?R;

where A[u; v] = [v] and R[u; v] = fw 2 [v] j uw 62 Sg. If G(S) is 
acyclic, then we choose an ordering of Q such that the matrix R is 
strictly upper triangular.

Proposition 16 Let G(S) be acyclic. Then we have:

Det(1 ?M l?1)

=
n
X

k=0
(?1)kfu1 ? ? ? uk j u1; : : : ; uk 2 S \ X l?1; ui?1ui 62 S for 1 < i <= 
kg:

Proof: Write 1 ?M l?1 = 1 ? A + A ?M l?1 = 1 ? A +R and apply Rule 7.

Remark 17 The determinant is therefore the alternating sum over the 
(finitely many) paths of the graph b
G(S).

Example 8 Let F ? X3 and let F be overlap free. Then we have

Det(1 ?M2) = 1 ?X2 +XF + FX ? F 2:

Theorem 18 Let G(S) be acyclic, then D(S; l ? 1) is a polynomial of 
degree at most n(l ? 1)(l ? 2) and we have the following explicit 
formula

D(S; l ? 1) = 1 +
n
X

k>=0
(?1)kfu0 ? ? ? uk j u0; : : : ; uk 2 S; 1 <= ju0j <= l ? 2;

juij = l ? 1; ui?1ui 62 S for 1 <= i <= kg:

16


Proof: By definition we have

D(S; l ? 1) = Det(1 +B +R) + (S \ X[1;l?2]) Det(1 ?M l?1):

Since R is strictly upper triangular we obtain by Sect. 3, Rule 7

Det(1 +B +R)

= 1 +
X

i1<???<ik
k>=1

(?1)k?1bi1ti1;i2 ? ? ? tik?1;ik

= 1 +
X

k>=1
(?1)k?1f(u0u1)u2 ? ? ? uk j 1 <= ju0j <= l ? 2; u0u1 2 S;

ui 2 S \ X l?1 for 1 <= i <= k; ui?1ui 62 S for 1 < i <= kg:

On the other hand, Prop. 16 yields:

(S \ X[1;l?2]) Det(1 ?M l?1)

=
X

k>=0
(?1)kfu0u1 ? ? ? uk j 1 <= ju0j <= l ? 2;

u0 2 S; ui 2 S \ X l?1; ui?1ui 62 S for 1 < i <= kg:

Note that both sums are finite, it is enough to sum up to k = n. 
Combining these sums we obtain:

D(S; l ? 1) = (S \ X[0;l?2]) +
X

k>=1
(?1)kfu0u1 ? ? ? uk j 1 <= ju0j <= l ? 2;

u0; u1; : : : ; uk 2 S; juij = l ? 1; ui?1ui 62 S for 1 <= i <= kg

= 1 +
X

k>=0
(?1)kfu0 ? ? ? uk j u0; : : : ; uk 2 S; 1 <= ju0j <= l ? 2;

juij = l ? 1; ui?1ui 62 S for 1 <= i <= kg:

Example 9 Let F ? X3 and let F be overlap free. Then we have:

D(S; 2) = 1 +X ? F:

Corollary 19 Let G(S) be acyclic. Then we have the following identity of 
formal power series:

S ? (
X

k>=0
(?1)kfu1 ? ? ? uk j u1; ui 2 S \ X l?1; ui?1ui 62 S for 1 < i <= kg)

= 1 +
X

k>=0
(?1)kfu0 ? ? ? uk j u0; : : : ; uk 2 S; 1 <= ju0j <= l ? 2;

juij = l ? 1; ui?1ui 62 S for 1 <= i <= kg:

17


Example 10 Let F ? X3 and let F be overlap free. Then the identity above 
becomes
S ? (1 ?X2 +XF + FX ? F 2) = 1 +X ? F:

Hence
?S = 1 ?X + F:

In particular, for F = fabbg we reobtain

?S = 1 ? a ? b + abb:

5.2 The case where the graph is acyclic up to self-loops

In this subsection we briefly consider the case where G(S) is acyclic up 
to selfloops. We derive identities in commuting variables, but the 
formulae have a rather complicated structure. First choose an ordering 
of Q such that the matrix R is upper triangular. Define

T [u; v] = fw 2 [v] j uw 62 S and [u] 6= [v]g:

Let D be the diagonal matrix with

D[v; v] = fw 2 [v] j ww 62 Sg:

Then R = D + T , and T is strictly upper triangular. For index sets J = 
fj1; : : : ; jmg, K = fi1; : : : ; ikg ? f1; : : : ; ng with j1 < ? ? ? 
< jm and i1 < ? ? ? < ik we denote the following finite subsets of X? :

?J = fw1 ? ? ? wm j wrwr 62 S; wr 2 [vjr ]; 1 <= r <= mg

UK = fu1 ? ? ? uk j ur 2 [vir ]; 1 <= r <= k; ur?1ur 62 S; 1 < r <= kg:

Analogously to the formulae above we obtain the following identity in 
commuting variables by Thm. 11 and Rule 6:

Corollary 20 Let G(S) be acyclic up to self-loops. Then we have:

S ?
X

J\K=;
(?1)jKj?J ? UK

?c
X

J\K=;
K=fi1;:::;ikg
i1<???<ik

(?1)k?J ? fu0u1 ? ? ? uk j 0 <= ju0j <= l ? 2;

u0 2 S; ur 2 [vir ]; ur?1ur 62 S; 1 <= r <= kg:

18


1
?>=

?<=
2
?>=

?<=
3
?>=

?<=
Ä

d

Y c
j
a
Ä

c

j
d Ä

a; b

Y d
k

c

Figure 6: The automaton recognizing Lex = X? n X?fca; cb; dbgX? with X = 
fa; b; c; dg.

6 Partial commutation revisited

In this final section we consider a simple example as an illustration 
how our method behaves in the case of partial commutation.
Let X = fa; b; c; dg, a < b < c < d, and I be given by the following 
graph:

a | c | b | d:

Then I+ = (I\ >) = f(c; a); (c; b); (d; b)g is a transitive relation and 
the set Lex of lexicographical normal forms is given by the set F = fca; 
cb; dbg of forbidden factors, Lex = X? n X?FX?.
The minimal automaton recognizing Lex has three states and is depicted 
in Fig. 6. State 1 is initial, all states are final. The associated 
matrix M = (Mi;j) is defined such that Mi;j denotes the sets of letters 
joining states i and j. Hence, we have:

M =

0

B
@
d c a
d c 0
d c a + b

1

C
A :

Denote by A the following matrix where all rows are equal:

A =

0

B
@
d c a + b
d c a + b
d c a + b

1

C
A :

Then A ?
P
k>=0 Mk is a matrix over formal power series where all rows are equal. 
Let (L1; L2; L3) be any row of the matrix A ?
P
k>=0 Mk. Then it holds:

L1 = fud 2 Lex j u 2 X?g

L2 = fuc 2 Lex j u 2 X?g

L3 = fux 2 Lex j u 2 X?; x 2 fa; bgg:

19


Hence Lex = 1 +L1 +L2 +L3 = 1 +Trace(A ?
P
k>=0 Mk): Some direct calculation
(or Rule 4) shows:

Det(A ?
X

k>=0
Mk) = Det

0

B
@
1 + L1 L2 L3
L1 1 + L2 L3
L1 L2 1 + L3

1

C
A = 1 + L1 + L2 + L3 = Lex :

On the other hand:

(1 + A ?
X

k>=0
Mk)(1 ?M) = (1 + A ?M):

Now, A ?M is a strictly upper triangular matrix:

A ?M =

0

B
@
0 0 a
0 0 a + b
0 0 0

1

C
A :

Hence Det(1 + A ? M) = 1. (This fact does not depend on the choice of 
the order of X. This determinant is 1 whether or not I+ is transitive!). 
By Rule 8 we obtain the identity on formal power series

Lex ? Det(1 ?M) = 1:

Hence Det(1 ?M) is the formal inverse of Lex. Explicitly we have:

Det(1 ?M) = Det

0

B
@
1 ? d ?c ?a
?d 1 ? c 0
?d ?c 1 ? a ? b

1

C
A

= 1 ? a ? b ? c ? d + ca + cb + db:

This polynomial is indeed the unambiguous lifting of the Möbius function 
Lex?1.

20


References

[1] David J. Anick. On the homology of associative algebras. 
Transactions of the American Math. Soc., 296:641{659, 1986.

[2] Winfried Bruns, Jürgen Herzog, and Udo Vetter. Syzygies and walks. 
In Aron Simis, editor, Commutative Algebra, pages 36{48. World 
Scientific, 1994. Proceedings of ITCP, Trieste 1992 (Italy).

[3] Pierre Cartier and Dominique Foata. Probl?emes combinatoires de 
commutation et r?earrangements. Number 85 in Lecture Notes in 
Mathematics. Springer, Berlin-Heidelberg-New York, 1969.

[4] Christian Choffrut and Massimiliano Goldwurm. Determinants and 
Möbius functions in trace monoids. Submitted for publication, 1996.

[5] Volker Diekert. Transitive orientations, Möbius functions and 
complete semi- Thue systems for free partially commutative monoids. In 
T. Lepistö et al., editors, Proceedings of the 15th International 
Colloquium on Automata, Languages and Programming (ICALP'88), Tampere 
(Finland) 1988, number 317 in Lecture Notes in Computer Science, pages 
176{187, Berlin-Heidelberg- New York, 1988. Springer.

[6] Volker Diekert. Combinatorics on Traces. Number 454 in Lecture Notes 
in Computer Science. Springer, Berlin-Heidelberg-New York, 1990.

[7] Volker Diekert and Grzegorz Rozenberg, editors. The Book of Traces. 
World Scientific, Singapore, 1995.

[8] Yuji Kobayashi. Complete rewriting systems and homology of monoid 
algebras. Journal of Pure and Applied Algebra, 65:263{275, 1990.

[9] Yuji Kobayashi. Partial commutation, homology and the Möbius 
inversion formula. In M. Ito, editor, Words, Languages and Combinatorics 
(Kyoto, Japan 1990), pages 288{298. World Scientific, Singapore, 1992.

[10] Antoni Mazurkiewicz. Concurrent program schemes and their 
interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977.

21