Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Université du Québec à Montréal

$34,000.00

Exploring combinatory logic via clone theory: an algebraic and combinatorial approach

EF 2024-25

Résumé
My research program is situated at the crossroad of combinatorics, algebra, and theoretical computer science. Its goal is to establish deep and enduring connections between combinatory logic (CL) and algebraic combinatorics, two fields that traditionally evolve independently and employ distinct methodologies. My approach involves the use of clone theory and tools specific to combinatorics to obtain new results in CL. I also intend to employ CL as a singular source for proposing innovative combinatorial constructions and new tools for enumeration. Combinatorics studies sets of discrete objects such as permutations, trees, or graphs. An important goal consists in designing general tools for the enumeration of such objects. Among these, the algebraic approach consists in endowing such sets with operations to form algebraic structures. This approach often reveals crucial properties of the objects by making apparent the elementary pieces by which they are built. Clones are the main algebraic structures considered in this research. They provide abstractions of operators and their compositions. The second main protagonist is CL, a model of computation akin to lambda-calculus. Its combinatorial heart is formed by terms, which are binary trees with labeled leaves, and rules to compute a result from a term, which are rewrite relations on trees. In the first axis of my research program, I consider clones which encode equivalence classes of terms which eventually rewrite to the same term. I plan to use tools from algebraic combinatorics, such as its range of combinatorial sets and spaces, combinatorial transformations, and changes of basis within the category of vector spaces, to examine their substructures and quotients. I expect to obtain a framework for studying both the extensional equivalence of terms and proposing new models of CL. The second axis involves extending to the level of clones four classical constructions serving as tools for enumeration, which take operads as inputs. These constructions produce generalized formal series, Hopf algebras, formal grammars, and pairs of dual graded graphs. The objective is to obtain more powerful tools for the enumeration of set of combinatorial objects or species of structures. I am mainly interested in studying such constructions arising from the clones of CL to gain new insights on this theory. The third axis concerns the study of rewrite graphs of terms. In this context, I aim to establish connections between CL and the theories of posets and lattices. Among the key questions, I wish to identify conditions under which the rewrite graph of a term is the Hasse diagram of a poset or a lattice. I plan to devise methods to enumerate particular elements in these structures, such as the minimal and maximal elements, by developing methods to enumerate terms avoiding patterns. This research is designed to facilitate significant advances in CL, algebra, combinatorics, and theoretical computer science.
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
RGPIN-2024-04465
Name nom
Giraudo, Samuele
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
2024
Competition year année de concours
2024
Award amount
34000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
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
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Exploring combinatory logic via clone theory: an algebraic and combinatorial approach
Keywords
algebraic combinatorics; combinatory logic; clones; treelike structures; term rewrite systems; graphs; partially ordered sets; operads; hopf algebras; models of computation
Application summary
My research program is situated at the crossroad of combinatorics, algebra, and theoretical computer science. Its goal is to establish deep and enduring connections between combinatory logic (CL) and algebraic combinatorics, two fields that traditionally evolve independently and employ distinct methodologies. My approach involves the use of clone theory and tools specific to combinatorics to obtain new results in CL. I also intend to employ CL as a singular source for proposing innovative combinatorial constructions and new tools for enumeration. Combinatorics studies sets of discrete objects such as permutations, trees, or graphs. An important goal consists in designing general tools for the enumeration of such objects. Among these, the algebraic approach consists in endowing such sets with operations to form algebraic structures. This approach often reveals crucial properties of the objects by making apparent the elementary pieces by which they are built. Clones are the main algebraic structures considered in this research. They provide abstractions of operators and their compositions. The second main protagonist is CL, a model of computation akin to lambda-calculus. Its combinatorial heart is formed by terms, which are binary trees with labeled leaves, and rules to compute a result from a term, which are rewrite relations on trees. In the first axis of my research program, I consider clones which encode equivalence classes of terms which eventually rewrite to the same term. I plan to use tools from algebraic combinatorics, such as its range of combinatorial sets and spaces, combinatorial transformations, and changes of basis within the category of vector spaces, to examine their substructures and quotients. I expect to obtain a framework for studying both the extensional equivalence of terms and proposing new models of CL. The second axis involves extending to the level of clones four classical constructions serving as tools for enumeration, which take operads as inputs. These constructions produce generalized formal series, Hopf algebras, formal grammars, and pairs of dual graded graphs. The objective is to obtain more powerful tools for the enumeration of set of combinatorial objects or species of structures. I am mainly interested in studying such constructions arising from the clones of CL to gain new insights on this theory. The third axis concerns the study of rewrite graphs of terms. In this context, I aim to establish connections between CL and the theories of posets and lattices. Among the key questions, I wish to identify conditions under which the rewrite graph of a term is the Hasse diagram of a poset or a lattice. I plan to devise methods to enumerate particular elements in these structures, such as the minimal and maximal elements, by developing methods to enumerate terms avoiding patterns. This research is designed to facilitate significant advances in CL, algebra, combinatorics, and theoretical computer science.