The code problem for traces — improving the boundaries

✍ Scribed by Hendrik Jan Hoogeboom; Anca Muscholl

• Book ID: 104326221
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 958 KB
• Volume: 172
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00216-2

✦ Synopsis

The code problem for traces ~ given a finite set X, decide whether every element in X+ has a unique factorization over X -is decidable if the independence relation equals P4, the line graph on four nodes. Additionally, it is undecidable for a particular independence relation that does not have C4, the cycle on four nodes, as induced subgraph. These results improve on the previously known boundaries of (un)decidable cases for this problem.