Research in Combinatorial Algorithms

组合算法是计算机科学的核心基础领域。该领域专注于在有限结构上运行的算法，特别是那些具有精确数学描述的算法。本研究的目的是确定一些基本的问题和结构，找到巧妙的算法解决问题的方法，编写代码以有效地实现它们，并对它们进行数学分析。此外，我和我的研究生们也不怕对这些步骤中出现的一些侧面问题进行相当详细的研究，如果这些问题在智力上看起来很有趣和具有挑战性的话。该方案集中在五个方面：Gray编码和de Bruijn循环、嵌套递归关系、维恩图、榻榻米瓷砖和线轴花边。灰色编码和德布鲁因循环：搜索空间通常是高度结构化和巨大的；我们打算继续开发有效的算法，以便在这些空间中进行彻底的或其他的搜索。最主要的兴趣是组合格雷码，它是穷尽列表，其中连续的组合对象仅相差一个常量。这样的灰色编码是所有生成算法中最有效的必要前提，在这些算法中，在生成的连续对象之间只完成一定量的工作。Gray码和de Bruijn循环有许多应用，包括计算生物学、旋转轴的位置检测、密码锁破解等。嵌套递归关系：递归关系是计算机科学和数学的基本工具。近年来，我们开始尝试更好地理解“嵌套递归关系”（NRRs），与传统的非嵌套递归关系相比，它在过去很少受到关注。典型的NRR是霍夫施塔特递归式：Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2))，该递归式在普利策奖获奖著作《哥德尔、埃舍尔、巴赫：一条永恒的金辫子》中得到推广。这种递归的关键语法特征是，它只使用加法、减法和组合——组合的嵌套深度至少为两层。我们要研究的递归式都有这些关键特征。我们将根据它们是否可决定进行分类，并尽可能为它们提供组合双标号。维恩图和欧拉图大多数人都熟悉小的“维恩”图，以及它们在表达集合关系和解释三段论中的用途。我们的研究重点是在平面和球面上寻找对称的维恩图，以及包含少量曲线的图的详尽列表。筒子花边：筒子花边是一种古老的艺术形式，至少可以追溯到16世纪，用于制作精美的花边织物图案。考虑到这些模式的规则和通常对称的特性，令人惊讶的是，似乎从来没有人试图精确地编目和理解可能的模式，尽管已经做了一些特别的观察列表和分类。我们的目的是提供一个坚实的数学和计算基础的线轴花边图案。榻榻米：用矩形铺成的正交区域，如果没有四个矩形相交，就称为榻榻米。这种限制在日本房间地板上榻榻米的安排上有着悠久的历史。在我从事这一领域的工作之前，只有在益智书籍和建筑期刊中提到过它们。这有点令人惊讶，因为榻榻米的约束可能是瓷砖上最自然的局部约束。我们将继续研究这些贴片的性质及其推广。

Combinatorial algorithms are a core foundational area of computer science. The area is focused on algorithms that operate on finite structures, particularly those that have precise mathematical descriptions. The objective of this research is to identify some problems and structures that are fundamental, find clever ways to solve the problems algorithmically, write code to implement them efficiently, and analyze them mathematically. Also, my grad students and I are not afraid to pursue in considerable detail some side-angle problem that arises in these steps, if such problem seems somehow intellectually interesting and challenging. This proposal focuses on five areas: Gray codes and de Bruijn cycles, nested recurrence relations, Venn diagrams, tatami tilings, and bobbin lace.Gray codes and de Bruijn Cycles:Search spaces are often highly-structured and huge; we intend to continue our development of efficient algorithms for searching, exhaustively and otherwise, in these spaces. Of primary interest are combinatorial Gray codes, which are exhaustive lists in which successive combinatorial objects differ by only a constant amount. Such Gray codes are a necessary precursor to the most efficient of all generation algorithms, those in which only a constant amount of work is done between successive objects generated. Gray codes and de Bruijn cycles have many applications, including computational biology, position detection on rotating axles, combination lock breaking, etc.Nested recurrence relations:Recurrence relations are a fundamental tool of computer science and mathematics. In recent years, we have begun trying to better understand "nested recurrence relations" (NRRs), which have received scant attention in the past as compared with the traditional non-nested recurrence relations. The prototypical NRR is Hofstadter's recurrence: Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2)), popularized in the Pulitzer Prize winning book "Godel, Escher, Bach: An Eternal Golden Braid". The key syntactic features of this recurrence are that it only uses addition, subtraction, and composition --- and the depth of nesting of the composition is at least two. The recurrences we intend to study all have these key features. We will classify them according to whether they are decidable or not, and provide combinatorial bijections for them whenever possible.Venn and Euler DiagramsMost people are familiar with small "Venn" diagrams, and their use in conveying set relationships and explaining syllogisms. Our research is focused on finding symmetric Venn diagrams, both in the plane and also on the sphere, and on exhaustive listing of diagrams with a small number of curves. Bobbin Lace:Bobbin lace is an old art form, dating back to at least the 16th century, for making fine lace fabric patterns. Given the regular and often symmetric qualities of these patterns, amazingly, there seems to never have been an attempt to precisely catalog and understand the possible patterns, although some ad hoc observational listing and classification has been done. Our aim is to provide a firm mathematical and computational base for bobbin lace patterns.Tatami Tilings:A tiling of an orthogonal region with rectangles is said to be tatami if no four rectangles meet. Such a restriction has a long history in the arrangement of tatami mats on the floors of Japanese rooms. Previous to my work in this area, there were only a couple of mentions of them in puzzle books and in architectural journals. This is somewhat surprising, since the tatami constraint is perhaps the most natural local constraint to place on a tiling. We will continue our investigations into the properties of these tilings and their generalizations.