A counterexample to the triangle conjecture

DOI10.1016/0097-3165(85)90032-9MaRDI QIDQ762613zbMATH OpenOpenAlexWikidataFDO

Authors Peter W. Shor

Publication date 1985

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0097-3165(85)90032-9

zbMATH Keywords

cardinality of a codeprefix codetriangle conjecture

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Prefix, length-variable, comma-free codes (94A45)

Review text

It is known that the triangle conjecture sets a bound on the cardinality of a code formed by words of the form \(a^iba^j\). A counterexample exceeding this bound is presented in this paper. This also disproves a stronger conjecture that every code is commutatively equivalent to a prefix code.

Recommendations

• A note with computer exploration on the triangle conjecture
• Supplemented results of finite maximal codes related to the triangle conjecture proposed by D. Perrin and M. P. Schützenbeger
• Finite maximal codes and triangle conjecture
• scientific article; zbMATH DE number 1047958
• A counter example to a conjecture concerning synchronizing words in finite automata

Cites work

• A conjecture on sets of differences of integer pairs
• A note on the triangle conjecture
• Baionnettes et cardinaux
• scientific article; zbMATH DE number 3760085 (Why is no real title available?)
• On the triangle conjecture

Cited in

(19)

• Noncommutative factorization of variable-length codes
• Some combinatorial results on Bernoulli sets and codes
• Completions in measure of languages and related combinatorial problems
• Coding by minimal linear grammars
• A note with computer exploration on the triangle conjecture
• Completing codes and the Rédei property of groups
• scientific article; zbMATH DE number 3926268 (Why is no real title available?)
• Completing codes
• ON A PROPERTY OF THE FACTORIZING CODES
• Some decompositions of Bernoulli sets and codes
• On the factorization conjecture
• The second step in characterizing a three-word code
• On the Commutative Equivalence of Algebraic Formal Series and Languages
• Finite maximal codes and factorizations of cyclic groups
• An application of Hajós factorizations to variable-length codes
• On the commutative equivalence of algebraic structures and related problems
• Factorizations of cyclic groups and bayonet codes
• Bernoulli sets over ternary and multiletter alphabets: algebraic characterizations, polynomial divisibility, and commutative prefix properties
• Finite maximal codes and triangle conjecture

This page was built for publication: A counterexample to the triangle conjecture

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