Grant: Discovery Grants Program - Individual
University of Calgary
$32,350.00
Proof Theory and Logic in Computer Science
FY 2023-24
Summary
Many important applications of computing can be characterized as the automation of reasoning tasks. A small sampling of these include finding answers to questions such as: Does this circuit conform to a given specification? Is this algorithm guaranteed to produce a result? What does this knowledge base imply about a certain problem? What kind of result does this program compute, given the types of its inputs? Given certain access rules, is this user allowed to view this file? The corresponding fields of hardware and software verification, knowledge representation and inference, type checking and inference in programming language design, and data security all make fundamental use of logical formalisms and proof systems developed by logicians. In the past 25 years, advances in hard- and software and in the theoretical foundations of logical inference systems have led to software applications that work at industrial scales, and that are now used by major companies such as Amazon, Boeing, and Intel. Many of the theoretical foundations, however, were laid by philosophers working in logic, and interactions between computer scientists and philosophers in this area remain strong and fruitful. For many applications, it is necessary to develop logical formalisms that diverge in various ways from what is known as "classical logic". One important such logic is known as "intuitionistic" logic. It is the paradigm example of a "constructive" logic for which there are close connections between logical proofs and programs. This connection, and the theory of proofs in intuitionistic logic, is the fundamental theoretical basis for type checking and inference for programming languages. Intuitionistic logic can be extended by adding additional axioms (yielding so-called intermediate logics) or by adding additional language elements (e.g., additional operators such as exclusion or if-then-else constructions, and logical choice operators). Other constructive logics promise to have similar applications. Continuing research previously funded through NSERC's computer science program, the project develops such extensions and alternative logical systems, and investigates their proof-theoretic properties. Applications of logic in formal specification and verification, knowledge representation, data security, and other areas rely on extensions of classical logic. Of particular importance here are so-called modal logics of time, belief, knowledge, and obligation. The project also develops and studies proof systems for such logics, e.g., analytic tableau systems for new modal logics and combinations of existing ones. It extends the scope of existing logical proof systems and their implementations to new, more expressive logics with a wider domain of application. Through knowledge dissemination and the training of highly qualified personnel, this contributes to the expansion of expertise in formal methods in Canada and beyond.
Program
Discovery Grants Program - Individual
Recipient
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2023-03427
Name nom
Zach, Richard
Department département
Philosophy
Organization id
11
Institution établissement
University of Calgary
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2023
Award amount
32350
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
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
Logic
Research subject en
Mathématiques pures
Research subject fr
Logique
Application title
Proof Theory and Logic in Computer Science
Keyword
automated theorem proving; computer science education; lambda calculus; logic; non-monotonic reasoning; proof theory; type systems
Application summary
Many important applications of computing can be characterized as the automation of reasoning tasks. A small sampling of these include finding answers to questions such as: Does this circuit conform to a given specification? Is this algorithm guaranteed to produce a result? What does this knowledge base imply about a certain problem? What kind of result does this program compute, given the types of its inputs? Given certain access rules, is this user allowed to view this file? The corresponding fields of hardware and software verification, knowledge representation and inference, type checking and inference in programming language design, and data security all make fundamental use of logical formalisms and proof systems developed by logicians. In the past 25 years, advances in hard- and software and in the theoretical foundations of logical inference systems have led to software applications that work at industrial scales, and that are now used by major companies such as Amazon, Boeing, and Intel. Many of the theoretical foundations, however, were laid by philosophers working in logic, and interactions between computer scientists and philosophers in this area remain strong and fruitful. For many applications, it is necessary to develop logical formalisms that diverge in various ways from what is known as "classical logic". One important such logic is known as "intuitionistic" logic. It is the paradigm example of a "constructive" logic for which there are close connections between logical proofs and programs. This connection, and the theory of proofs in intuitionistic logic, is the fundamental theoretical basis for type checking and inference for programming languages. Intuitionistic logic can be extended by adding additional axioms (yielding so-called intermediate logics) or by adding additional language elements (e.g., additional operators such as exclusion or if-then-else constructions, and logical choice operators). Other constructive logics promise to have similar applications. Continuing research previously funded through NSERC's computer science program, the project develops such extensions and alternative logical systems, and investigates their proof-theoretic properties. Applications of logic in formal specification and verification, knowledge representation, data security, and other areas rely on extensions of classical logic. Of particular importance here are so-called modal logics of time, belief, knowledge, and obligation. The project also develops and studies proof systems for such logics, e.g., analytic tableau systems for new modal logics and combinations of existing ones. It extends the scope of existing logical proof systems and their implementations to new, more expressive logics with a wider domain of application. Through knowledge dissemination and the training of highly qualified personnel, this contributes to the expansion of expertise in formal methods in Canada and beyond.