Student Talks in Computer Science

Where and when?	What?	Who?
Lecture Hall 5 9 September, 2019 5.00 pm	Timed Automata, Reachability and Diagonal Constraints In this talk, we will look into the model of Timed Automata, the problem of reachability and how we can check reachability in Timed Automata. After this, we will see what are diagonal constraints, how they are useful and why the off-the-shelf reachability algorithms cannot be used when diagonal constraints are present in the automaton. If time permits, we will discuss a few possible ways of dealing with diagonal constraints. Only knowing what are finite state automata and how they function would be sufficient to follow this talk.	Sayan Mukherjee
Lecture Hall 5 2 July, 2019 4.00 pm	Synchronizing words for Automata We need a 'reset' button when systems go crazy. I'll talk about how do we do that automata theoretically. No background is assumed apart from basic automata theory and graph theory.	Adwitee Roy
Lecture Hall 5 18 June, 2019 4.00 pm	Applications of Automata Theory to Non Commutative Arithmetic Circuits and Polynomial Identity Testing I will introduce Arithmetic Circuits and the various problems that arise in this subject. Then we shall move to the non-commutative setting and illustrate how automata theory can be used to address some of these problems. I shall introduce all the concepts required and the talk will be accessible to all. Knowledge of how to multiply matrices is needed.	Rajit Datta
Lecture Hall 5 14 June, 2019 4.00 pm	*Angluin's L algorithm** The setting for the problem is as follows - Teacher: Has a regular language L in mind. Learner: Wants to learn DFA for L by asking two types of queries: 1. Is a given string w ∈ L? Teacher answers “Yes” or “No”. 2. Does a given DFA A accept the language L? Teacher answers “Yes” or gives a counterexample x. Angluin's solution gives a polynomial time algorithm for the Learner.	R Keerthan

Where and when?

What?

Who?

Lecture Hall 5

9 September, 2019

5.00 pm

Timed Automata, Reachability and Diagonal Constraints

In this talk, we will look into the model of Timed Automata, the problem of reachability and how we can check reachability in Timed Automata. After this, we will see what are diagonal constraints, how they are useful and why the off-the-shelf reachability algorithms cannot be used when diagonal constraints are present in the automaton. If time permits, we will discuss a few possible ways of dealing with diagonal constraints.

Only knowing what are finite state automata and how they function would be sufficient to follow this talk.

Sayan Mukherjee

Lecture Hall 5

2 July, 2019

4.00 pm

Synchronizing words for Automata

We need a 'reset' button when systems go crazy. I'll talk about how do we do that automata theoretically. No background is assumed apart from basic automata theory and graph theory.

Adwitee Roy

Lecture Hall 5

18 June, 2019

4.00 pm

Applications of Automata Theory to Non Commutative Arithmetic Circuits and Polynomial Identity Testing

I will introduce Arithmetic Circuits and the various problems that arise in this subject. Then we shall move to the non-commutative setting and illustrate how automata theory can be used to address some of these problems.

I shall introduce all the concepts required and the talk will be accessible to all. Knowledge of how to multiply matrices is needed.

Rajit Datta

Lecture Hall 5

14 June, 2019

4.00 pm

Angluin's L* algorithm

The setting for the problem is as follows -

Teacher: Has a regular language L in mind.

Learner: Wants to learn DFA for L by asking two types of queries:

1. Is a given string w ∈ L? Teacher answers “Yes” or “No”.

2. Does a given DFA A accept the language L? Teacher answers “Yes” or gives a counterexample x.

Angluin's solution gives a polynomial time algorithm for the Learner.

R Keerthan