Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Queen's University

$48,000.00

Descriptional Complexity and Applications of Formal Languages and Automata

EF 2024-25

Résumé
The work of the proposal focuses on the descriptional complexity of finite state machines and of their extensions. Finite state machines, or finite automata, are a fundamental computational model and a basis for the study of the theory of computation. Nondeterminism is a model of parallel computation that allows the machine to follow multiple transition paths simultaneously. Descriptional complexity studies the relative succinctness of different representations of formal languages. The size of finite automata is normally measured by the number of states. It is well known that, in the worst case, converting a nondeterministic finite automaton (NFA) into an equivalent deterministic machine results in an exponential size blow-up. In order to obtain a solid understanding of the power of nondeterministic computation, researchers have quantified nondeterminism as one more resource used by the machines. The amount of nondeterminism can be measured, among others, by counting the number of all computations or by counting the number of nondeterministic choices in the best accepting computation. Alternating finite automata (AFA) extend NFAs by allowing both existential (i.e., nondeterministic) and universal parallelism in a computation. A major direction of the proposed research deals with quantifying the parallelism of an AFA and investigating the state complexity trade-offs between machines employing different amounts of parallelism. Universal width counts the number of parallel branches in one computation of an AFA and existential width counts the number of existential choices encountered in a computation. An important goal of the research is to perform a state complexity comparison of AFAs having existential and universal width bounded by given constants and with (non)deterministic finite automata. The crucial task in state complexity research is to prove lower bounds and we need to develop specialized techniques for this purpose. Visibly pushdown automata, a.k.a. input-driven pushdown automata, are a much studied extension of finite state machines. Visibly pushdown automata are used in applications like XML document processing and program verification and the visibly pushdown languages retain many of the useful closure and decidability properties of the regular languages. An alternating visibly pushdown automaton has always an equivalent deterministic machine, however, the basic decision problems, such as language equality, are known to have higher complexity. I propose to study decision problems and state complexity of alternating visibly pushdown automata employing limited existential and universal parallelism. I expect that the research program will provide training each year for two PhD, two Master's and one undergraduate student. All the HQP trainees receive a thorough grounding in theory of computation and have in the past found employment both in academia and industry.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2024-05811
Name nom
Salomaa, Kai
Department département
School of Computing
Organization id
29
Institution établissement
Queen's University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
48000
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
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
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
Descriptional Complexity and Applications of Formal Languages and Automata
Keywords
finite state machines; state complexity; nondeterminism and alternation; visibly pushdown automata; algorithmic complexity; decidability and undecidability
Application summary
The work of the proposal focuses on the descriptional complexity of finite state machines and of their extensions. Finite state machines, or finite automata, are a fundamental computational model and a basis for the study of the theory of computation. Nondeterminism is a model of parallel computation that allows the machine to follow multiple transition paths simultaneously. Descriptional complexity studies the relative succinctness of different representations of formal languages. The size of finite automata is normally measured by the number of states. It is well known that, in the worst case, converting a nondeterministic finite automaton (NFA) into an equivalent deterministic machine results in an exponential size blow-up. In order to obtain a solid understanding of the power of nondeterministic computation, researchers have quantified nondeterminism as one more resource used by the machines. The amount of nondeterminism can be measured, among others, by counting the number of all computations or by counting the number of nondeterministic choices in the best accepting computation. Alternating finite automata (AFA) extend NFAs by allowing both existential (i.e., nondeterministic) and universal parallelism in a computation. A major direction of the proposed research deals with quantifying the parallelism of an AFA and investigating the state complexity trade-offs between machines employing different amounts of parallelism. Universal width counts the number of parallel branches in one computation of an AFA and existential width counts the number of existential choices encountered in a computation. An important goal of the research is to perform a state complexity comparison of AFAs having existential and universal width bounded by given constants and with (non)deterministic finite automata. The crucial task in state complexity research is to prove lower bounds and we need to develop specialized techniques for this purpose. Visibly pushdown automata, a.k.a. input-driven pushdown automata, are a much studied extension of finite state machines. Visibly pushdown automata are used in applications like XML document processing and program verification and the visibly pushdown languages retain many of the useful closure and decidability properties of the regular languages. An alternating visibly pushdown automaton has always an equivalent deterministic machine, however, the basic decision problems, such as language equality, are known to have higher complexity. I propose to study decision problems and state complexity of alternating visibly pushdown automata employing limited existential and universal parallelism. I expect that the research program will provide training each year for two PhD, two Master's and one undergraduate student. All the HQP trainees receive a thorough grounding in theory of computation and have in the past found employment both in academia and industry.