Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Simon Fraser University

$29,000.00

Computational Aspects of Reasoning about Dynamic Systems

EF 2024-25

Résumé
An important part of practical problems, and AI problems in particular, e.g. scheduling, diagnosis, planning and synthesis of reactive agents, are search problems. In many applications, some explicit data, that changes over time, is present. This setting is prevalent, e.g., in medical domains and in business process modelling. The data is, typically, large, and changes over time, and the problems are computationally hard. The representation of the problem must be such that reasoning algorithms could be executed efficiently with respect to the size of the data. In some applications, complexity of the algorithms may also depend on the size of the formula. An intriguing question is under what conditions on the specification language the problem definitely has an efficient algorithm. If the conditions are understood, then a specification language with a complexity guarantee can be developed. I plan to develop theoretical foundations and understand general principles, of the conditions for efficient computations. This foundational research will help us to develop practical algorithms. The algorithms will automate problem solving starting from a high-level specification written by the user, thus assisting in these intellectually challenging tasks. My research is about how to bridge the gap between user and advanced technology, and it is within the overall trend of replacing human services with exciting AI applications. The research leads towards making solving a large proportion of such problems accessible to a non-specialist user thus reducing the overall cost to the society and achieving a significant socio-economic benefit.
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2022-05453
Name nom
Ternovska, Evgenia
Department département
School of Computing Science
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2022
Award amount
29000
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
801
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
Computer software
Area of application fr
Logiciel
Research subject code
2803
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Knowledge representation
Research subject fr
Répresentation des connaissances
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
Computational Aspects of Reasoning about Dynamic Systems
Keywords
knowledge representation (kr); reasoning about actions; descriptive complexity (dc); dynamic logics; hanf locality; efficient reasoning; monadic second-order logic (mso); homomorphisms; synthesis of reactive ai agents; automata
Application summary
An important part of practical problems, and AI problems in particular, e.g. scheduling, diagnosis, planning and synthesis of reactive agents, are search problems. In many applications, some explicit data, that changes over time, is present. This setting is prevalent, e.g., in medical domains and in business process modelling. The data is, typically, large, and changes over time, and the problems are computationally hard. The representation of the problem must be such that reasoning algorithms could be executed efficiently with respect to the size of the data. In some applications, complexity of the algorithms may also depend on the size of the formula. An intriguing question is under what conditions on the specification language the problem definitely has an efficient algorithm. If the conditions are understood, then a specification language with a complexity guarantee can be developed. I plan to develop theoretical foundations and understand general principles, of the conditions for efficient computations. This foundational research will help us to develop practical algorithms. The algorithms will automate problem solving starting from a high-level specification written by the user, thus assisting in these intellectually challenging tasks. My research is about how to bridge the gap between user and advanced technology, and it is within the overall trend of replacing human services with exciting AI applications. The research leads towards making solving a large proportion of such problems accessible to a non-specialist user thus reducing the overall cost to the society and achieving a significant socio-economic benefit.