The lattices of prefixes and overlaps of traces

DOI10.1016/0012-365X(95)00046-YMaRDI QIDQ1815323zbMATH OpenFDO

Publication date 7 November 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00046-Y

distributive lattice overlap lattice overlap of a trace prefix lattice prefix of a trace prefix order suffix of a trace trace monoid

Mathematics Subject Classification ID

Structure and representation theory of distributive lattices (06D05) Semigroups in automata theory, linguistics, etc. (20M35) Combinatorics on words (68R15)

Review text

Traces are considered. A partially commutative alphabet is a pair \((A,I)\), where \(A\) is a finite alphabet and \(I\subseteq A\times A\) is a symmetric and irreflexive binary relation on \(A\), called the independence relation. By \(A^*\) the free monoid over \(A\) is denoted. The symbol \(\equiv\) denotes the congruence on \(A^*\) generated by the set of pairs \(\{(ab,ba)\mid (a,b)\in I\}\), and the quotient monoid \(M(A,I)=A^*/\equiv\) is called the trace monoid. Its elements are called traces. A prefix of a trace is a left factor in the trace monoid and a suffix is a right factor. The prefixes form a lattice with respect to a certain order called prefix order. If a prefix of a trace is also a suffix, it is called an overlap of this trace; the overlaps also form a lattice. The lattices of prefixes and of overlaps are studied. Among the results, it is proved that every finite distributive lattice is isomorphic to the prefix lattice of some trace, and a necessary and sufficient condition for a lattice to be isomorphic to the overlap lattice of a trace is stated.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: The lattices of prefixes and overlaps of traces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1815323)