Grant: Discovery Grants Program - Individual
McMaster University
$48,000.00
Algebra, logic, and complexity
EF 2024-25
Résumé
Algebraic structures arise in many different contexts, not only within mathematics, but in most of the sciences, and even in day to day life. For example, algebras known as groups are used to represent the symmetries of crystals and other physical systems, and Boolean algebras are used to codify rules of logic. Many other common systems, in particular those arising from questions in computer science can be viewed in an algebraic way. Thus research on algebraic structures can have an impact on several branches of the sciences and in particular on computer science.
Several important properties of algebraic systems can be expressed via equations. For example, the fact that addition is commutative is expressed by the equation x + y = y + x. It has proved useful to organize and classify algebraic systems according to the equations that they satisfy. These equationally defined classes of algebras, called varieties, are objects that I study in my research. One of the long term objectives of my research is to investigate the connection between various types of complexities that can arise in varieties and the structure of the algebras that belong to them.
A more recent direction that my research has taken relates to problems and questions from theoretical computer science. An important class of problems, known as constraint satisfaction problems (CSPs), has a natural expression in terms of finite algebras. CSPs are ubiquitous in many areas of artificial intelligence, computer science, and discrete mathematics, such as database theory, scheduling, and networking. A system of linear equations can be viewed as a special type of CSP. Another long term objective of my research is to understand the correlation between well behaved/manageable subclasses of CSPs and related problems and the structure of the corresponding algebraic systems that define them.
In computer science, trees are a certain kind of ordered data type that can be used to store information that has a natural hierarchical structure. Depending on the complexity of the trees being considered, they can be processed by simple computing devices known as finite state tree automata. The collection of trees that a given finite state tree automaton can process is called a regular tree language. A big open problem in automata theory is to find an effective characterization of regular tree languages that can be defined using a first order sentence. A long term objective of my research is to solve this problem and to more generally investigate regular tree languages from the perspective of definability.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2020-05714
Name nom
Valeriote, Matthew
Department département
Mathematics and Statistics - Mathematics and Statistics
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2020
Award amount
48000
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
2912
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Logic
Research subject fr
Logique
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
Algebra, logic, and complexity
Keywords
universal algebra; computational complexity; maltsev conditions; tree languages and automata; constraint satisfaction; mathematical logic; model theory
Application summary
Algebraic structures arise in many different contexts, not only within mathematics, but in most of the sciences, and even in day to day life. For example, algebras known as groups are used to represent the symmetries of crystals and other physical systems, and Boolean algebras are used to codify rules of logic. Many other common systems, in particular those arising from questions in computer science can be viewed in an algebraic way. Thus research on algebraic structures can have an impact on several branches of the sciences and in particular on computer science.
Several important properties of algebraic systems can be expressed via equations. For example, the fact that addition is commutative is expressed by the equation x + y = y + x. It has proved useful to organize and classify algebraic systems according to the equations that they satisfy. These equationally defined classes of algebras, called varieties, are objects that I study in my research. One of the long term objectives of my research is to investigate the connection between various types of complexities that can arise in varieties and the structure of the algebras that belong to them.
A more recent direction that my research has taken relates to problems and questions from theoretical computer science. An important class of problems, known as constraint satisfaction problems (CSPs), has a natural expression in terms of finite algebras. CSPs are ubiquitous in many areas of artificial intelligence, computer science, and discrete mathematics, such as database theory, scheduling, and networking. A system of linear equations can be viewed as a special type of CSP. Another long term objective of my research is to understand the correlation between well behaved/manageable subclasses of CSPs and related problems and the structure of the corresponding algebraic systems that define them.
In computer science, trees are a certain kind of ordered data type that can be used to store information that has a natural hierarchical structure. Depending on the complexity of the trees being considered, they can be processed by simple computing devices known as finite state tree automata. The collection of trees that a given finite state tree automaton can process is called a regular tree language. A big open problem in automata theory is to find an effective characterization of regular tree languages that can be defined using a first order sentence. A long term objective of my research is to solve this problem and to more generally investigate regular tree languages from the perspective of definability.