Combinatorics on words and digital geometry

文字与数字几何的组合学

• 批准号: 46482-2013
• 负责人: Brlek, Srecko
• 金额: $ 1.82万
• 依托单位: Université du Québec à Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=646279
• 关键词: 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.离散图形的轮廓由所谓的Freeman链码编码，即由数字平面(正方形网格)中的四个基本步骤组成的四个字母表上的一个单词。因此，词的组合学直接适用，并为开发新算法提供了有用的工具。回文和有限的Sturmian单词再次出现，因为它们分别编码对称和线段。林登因式分解也适用于分段。通过平移平铺平面的多项式的例子是许多问题的来源，也与数论有关。**C.我研究枚举问题，通常用有理或代数语言来列举。我还考虑了组合对象的穷举和随机生成问题。