The lattices of prefixes and overlaps of traces

DOI10.1016/0012-365X(95)00046-YzbMath0861.06006MaRDI QIDQ1815323

Yanyan Li

Publication date: 7 November 1996

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

distributive latticetrace monoidoverlap latticeoverlap of a traceprefix latticeprefix of a traceprefix ordersuffix of a trace

Mathematics Subject Classification ID

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

Related Items

Overlaps in free partially commutative monoids ⋮ Bounded query machines: on NP and PSPACE ⋮ Bounded query machines: on NP( ) and NPQUERY( ) ⋮ Complete sets and the polynomial-time hierarchy ⋮ On languages specified by relative acceptance

Cites Work

• On some equations in free partially commutative monoids
• Theory of traces
• Probabilistic estimation of the number of prefixes of a trace
• Combinatorics on traces
• Membership problems for regular and context-free trace languages
• Combinatorial problems of commutation and rearrangements
• Overlaps in free partially commutative monoids
• Efficient solution of some problems in free partially commutative monoids
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item