Back

G-87-31

A Linear Algebra for Discrete Event Systems Moduloids and the Bases

BibTeX reference

In the analysis of discrete event systems, we need to consider sequences and/or matrices of elements in a given numerical set D (ℕ, Z, Q or ℝ according to the context) on which two composition laws are defined. The first law is written "∨" and stands for the Max or Min operator and, when − ∞ or + ∞ is added, defines a structure of monoïd on the set considered. The second law is usual addition and is written multiplicatively for notational convenience. This law defines a structure of monoïd on ℕ, Q+ or ℝ+ and of group on Z, Q or ℝ (with 0 as neutral and &#x00B1 ∞ as absorbing element); it is distributive over "∨" and (D, ∨, ⋅) is an Archimedian cancellative dioïd (or a pseudo-ring whenever D has inverses with respect to "⋅").

In order to compare two or more sequences or matrices defined on D, G. Cohen et al. [3] introduced the concept of moduloïd over D and raise the question whether there exists an intrinsic dimension for these objects.

In this paper we investigate two notions of dimension for moduloïds, one being weaker than the other. When D is a pseudo-ring the two notions coïncide. Then we prove:

Theorem 1
Every finitely generated moduloïd has a wek basis.

Theorem 2
Every finitely generated moduloït contains a maximal submoduloïd which has a basis.

Theorem 3
The basis (resp. the weak basis) of a moduloïd is essentially unique.

, 24 pages