Computability and Decision Procedures for Number Theory and Combinatorics

数论和组合学的可计算性和决策程序

基本信息

  • 批准号:
    RGPIN-2018-04118
  • 负责人:
  • 金额:
    $ 3.5万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2019
  • 资助国家:
    加拿大
  • 起止时间:
    2019-01-01 至 2020-12-31
  • 项目状态:
    已结题

项目摘要

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? And can we use automated theorem-proving to prove our mathematical insights "purely mechanically"?******To take an example, consider additive number theory: the study of how to represent numbers as the sum of members of a given set. This is a well-studied area of pure mathematics that includes such celebrated results as Waring's theorem on sums of powers of integers (proved by Hilbert), and the Goldbach conjecture about sums of primes (still unproved). Recently, Cilleruelo, Luca, and Baxter proved that, for bases b 5, every natural number is the sum of at most three numbers whose base-b representation is a palindrome (a number that reads the same forwards and backwards, like the English word radar). But they were unable to prove this for bases b = 2, 3, 4.******My collaborators and I completed the additive theory of the palindromes for the remaining cases, using automata theory and a decision procedure. For example, to handle the case of base b = 2, we rephrased the assertion "every natural number is the sum of at most four binary palindromes" as a claim about the computational behavior of a particular automaton A. We then used a known decision procedure for the universality problem for this class of automata to prove that our automaton A has the specified behavior. This is just one of many similar problems that are amenable to this approach.******I propose to apply these ideas to many other problems in number theory, combinatorics, and algebra. 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.
从广义上讲,我的研究涉及两个不同的领域以及它们如何相互作用。第一个领域涉及简单计算机(“自动机”)的数学模型及其功能。第二个领域涉及纯数学的基础:数论,组合数学和代数。虽然这两个领域表面上看起来很分离,但实际上它们是紧密相连的。我们如何使用自动机理论的见解来为纯数学做出贡献,反之亦然?我们能用自动化的定理证明来“纯粹机械地”证明我们的数学见解吗?举个例子,考虑加法数论:研究如何将数字表示为给定集合的成员之和。这是纯数学的一个研究得很好的领域,其中包括诸如关于整数幂和的华林定理(由希尔伯特证明)和关于素数和的哥德巴赫猜想(尚未证明)等著名的结果。最近,Cilleruelo、Luca和巴克斯特证明了,对于基数B为5的自然数,每个自然数都是至多三个基数为B的数字的和,这些数字的表示是回文(一个向前和向后读起来都一样的数字,就像英语单词radar)。但是他们无法证明B = 2,3,4的情况。我和我的合作者们利用自动机理论和一个决策过程,完成了剩余情况下的回文的加法理论。例如,为了处理基数B = 2的情况,我们将断言“每个自然数最多是四个二进制回文的和”重新表述为关于特定自动机A的计算行为的声明。然后,我们使用一个已知的决策程序的普遍性问题,这类自动机,以证明我们的自动机A具有指定的行为。这只是许多类似问题中的一个,这些问题都适用于这种方法。我打算把这些思想应用到数论、组合数学和代数中的许多其他问题上。我将确定合适的问题,寻找合适的计算模型,可以解决这些问题,并应用决策程序来证明定理。我也将指导自由软件的准备工作,以便其他数学家和计算机科学家可以在他们自己的工作中使用这种方法。我的学生Hamoon Mousavi已经开发了一些开源软件,叫做Walnut,其他研究人员也在使用。我的工作积极涉及高素质人才的培训,从本科生到博士后研究人员。这些对我的工作至关重要,无论是解决问题还是编写软件。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Shallit, Jeffrey其他文献

Avoiding squares and overlaps over the natural numbers
  • DOI:
    10.1016/j.disc.2009.06.004
  • 发表时间:
    2009-11-06
  • 期刊:
  • 影响因子:
    0.8
  • 作者:
    Guay-Paquet, Mathieu;Shallit, Jeffrey
  • 通讯作者:
    Shallit, Jeffrey
Avoiding 3/2-powers over the natural numbers
  • DOI:
    10.1016/j.disc.2011.12.019
  • 发表时间:
    2012-03-28
  • 期刊:
  • 影响因子:
    0.8
  • 作者:
    Rowland, Eric;Shallit, Jeffrey
  • 通讯作者:
    Shallit, Jeffrey
A pattern sequence approach to Stern's sequence
  • DOI:
    10.1016/j.disc.2011.07.029
  • 发表时间:
    2011-11-28
  • 期刊:
  • 影响因子:
    0.8
  • 作者:
    Coons, Michael;Shallit, Jeffrey
  • 通讯作者:
    Shallit, Jeffrey
