Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

McGill University

$50,000.00

Reasoning About Probabilistic and Concurrent Systems

FY 2015-16

Summary
My primary focus is to develop techniques to approximate and reason about <span style=""line-height: 1.5em;"">continuous-state Markov decision processes. These models are central to <span style=""line-height: 1.5em;"">machine learning, embedded systems and to robotics. I <span style=""line-height: 1.5em;"">have developed, in the past, approximation schemes that construct a family <span style=""line-height: 1.5em;"">of finite-state Markov processes that approximate given continuous-state <span style=""line-height: 1.5em;"">Markov processes. I have also developed behavioural pseudo-metrics such <span style=""line-height: 1.5em;"">that when two processes are at zero distance they are bisimilar: no <span style=""line-height: 1.5em;"">observation will distinguish them. This work is well established by now and <span style=""line-height: 1.5em;"">lead to interesting theory but the metrics are expensive to compute. In <span style=""line-height: 1.5em;"">the coming period I wish to explore new ways of approximating the metrics <span style=""line-height: 1.5em;"">and indeed defining new metrics that also capture interesting notions of <span style=""line-height: 1.5em;"">behavioural similarity but are not so stringent and so expensive to <span style=""line-height: 1.5em;"">compute. The methodology that I exploit is to use duality theory. My collborators and I have discovered some striking consequences of  <span style=""line-height: 1.5em;"">duality. For example, Brzozowski's remarkable algorithm, from the 1960s, <span style=""line-height: 1.5em;"">for minimizing finite automata can be viewed as an instance of duality. <span style=""line-height: 1.5em;"">The point of this general view is that one is able to develop similar style <span style=""line-height: 1.5em;"">algorithms for the minimization of weighted and probabilistic automata. <span style=""line-height: 1.5em;"">Duality theorems also subsume completeness results in logic. For example, <span style=""line-height: 1.5em;"">the Stone duality theorem subsumes the completeness theorems for <span style=""line-height: 1.5em;"">propositional logic and generalizations by Jonsson and Tarski subsume modal <span style=""line-height: 1.5em;"">completeness theorems. In 2013 we discovered a striking Stone-type <span style=""line-height: 1.5em;"">duality for Markov processes. This opens the way to deepen our <span style=""line-height: 1.5em;"">understanding of quantitative logics (like probabilistic modal logics) for <span style=""line-height: 1.5em;"">reasoning about probabilistic systems. In the proposal I will discuss how <span style=""line-height: 1.5em;"">other dualities, like Gelfand duality or convex duality, could be used to <span style=""line-height: 1.5em;"">develop new minimization techniques and new approximation techniques for <span style=""line-height: 1.5em;"">weighted transition systems and for probabilistic systems like MDPs and <span style=""line-height: 1.5em;"">POMDPs.  I will also explore the fundamental theory of Markov processes with a view to developing techniques for large systems. The application areas are to machine learning where compressing decriptions  <span style=""line-height: 1.5em;"">of large systems is important and also in verification of probabilistic <span style=""line-height: 1.5em;"">systems where the known model-checking techniques developed for finite-state systems can be extended to <span style=""line-height: 1.5em;"">probabilistic systems defined on continuous state spaces.
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2015-05508
Name nom
Panangaden, Prakash
Department département
Computer Science, School of - Computer Science, School of
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2015
Award amount
50000
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
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
1
Nb partie
5
Application title
Reasoning About Probabilistic and Concurrent Systems
Keyword
NSERC
Application summary
<p>My primary focus is to develop techniques to approximate and reason about <span style=""line-height: 1.5em;"">continuous-state Markov decision processes. These models are central to </span><span style=""line-height: 1.5em;"">machine learning, embedded systems and to robotics. I </span><span style=""line-height: 1.5em;"">have developed, in the past, approximation schemes that construct a family </span><span style=""line-height: 1.5em;"">of finite-state Markov processes that approximate given continuous-state </span><span style=""line-height: 1.5em;"">Markov processes. I have also developed behavioural pseudo-metrics such </span><span style=""line-height: 1.5em;"">that when two processes are at zero distance they are bisimilar: no </span><span style=""line-height: 1.5em;"">observation will distinguish them. This work is well established by now and </span><span style=""line-height: 1.5em;"">lead to interesting theory but the metrics are expensive to compute. In </span><span style=""line-height: 1.5em;"">the coming period I wish to explore new ways of approximating the metrics </span><span style=""line-height: 1.5em;"">and indeed defining new metrics that also capture interesting notions of </span><span style=""line-height: 1.5em;"">behavioural similarity but are not so stringent and so expensive to </span><span style=""line-height: 1.5em;"">compute. The methodology that I exploit is to use duality theory.</span></p> <p>My collborators and I have discovered some striking consequences of  <span style=""line-height: 1.5em;"">duality. For example, Brzozowski's remarkable algorithm, from the 1960s, </span><span style=""line-height: 1.5em;"">for minimizing finite automata can be viewed as an instance of duality. </span><span style=""line-height: 1.5em;"">The point of this general view is that one is able to develop similar style </span><span style=""line-height: 1.5em;"">algorithms for the minimization of weighted and probabilistic automata. </span><span style=""line-height: 1.5em;"">Duality theorems also subsume completeness results in logic. For example, </span><span style=""line-height: 1.5em;"">the Stone duality theorem subsumes the completeness theorems for </span><span style=""line-height: 1.5em;"">propositional logic and generalizations by Jonsson and Tarski subsume modal </span><span style=""line-height: 1.5em;"">completeness theorems. In 2013 we discovered a striking Stone-type </span><span style=""line-height: 1.5em;"">duality for Markov processes. This opens the way to deepen our </span><span style=""line-height: 1.5em;"">understanding of quantitative logics (like probabilistic modal logics) for </span><span style=""line-height: 1.5em;"">reasoning about probabilistic systems. In the proposal I will discuss how </span><span style=""line-height: 1.5em;"">other dualities, like Gelfand duality or convex duality, could be used to </span><span style=""line-height: 1.5em;"">develop new minimization techniques and new approximation techniques for </span><span style=""line-height: 1.5em;"">weighted transition systems and for probabilistic systems like MDPs and </span><span style=""line-height: 1.5em;"">POMDPs.  I will also explore the fundamental theory of Markov processes with a view to developing techniques for large systems.</span></p> <p>The application areas are to machine learning where compressing decriptions  <span style=""line-height: 1.5em;"">of large systems is important and also in verification of probabilistic </span><span style=""line-height: 1.5em;"">systems where the known model-checking techniques developed for finite-state systems can be extended to </span><span style=""line-height: 1.5em;"">probabilistic systems defined on continuous state spaces.</span></p>