Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$55,000.00

Novel Applications of Logic and Automata Theory to Number Theory and Combinatorics on Words

EF 2024-25

Résumé
Broadly speaking, my research involves two different areas and how they interact. The first area concerns mathematical models of simple computers ("automata") and their capabilities. The second area concerns the basics of pure mathematics: number theory, combinatorics, and algebra. Although these two areas superficially seem quite separated, in reality they are closely connected. How can we use insights from automata theory to contribute to pure mathematics, and vice versa?  Answers will provide researchers with novel methods and tools to attack old problems. Consider some examples.  My co-authors and I have shown that a logical decision procedure due to Büchi in the 1960's, and subsequently refined by Bruyère et al. in the 1990's, can be used to prove many results in discrete mathematics "purely mechanically", simply by stating the result as an appropriate first-order logical statement.   Although the worst-case running time of the decision procedure is enormous, it nevertheless appears to be extremely useful in practice, as evidenced by over 70 papers published in the peer-reviewed literature where this technique has been used.   As I and co-authors have shown, these techniques can be used to compute many aspects of well-studied sequences, such as subword complexity (number of distinct length-n blocks), recurrence (maximum gaps between two successive occurrences of the same block), and pattern avoidance.  A classic result of Thue---that there exist infinite words over a three-letter alphabet containing no two adjacent identical blocks---can be rigorously proved in milliseconds on a computer with this decision procedure.   These ideas have been applied to an old area of pure mathematics:   additive number theory, which goes back to the 18th century work of Waring on sums of powers.  Here we are concerned with deciding whether every natural number can be written as a sum of a fixed number of summands from a given set.   Automata theory provides new tools to the additive number theorist.   As an example, my co-authors used automata theory to prove that every natural number is the sum of four numbers, each of which is a palindrome when expressed in base 2.   This resolved an open case of a similar theorem proved for larger bases by Cilleruelo, Luca, and Baxter. I will identify suitable problems, search for appropriate computational models that can resolve them, and apply decision procedures to prove the theorems. I will also direct the preparation of free software, so that other mathematicians and computer scientists can use this approach in their own work. Already some open-source software, called Walnut, has been created by my student Hamoon Mousavi, and is being used by other researchers. My work actively involves the training of highly-qualified personnel, ranging from undergraduate students to postdoctoral researchers. These are essential to my work, both for solving problems and for writing software.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2024-03725
Name nom
Shallit, Jeffrey
Department département
School of Computer Science
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
55000
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
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
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
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
Novel Applications of Logic and Automata Theory to Number Theory and Combinatorics on Words
Keywords
finite automata; combinatorics on words; number theory; formal languages; first-order logic; automated theorem-proving; decision procedure; decidable theory
Application summary
Broadly speaking, my research involves two different areas and how they interact. The first area concerns mathematical models of simple computers ("automata") and their capabilities. The second area concerns the basics of pure mathematics: number theory, combinatorics, and algebra. Although these two areas superficially seem quite separated, in reality they are closely connected. How can we use insights from automata theory to contribute to pure mathematics, and vice versa?  Answers will provide researchers with novel methods and tools to attack old problems. Consider some examples.  My co-authors and I have shown that a logical decision procedure due to Büchi in the 1960's, and subsequently refined by Bruyère et al. in the 1990's, can be used to prove many results in discrete mathematics "purely mechanically", simply by stating the result as an appropriate first-order logical statement.   Although the worst-case running time of the decision procedure is enormous, it nevertheless appears to be extremely useful in practice, as evidenced by over 70 papers published in the peer-reviewed literature where this technique has been used.   As I and co-authors have shown, these techniques can be used to compute many aspects of well-studied sequences, such as subword complexity (number of distinct length-n blocks), recurrence (maximum gaps between two successive occurrences of the same block), and pattern avoidance.  A classic result of Thue---that there exist infinite words over a three-letter alphabet containing no two adjacent identical blocks---can be rigorously proved in milliseconds on a computer with this decision procedure.   These ideas have been applied to an old area of pure mathematics:   additive number theory, which goes back to the 18th century work of Waring on sums of powers.  Here we are concerned with deciding whether every natural number can be written as a sum of a fixed number of summands from a given set.   Automata theory provides new tools to the additive number theorist.   As an example, my co-authors used automata theory to prove that every natural number is the sum of four numbers, each of which is a palindrome when expressed in base 2.   This resolved an open case of a similar theorem proved for larger bases by Cilleruelo, Luca, and Baxter. I will identify suitable problems, search for appropriate computational models that can resolve them, and apply decision procedures to prove the theorems. I will also direct the preparation of free software, so that other mathematicians and computer scientists can use this approach in their own work. Already some open-source software, called Walnut, has been created by my student Hamoon Mousavi, and is being used by other researchers. My work actively involves the training of highly-qualified personnel, ranging from undergraduate students to postdoctoral researchers. These are essential to my work, both for solving problems and for writing software.