Efficient enumeration of words in regular languages
  • DOI:
    10.1016/j.tcs.2009.03.018
  • 发表时间:
    2009-09-01
  • 期刊:
  • 影响因子:
    1.1
  • 作者:
    Ackerman, Margareta;Shallit, Jeffrey
  • 通讯作者:
    Shallit, Jeffrey
Decidability of Sturmian Words
Sturmian 单词的可判定性

Shallit, Jeffrey的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Shallit, Jeffrey', 18)}}的其他基金

Computability and Decision Procedures for Number Theory and Combinatorics
数论和组合学的可计算性和决策程序
  • 批准号:
    RGPIN-2018-04118
  • 财政年份:
    2022
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Computability and Decision Procedures for Number Theory and Combinatorics
数论和组合学的可计算性和决策程序
  • 批准号:
    RGPIN-2018-04118
  • 财政年份:
    2021
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Computability and Decision Procedures for Number Theory and Combinatorics
数论和组合学的可计算性和决策程序
  • 批准号:
    RGPIN-2018-04118
  • 财政年份:
    2020
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Computability and Decision Procedures for Number Theory and Combinatorics
数论和组合学的可计算性和决策程序
  • 批准号:
    RGPIN-2018-04118
  • 财政年份:
    2018
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Avoidability and Decidability in Formal Languages and Automata
形式语言和自动机中的可避免性和可判定性
  • 批准号:
    105829-2013
  • 财政年份:
    2017
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Avoidability and Decidability in Formal Languages and Automata
形式语言和自动机中的可避免性和可判定性
  • 批准号:
    105829-2013
  • 财政年份:
    2016
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Avoidability and Decidability in Formal Languages and Automata
形式语言和自动机中的可避免性和可判定性
  • 批准号:
    105829-2013
  • 财政年份:
    2015
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Avoidability and Decidability in Formal Languages and Automata
形式语言和自动机中的可避免性和可判定性
  • 批准号:
    105829-2013
  • 财政年份:
    2014
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Avoidability and Decidability in Formal Languages and Automata
形式语言和自动机中的可避免性和可判定性
  • 批准号:
    105829-2013
  • 财政年份:
    2013
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Descriptional complexity, combinatorics on words, formal languages and number theory
描述复杂性、单词组合学、形式语言和数论
  • 批准号:
    105829-2008
  • 财政年份:
    2012
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual

相似国自然基金

Scalable Learning and Optimization: High-dimensional Models and Online Decision-Making Strategies for Big Data Analysis
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    万元
  • 项目类别:
    合作创新研究团队

相似海外基金

CAREER: Robust Online Decision Procedures for Societal Scale CPS
职业:社会规模 CPS 的稳健在线决策程序
  • 批准号:
    2238815
  • 财政年份:
    2023
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Continuing Grant
EC1 is a mobile 360-degree point-of-view learning and gamification tool integrating a VR scenario, APIE response procedures and assessment to test and improve firefighter decision-making and response.
EC1是一款移动360度视角学习和游戏化工具,集成了VR场景、APIE响应程序和评估,以测试和改进消防员的决策和响应。
  • 批准号:
    10459708
  • 财政年份:
    2022
  • 资助金额:
    $ 3.5万
  • 项目类别:
Computability and Decision Procedures for Number Theory and Combinatorics
数论和组合学的可计算性和决策程序
  • 批准号:
    RGPIN-2018-04118
  • 财政年份:
    2022
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Collaborative Research: Experiments on Procedures and Prediction in Economic Decision Making
合作研究:经济决策过程和预测的实验
  • 批准号:
    2049748
  • 财政年份:
    2021
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Continuing Grant
Computability and Decision Procedures for Number Theory and Combinatorics
数论和组合学的可计算性和决策程序
  • 批准号:
    RGPIN-2018-04118
  • 财政年份:
    2021
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
Collaborative Research: Experiments on Procedures and Prediction in Economic Decision Making
合作研究:经济决策过程和预测的实验
  • 批准号:
    2049749
  • 财政年份:
    2021
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Continuing Grant
Applying Decision Procedures to Synthesis Problems
将决策程序应用于综合问题
  • 批准号:
    2444465
  • 财政年份:
    2020
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Studentship
Computability and Decision Procedures for Number Theory and Combinatorics
数论和组合学的可计算性和决策程序
  • 批准号:
    RGPIN-2018-04118
  • 财政年份:
    2020
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Discovery Grants Program - Individual
CAREER: Decision Procedures for High-Assurance, AI-Controlled, Cyber-Physical Systems
职业:高可信度、人工智能控制、网络物理系统的决策程序
  • 批准号:
    1845194
  • 财政年份:
    2019
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Continuing Grant
CAREER: Decision Procedures for High-Assurance, AI-Controlled, Cyber-Physical Systems
职业:高可信度、人工智能控制、网络物理系统的决策程序
  • 批准号:
    2002405
  • 财政年份:
    2019
  • 资助金额:
    $ 3.5万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了