Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Université du Québec à Montréal

$25,000.00

Combinatorics on words and digital geometry

EF 2013-14

Résumé
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.
Programme
Discovery Grants Program - Individual
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
46482-2013
Name nom
Brlek, Srecko
Department département
Informatique
Organization id
57
Institution établissement
Université du Québec à Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2013
Competition year année de concours
2013
Award amount
25000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
1
Nb partie
5
Application title
Combinatorics on words and digital geometry
Keyword
NSERC
Application summary
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.