Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Waterloo

$24,000.00

Complexity Measures for Regular Languages

EF 2015-16

Résumé
Complexity is an important issue in Computer Science: How much time will it take to solve a problem, how much memory space? One would prefer a precise answer, but that is difficult to get. Lower and upper bounds are useful, and lower bounds are often difficult to find. I work on the complexity of problems in the simplest, most common formal model of a deterministic finite automaton (DFA), using the number of states of the DFA as a complexity measure. I study the complexity of operations on DFAs; this gives a lower bound on the time and space complexities of operations. A DFA M has a finite number of states and inputs;  the set of inputs is the alphabet A of M. A state is a value in a memory cell and an input, a letter of A, is an action by a user of the DFA. When a letter is applied to a DFA M in its present state, M moves to a next state. A sequence of letters is a word, and a set of words is a language. A DFA has an initial state, and a finite number of outputs; one output is associated with each state. The simplest model has only two outputs, ""yes"" and ""no"". If a word w is applied to a DFA in its initial state, the DFA reaches some state q at the end of w. If q has output ""yes"", w is accepted; otherwise it is rejected. The set of all words accepted by a DFA M is the language L(M) of M. Each DFA performs a specific task of accepting only a certain language. For two different tasks, DFAs M1 and M2, it may be necessary to satisfy the conditions of both tasks; then we need a DFA that accepts the intersection of L(M1) and L(M2). If we need to satisfy either M1 or M2, we need the union of L(M1) and L(M2). If we first have to satisfy M1 and then M2, we need the concatenation of L(M1) and L(M2), which consist of words composed of a word of L(M1) followed by a word of L(M2). The language of words constructed by concatenating any number of words of L(M1)  is called the star of the language. In some cases it is useful to store the words of a language in the reverse order; then we need reversal. A language is regular if it can be constructed from finite languages by using only union, concatenation and star; equivalently, if and only if it can be accepted by a DFA. The state complexity of a regular language is the number of states in the minimal DFA accepting that language. The state complexity of an operation is the maximal state complexity of the language resulting from the operation expressed as a function of the state complexities of the arguments. I study state complexity and related measures of complexity of regular languages.  Operations with more than one basic operation, e.g., the union of a language with the reverse of another language, are called combined operations. I hope to give implementers of operations on finite automata and regular languages not only a large catalog of known results, but also a theory -- firmly based on the theories of semigroups and groups -- which should permit them to more easily estimate the complexity of combined operations in the class of regular languages or one of its subclasses.
Programme
Discovery Grants Program - Individual
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2015-05399
Name nom
Brzozowski, Janusz
Department département
Computer Science, David R. Cheriton School of - Computer Science, David R. Cheri
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2015
Award amount
24000
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
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
Partie
1
Nb partie
5
Application title
Complexity Measures for Regular Languages
Keyword
NSERC
Application summary
<p>Complexity is an important issue in Computer Science: How much time will it take to solve a problem, how much memory space? One would prefer a precise answer, but that is difficult to get. Lower and upper bounds are useful, and lower bounds are often difficult to find. I work on the complexity of problems in the simplest, most common formal model of a deterministic finite automaton (DFA), using the number of states of the DFA as a complexity measure. I study the complexity of operations on DFAs; this gives a lower bound on the time and space complexities of operations.</p> <p><em>A DFA </em><em>M</em><em> </em>has a finite number of <em>states </em>and <em>inputs; </em> the set of inputs is the<em> alphabet</em> <em>A</em> of <em>M</em>. A state is a value in a memory cell and an input, a <em>letter of A,</em> is an action by a user of the DFA. When a letter is applied to a DFA <em>M</em> in its present state, <em>M</em> moves to a next state. A sequence of letters is a <em>word</em>, and a set of words is a <em>language</em>. A DFA has an <em>initial state</em>, and a finite number of <em>outputs</em>; one output is associated with each state. The simplest model has only two outputs, ""yes"" and ""no"". If a word <em>w</em> is applied to a DFA in its initial state, the DFA reaches some state <em>q</em> at the end of<em> w</em>. If <em>q</em> has output ""yes"", <em>w</em> is <em>accepted</em>; otherwise it is <em>rejected</em>. The set of all words accepted by a DFA <em>M</em> is the <em>language L(M)</em> of <em>M</em>. Each DFA performs a specific task of accepting only a certain language. </p> <p>For two different tasks, DFAs<em> M<sub>1</sub></em> and <em>M<sub>2</sub></em>, it may be necessary to satisfy the conditions of both tasks; then we need a DFA that accepts the <em>intersection</em> of <em>L(M<sub>1</sub>)</em> and <em>L(M<sub>2</sub>)</em>. If we need to satisfy either<em> M<sub>1</sub></em> or <em>M<sub>2</sub></em>, we need the <em>union</em> of <em>L(M<sub>1</sub>)</em> and <em>L(M<sub>2</sub>)</em>. If we first have to satisfy <em>M<sub>1</sub></em> and then <em>M<sub>2</sub></em>, we need the <em>concatenation</em> of <em>L(M<sub>1</sub>) </em>and<em> L(M</em><sub>2</sub>), which consist of words composed of a word of <em>L(M<sub>1</sub>) </em>followed by a word of <em>L(M<sub>2</sub>).</em> The language of words constructed by concatenating any number of words of <em>L(M<sub>1</sub>)</em>  is called the <em>star</em> of the language. In some cases it is useful to store the words of a language in the reverse order; then we need <em>reversal</em>.</p> <p>A language <em></em> is <em>regular</em> if it can be constructed from finite languages by using only union, concatenation and star; equivalently, if and only if it can be accepted by a DFA. The<em> state complexity </em>of a regular language is the number of states in the minimal DFA accepting that language. The state complexity of an operation is the maximal state complexity of the language resulting from the operation expressed as a function of the state complexities of the arguments. I study state complexity and related measures of complexity of regular languages.  Operations with more than one basic operation, e.g., the union of a language with the reverse of another language, are called <em>combined operations</em>. </p> <p>I hope to give implementers of operations on finite automata and regular languages not only a large catalog of known results, but also a theory -- firmly based on the theories of semigroups and groups -- which should permit them to more easily estimate the complexity of combined operations in the class of regular languages or one of its subclasses. </p> <p> </p> <p> </p> <p> </p>