Student Presentations
As part of the required work for this course, each student needs to chose two articles, one from each group, study, present and be able to discuss them at a date to be announced. The articles are the follow:
Student presentations will take place at November, 25. Each presentation should not exceed 20 minutes and will be followed by 10 minutes of questions.
Group 1
1. Automata and Monadic second order logic
ALREADY TAKEN!
The Kleene-Büchi theorem states that a language L is definable in a certain monadic second order logic (MSO(<)) if and only if L is regular. Besides proving the decidability of a fragmente of MSO, this result is import because
it extends to several other kinds of automata.
Chapter: An Introduction to Finite Automata and their Connection to Logic, Section 1.3, 1.4.1-14.4 (pp. 14-25)
2. Büchi automata complementation
ALREADY TAKEN!
Contrary to the finite word case the complementation for (non-deterministic) Büchi automata is a very difficult problem, but it is essential in many model checking problems
Chapter in Automata Theory and its Applications, B. khoussainov and A. Nerode, pp 150-160. (Sec. 3.4-3.5)
3. Basis of Tree automata for ranked trees
ALREADY TAKEN!
Tree automata are automata that recognise trees instead of words. They have may applications in several areas of computer science.
Chapter "Basis on tree automata", Christof Loding. in "Modern applications on automata theory, Ed.D'Souza, Deepak.Shankar, P. pp 79-96 (focusing on ranked trees).
4. A Unified Construction of the Glushkov, Follow, and Antimirov Automata
"A number of different techniques have been introduced in the last few decades to create ε-free automata representing regular ex- pressions such as the Glushkov automata, follow automata, or Antimirov automata. This paper presents a simple and unified view of all these construction methods both for unweighted and weighted regular expres- sions. It describes simpler algorithms with time complexities at least as favorable as that of the best previously known techniques, and provides a concise proof of their correctness. Our algorithms are all based on two standard automata operations: epsilon-removal and minimization. This contrasts with the multitude of complicated and special-purpose tech- niques previously described in the literature, and makes it straightfor- ward to generalize these algorithms to the weighted case. In particular, we extend the definition and construction of follow automata to the case of weighted regular expressions over a closed semiring and present the first algorithm to compute weighted Antimirov automata."
5. Applications of Weighted Automata in Natural Language Processing
ALREADY TAKEN!
Only pages 571–596.
6. Linear Cellular Automata and the Garden-of-Eden
7. A secret sharing scheme based on cellular automata
A new secret sharing scheme based on a particular type of discrete delay dynamical systems: memory cellular automata, is proposed. Specifically, such scheme consists of a (k,n)-threshold scheme where the text to be shared is considered as one of the k initial conditions of the memory cellular automata and the n shares to be distributed are n con- secutive configurations of the evolution of such cellular automata. It is also proved to be perfect and ideal.
1. Automata and Monadic second order logic
ALREADY TAKEN!
The Kleene-Büchi theorem states that a language L is definable in a certain monadic second order logic (MSO(<)) if and only if L is regular. Besides proving the decidability of a fragmente of MSO, this result is import because
it extends to several other kinds of automata.
Chapter: An Introduction to Finite Automata and their Connection to Logic, Section 1.3, 1.4.1-14.4 (pp. 14-25)
2. Büchi automata complementation
ALREADY TAKEN!
Contrary to the finite word case the complementation for (non-deterministic) Büchi automata is a very difficult problem, but it is essential in many model checking problems
Chapter in Automata Theory and its Applications, B. khoussainov and A. Nerode, pp 150-160. (Sec. 3.4-3.5)
3. Basis of Tree automata for ranked trees
ALREADY TAKEN!
Tree automata are automata that recognise trees instead of words. They have may applications in several areas of computer science.
Chapter "Basis on tree automata", Christof Loding. in "Modern applications on automata theory, Ed.D'Souza, Deepak.Shankar, P. pp 79-96 (focusing on ranked trees).
4. A Unified Construction of the Glushkov, Follow, and Antimirov Automata
"A number of different techniques have been introduced in the last few decades to create ε-free automata representing regular ex- pressions such as the Glushkov automata, follow automata, or Antimirov automata. This paper presents a simple and unified view of all these construction methods both for unweighted and weighted regular expres- sions. It describes simpler algorithms with time complexities at least as favorable as that of the best previously known techniques, and provides a concise proof of their correctness. Our algorithms are all based on two standard automata operations: epsilon-removal and minimization. This contrasts with the multitude of complicated and special-purpose tech- niques previously described in the literature, and makes it straightfor- ward to generalize these algorithms to the weighted case. In particular, we extend the definition and construction of follow automata to the case of weighted regular expressions over a closed semiring and present the first algorithm to compute weighted Antimirov automata."
5. Applications of Weighted Automata in Natural Language Processing
ALREADY TAKEN!
Only pages 571–596.
6. Linear Cellular Automata and the Garden-of-Eden
7. A secret sharing scheme based on cellular automata
A new secret sharing scheme based on a particular type of discrete delay dynamical systems: memory cellular automata, is proposed. Specifically, such scheme consists of a (k,n)-threshold scheme where the text to be shared is considered as one of the k initial conditions of the memory cellular automata and the n shares to be distributed are n con- secutive configurations of the evolution of such cellular automata. It is also proved to be perfect and ideal.
Group 2
1. Testing the Equivalence of Regular Languages
ALREADY TAKEN!
"The minimal deterministic finite automaton is generally used to determine regular languages equality. Using Brzozowski’s notion of derivative, Antimirov and Mosses proposed a rewrite system for deciding regular expressions equivalence of which Almeida et al. presented an improved variant. Hopcroft and Karp proposed an almost linear algorithm for testing the equivalence of two deterministic finite automata that avoids minimisation. In this paper we improve this algorithm’s best-case running time, present an extension to non-deterministic finite automata, and establish a relationship with the one proposed in Almeida et al., for which we also exhibit an exponential lower bound. We also present some experimental comparative results."
2. Theory of Átomata
ALREADY TAKEN!
"Abstract. We show that every regular language defines a unique non- deterministic finite automaton (NFA), which we call “a ́tomaton”, whose states are the “atoms” of the language, that is, non-empty intersections of complemented or uncomplemented left quotients of the language. We describe methods of constructing the ́atomaton, and prove that it is iso- morphic to the normal automaton of Sengoku, and to an automaton of Matz and Potthoff. We study “atomic” NFA’s in which the right lan- guage of every state is a union of atoms. We generalize Brzozowski’s double-reversal method for minimizing a deterministic finite automaton (DFA), showing that the result of applying the subset construction to an NFA is a minimal DFA if and only if the reverse of the NFA is atomic."
3. An introduction to descriptional complexity of regular languages through analytic combinatorics.
"Nowadays, an increasing attention is being given to the study of the descriptional complexity on the average case. Although the underlying theory for such a study seems intimidating, one can obtain interesting results in this area without too much effort. In this gentle introduction we take the reader on a journey through the basic analytical tools of that theory, giving some illustrative examples using regular expressions. We finalize with some new asymptotic average case results for several ε-NFA constructions, presented in a unified framework."
4. Regular Expressions, au point
ALREADY TAKEN!
"We introduce a new technique for constructing a finite state deterministic automaton from a regular expression, based on the idea of marking a suitable set of positions inside the expression, intuitively representing the possible points reached after the processing of an initial prefix of the input string. Pointed regular expressions join the elegance and the symbolic appealingness of Brzozowski’s derivatives, with the effectiveness of McNaughton and Yamada’s labelling technique, essentially combining the best of the two approaches."
5. An Efficient Algorithm for Constructing Minimal Cover Automata for Finite Languages
ALREADY TAKEN!
"The concept of cover automata for finite languages was formally introduced in [3]. Cover automata have been studied as an efficient representation of finite languages. In [3], an algorithm was given to transform a DFA that accepts a finite language to a minimal deterministic finite cover automaton (DFCA) with the time complexity O(n4), where n is the number of states of the given DFA. In this paper, we review the basic concept of cover automata and describe a new efficient transformation algorithm with the time complexity O(n2), which is a significant improvement from the previous algorithm."
1. Testing the Equivalence of Regular Languages
ALREADY TAKEN!
"The minimal deterministic finite automaton is generally used to determine regular languages equality. Using Brzozowski’s notion of derivative, Antimirov and Mosses proposed a rewrite system for deciding regular expressions equivalence of which Almeida et al. presented an improved variant. Hopcroft and Karp proposed an almost linear algorithm for testing the equivalence of two deterministic finite automata that avoids minimisation. In this paper we improve this algorithm’s best-case running time, present an extension to non-deterministic finite automata, and establish a relationship with the one proposed in Almeida et al., for which we also exhibit an exponential lower bound. We also present some experimental comparative results."
2. Theory of Átomata
ALREADY TAKEN!
"Abstract. We show that every regular language defines a unique non- deterministic finite automaton (NFA), which we call “a ́tomaton”, whose states are the “atoms” of the language, that is, non-empty intersections of complemented or uncomplemented left quotients of the language. We describe methods of constructing the ́atomaton, and prove that it is iso- morphic to the normal automaton of Sengoku, and to an automaton of Matz and Potthoff. We study “atomic” NFA’s in which the right lan- guage of every state is a union of atoms. We generalize Brzozowski’s double-reversal method for minimizing a deterministic finite automaton (DFA), showing that the result of applying the subset construction to an NFA is a minimal DFA if and only if the reverse of the NFA is atomic."
3. An introduction to descriptional complexity of regular languages through analytic combinatorics.
"Nowadays, an increasing attention is being given to the study of the descriptional complexity on the average case. Although the underlying theory for such a study seems intimidating, one can obtain interesting results in this area without too much effort. In this gentle introduction we take the reader on a journey through the basic analytical tools of that theory, giving some illustrative examples using regular expressions. We finalize with some new asymptotic average case results for several ε-NFA constructions, presented in a unified framework."
4. Regular Expressions, au point
ALREADY TAKEN!
"We introduce a new technique for constructing a finite state deterministic automaton from a regular expression, based on the idea of marking a suitable set of positions inside the expression, intuitively representing the possible points reached after the processing of an initial prefix of the input string. Pointed regular expressions join the elegance and the symbolic appealingness of Brzozowski’s derivatives, with the effectiveness of McNaughton and Yamada’s labelling technique, essentially combining the best of the two approaches."
5. An Efficient Algorithm for Constructing Minimal Cover Automata for Finite Languages
ALREADY TAKEN!
"The concept of cover automata for finite languages was formally introduced in [3]. Cover automata have been studied as an efficient representation of finite languages. In [3], an algorithm was given to transform a DFA that accepts a finite language to a minimal deterministic finite cover automaton (DFCA) with the time complexity O(n4), where n is the number of states of the given DFA. In this paper, we review the basic concept of cover automata and describe a new efficient transformation algorithm with the time complexity O(n2), which is a significant improvement from the previous algorithm."