We show that the independence relation defining a trace monoid M admits a transitive orientation if and only if the characteristic series ξ of a lexicographic cross section of M is the inverse of the determinant of (Id-X), where X is a matrix representing the minimum finite automaton recognizing ξ and Id is the identity matrix. This implies that, if the independence relation of a trace monoid M admits a transitive orientation, then any unambiguous lifting of the Möbius function of M is the determinant of a matrix defined by the smallest acceptor of the corresponding cross section.

Determinants and Moebius functions in trace monoids / C. Choffrut, M. Goldwurm. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 194:1-3(1999), pp. 239-247.

Determinants and Moebius functions in trace monoids

M. Goldwurm
Ultimo
1999

Abstract

We show that the independence relation defining a trace monoid M admits a transitive orientation if and only if the characteristic series ξ of a lexicographic cross section of M is the inverse of the determinant of (Id-X), where X is a matrix representing the minimum finite automaton recognizing ξ and Id is the identity matrix. This implies that, if the independence relation of a trace monoid M admits a transitive orientation, then any unambiguous lifting of the Möbius function of M is the determinant of a matrix defined by the smallest acceptor of the corresponding cross section.
Settore INF/01 - Informatica
1999
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/190947
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact