Combinatorics on words and digital geometry

文字与数字几何的组合学

• 批准号: 46482-2013
• 负责人: Brlek, Srecko
• 金额: $ 1.82万
• 依托单位: Université du Québec à Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=680371
• 关键词: Combinatorics; words; digital; geometry

My main research domain is combinatorics on words, where the algorithmic point of view plays an important role both on the theoretical and practical aspects. I developed my research along the following axes where combinatorics of words are central: A. Combinatorics of infinite words B. Digital geometry and tilings C. Formal languages and applications A. In this area I am mostly concerned with palindromic complexity (number of distinct palindomic subwords) and subword or factor complexity (number of distinct factors). It is used for classifying words and particularly fixed points of morphisms accordingly. I also study a particular class of infinite words (called smooth) related to the exponential trajectories of Oldenburger, which include the fixed points of exponential trajectories and therefore the Kolakoski word. B. The contour of discrete figures is encoded by the so-called Freeman chain code, a word on a 4-letter alphabet consisting of the four elementary steps in the digital plane (square grid). Combinatorics on words apply therefore directly and provide useful tools for developing new algorithms. Palindromes and finite Sturmian words again appear, since they encode respectively symmetries and line segments. Lyndon factorizations also apply in the segmentation. The case of polyominoes that tile the plane by translation is a source of numerous problems also linked with number theory. C. I study enumeration problems, often are enumerated by rational or algebraic languages. I also consider the problems of exhaustive and random generation of combinatorial objects.

我的主要研究领域是单词组合学，其中算法的观点在理论和实践方面都发挥着重要作用。我沿着以单词组合为中心的以下轴开展我的研究：A. 无限单词的组合 B. 数字几何和平铺 C. 形式语言和应用 A. 在这个领域，我主要关注回文复杂性（不同回文子词的数量）和子词或因子复杂性（不同因子的数量）。它用于对单词和特别是态射的固定点进行相应的分类。我还研究了与 Oldenburger 指数轨迹相关的一类特定的无限词（称为平滑词），其中包括指数轨迹的不动点，因此也包括 Kolakoski 词。 B. 离散图形的轮廓由所谓的弗里曼链码进行编码，弗里曼链码是 4 个字母字母表上的一个单词，由数字平面（方形网格）中的四个基本步骤组成。因此，单词组合学可以直接应用，并为开发新算法提供有用的工具。回文和有限的斯图姆词再次出现，因为它们分别编码对称性和线段。 Lyndon 分解也适用于分割。通过平移平铺平面的多联骨牌的情况是许多也与数论相关的问题的根源。 C. 我研究枚举问题，经常用有理或代数语言来枚举。我还考虑了组合对象的详尽和随机生成的问题。