The word problem for \(1\mathcal{LC}\) congruences is NP-hard.

DOI10.1016/S0304-3975(03)00283-4zbMath1059.68077MaRDI QIDQ1426452

Laurent Rosaz

Publication date: 14 March 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

NP-hardnessGeneralization of Mazurkiewicz traces

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Combinatorics on words (68R15)

Cites Work

• The poset of infinitary traces
• Un modèle asynchrone pour les systèmes distribués. (An asynchronous model of distributed systems)
• Semi-commutations
• Theory of traces
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• A trace semantics for Petri nets
• Combinatorial problems of commutation and rearrangements
• A generalization of traces
• Parties reconnaissables de monoïdes définis par générateurs et relations
• Recursive Unsolvability of a problem of Thue
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The word problem for \(1\mathcal{LC}\) congruences is NP-hard.