A Construction of Short Sequences Containing All Permutations of a Set as Subsequences

  • Sasa Radomirovic
Keywords: Combinatorics on Words, Shortest Sequences, Permutations

Abstract

A sequence over a fixed finite set is said to be complete if it contains all permutations of the set as subsequences. Determining the length of shortest complete sequences is an open problem. We improve the existing upper bound and introduce tools to manually prove the completeness of sequences.

Published
2012-11-22
Article Number
P31