Grant: Discovery Grants Program - Individual
Université Laval
$28,000.00
""Domain algebra, quantum algebra, refinement algebra""
FY 2016-17
Summary
This research is about the mathematics of program construction, a branch of formal methods. It consists in finding methods for rigorously (mathematically) specifying what we want a computer to do, and then deriving a correct program from the specification (the program is said to refine the specification). The goal of these methods is to obtain programs that are correct by construction, rather than verifying them later to correct bugs. This research uses algebraic techniques to describe specifications, programs and refinement. It has five main objectives. (1) Determining whether so-called refinement algebras with a domain operator are decidable, i.e., whether there exists an algorithm deciding if two expressions of the algebra are equal. This property is important when using the algebras in practice, since automated deductions can be carried out. (2) Find algebras modelling the behaviour of quantum automata. These automata are abstract quantum computers with a rather weak computing power, but understanding them better is a way to improve our knowledge of what quantum computation will bring when quantum computers are available. (3) Devise refinement algebras for probabilistic and quantum programming. (4) Find an algorithm for calculating controllers for visibly pushdown automata, another abstract type of computer that is useful for modelling some properties of programs. If this research is successful, it will yield applications to program security. (5) Mathematically derive efficient programs (i.e., fast and using little memory) for solving problems in digital geometry. An example of a 2-D digital geometry is that of a computer screen, made of discrete pixels rather than a continuous set of points. Surprisingly, not much research on computational complexity (the branch of computing science targeting efficient programs) has been done in this area, at least when compared to continuous geometry. This is thus a good occasion to invent new algorithms while proving their correctness in the rigorous style of the mathematics of program construction.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
89769-2012
Name nom
Desharnais, Jules
Department département
Informatique et de génie logiciel
Organization id
51
Institution établissement
Université Laval
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2012
Award amount
28000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à 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
2714
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Mathematics of computing
Research subject fr
Mathématiques de l'informatique
Partie
5
Nb partie
5
Application title
""Domain algebra, quantum algebra, refinement algebra""
Keyword
NSERC
Application summary
This research is about the mathematics of program construction, a branch of formal methods. It consists in finding methods for rigorously (mathematically) specifying what we want a computer to do, and then deriving a correct program from the specification (the program is said to refine the specification). The goal of these methods is to obtain programs that are correct by construction, rather than verifying them later to correct bugs. This research uses algebraic techniques to describe specifications, programs and refinement. It has five main objectives. (1) Determining whether so-called refinement algebras with a domain operator are decidable, i.e., whether there exists an algorithm deciding if two expressions of the algebra are equal. This property is important when using the algebras in practice, since automated deductions can be carried out. (2) Find algebras modelling the behaviour of quantum automata. These automata are abstract quantum computers with a rather weak computing power, but understanding them better is a way to improve our knowledge of what quantum computation will bring when quantum computers are available. (3) Devise refinement algebras for probabilistic and quantum programming. (4) Find an algorithm for calculating controllers for visibly pushdown automata, another abstract type of computer that is useful for modelling some properties of programs. If this research is successful, it will yield applications to program security. (5) Mathematically derive efficient programs (i.e., fast and using little memory) for solving problems in digital geometry. An example of a 2-D digital geometry is that of a computer screen, made of discrete pixels rather than a continuous set of points. Surprisingly, not much research on computational complexity (the branch of computing science targeting efficient programs) has been done in this area, at least when compared to continuous geometry. This is thus a good occasion to invent new algorithms while proving their correctness in the rigorous style of the mathematics of program construction.