Alphabetical satisfiability problem for trace equations

MaRDI QIDQ5306172zbMATH OpenFDO

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

Publication date 8 April 2010

zbMATH Keywords

free partially commutative monoidNP-complete problemtrace equation

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Recommendations

• Solving word equations modulo partial commutations
• Solutions of word equations over partially commutative structures
• scientific article; zbMATH DE number 1834675
• Satisfiability of equations in free groups is in \(\mathsf{PSPACE}\)
• scientific article; zbMATH DE number 1754619

Cited in

(5)

• scientific article; zbMATH DE number 1114346 (Why is no real title available?)
• scientific article; zbMATH DE number 1490005 (Why is no real title available?)
• scientific article; zbMATH DE number 1754619 (Why is no real title available?)
• scientific article; zbMATH DE number 1759404 (Why is no real title available?)
• Solving trace equations using lexicographical normal forms

This page was built for publication: Alphabetical satisfiability problem for trace equations

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