Research in Combinatorial Algorithms

组合算法是计算机科学的核心基础领域。该领域专注于在有限结构上运行的算法，特别是那些具有精确数学描述的算法。本研究的目的是确定一些基本的问题和结构，找到巧妙的算法解决问题的方法，编写代码以有效地实现它们，并对它们进行数学分析。此外，我和我的研究生们也不怕对这些步骤中出现的一些侧面问题进行相当详细的研究，如果这些问题在智力上看起来很有趣和具有挑战性的话。该方案集中在五个方面：Gray编码和de Bruijn循环、嵌套递归关系、维恩图、榻榻米瓷砖和线轴花边。

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 Diagrams Most 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.