论文标题
与二进制de Bruijn序列的贪婪方法的图形
A Graph Joining Greedy Approach to Binary de Bruijn Sequences
论文作者
论文摘要
使用贪婪的算法生成de bruijn序列是一种经典方法，它产生了许多有趣的理论结果。本文研究了一种算法，我们称之为广义优选材料（GPO）。它包括所有先前的贪婪算法，除了在de bruijn图上应用的Fleury算法（作为特定情况）。 GPO算法可以在输入一对合适的反馈函数和初始状态上至少产生任何具有非线性复杂性的二元期刊序列。特别是，建立了GPO算法生成二元de bruijn序列的足够和必要条件。这需要在其各自的状态图中使用唯一周期或循环的反馈函数。此外，我们讨论了对GPO算法的修改，以处理更多的反馈功能家族的状态图具有多个周期或循环。这些最终以图形连接方法结束。随后使用了几种大类反馈功能来说明GPO算法及其在实践中加入Peave-Opposite（GJPO）算法的图表中如何修改。
Using greedy algorithms to generate de Bruijn sequences is a classical approach that has produced numerous interesting theoretical results. This paper investigates an algorithm which we call the Generalized Prefer-Opposite (GPO). It includes all prior greedy algorithms, with the exception of the Fleury Algorithm applied on the de Bruijn graph, as specific instances. The GPO Algorithm can produce any binary periodic sequences with nonlinear complexity at least two on input a pair of suitable feedback function and initial state. In particular, a sufficient and necessary condition for the GPO Algorithm to generate binary de Bruijn sequences is established. This requires the use of feedback functions with a unique cycle or loop in their respective state graphs. Moreover, we discuss modifications to the GPO Algorithm to handle more families of feedback functions whose state graphs have multiple cycles or loops. These culminate in a graph joining method. Several large classes of feedback functions are subsequently used to illustrate how the GPO Algorithm and its modification into the Graph Joining Prefer-Opposite (GJPO) Algorithm work in practice.
