Scholarlink

<p>Orientable sequences of order <i>n</i> are infinite periodic sequences with symbols drawn from a finite alphabet of size <i>k</i> with the property that any tuple of <i>n</i> elements or its reverse occurs at most once as a contiguous subsequence (i.e. a substring or factor) in a period. They were introduced in the early 1990s in the context of possible applications in position sensing. Bounds on the period of such sequences and a range of methods of construction have been devised, although apart from very small cases a significant gap remains between the largest known period for such a sequence and the best known upper bound. In this paper we first give improved upper bounds on the period of such sequences. We then give a new general method of construction for orientable sequences involving subgraphs of the de Bruijn graph with special properties, and describe two different approaches for generating such subgraphs. This enables us to construct orientable sequences with periods meeting the improved upper bounds when <i>n</i> is 2 or 3, as well as <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(n=4\)</EquationSource> </InlineEquation> and <i>k</i> odd. For <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(4\le n\le 8\)</EquationSource> </InlineEquation>, in some cases the sequences produced by the methods described have periods larger than for any previously known sequences.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

New orientable sequences

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年3月18日

查看全文
  • Chris J. Mitchell,
  • Peter R. Wild

摘要

Orientable sequences of order n are infinite periodic sequences with symbols drawn from a finite alphabet of size k with the property that any tuple of n elements or its reverse occurs at most once as a contiguous subsequence (i.e. a substring or factor) in a period. They were introduced in the early 1990s in the context of possible applications in position sensing. Bounds on the period of such sequences and a range of methods of construction have been devised, although apart from very small cases a significant gap remains between the largest known period for such a sequence and the best known upper bound. In this paper we first give improved upper bounds on the period of such sequences. We then give a new general method of construction for orientable sequences involving subgraphs of the de Bruijn graph with special properties, and describe two different approaches for generating such subgraphs. This enables us to construct orientable sequences with periods meeting the improved upper bounds when n is 2 or 3, as well as \(n=4\) and k odd. For \(4\le n\le 8\) , in some cases the sequences produced by the methods described have periods larger than for any previously known sequences.