Publication:5306172

zbMath1199.68164MaRDI QIDQ5306172

Luca Breveglieri, Emanuele Rodaro, C. Nuccio, A. Cherubini Spoletini

Publication date: 8 April 2010

zbMATH Keywords

NP-complete problem; free partially commutative monoid; trace equation

Mathematics Subject Classification ID

68R15: Combinatorics on words

20M05: Free semigroups, generators and relations, word problems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)