Institute for Mathematical Sciences Event Archive
|
Online registration form
Application for financial support is closed. Enquiries |
|
Automata Theory and Applications
(1 - 30 September 2011)
Organizing Committee · Visitors and Participants · Overview · Activities · Venue · Funding for Students/Young Scientists
Chair
- Frank Stephan (National University of Singapore)
Members
- Sanjay Jain (National University of Singapore)
- Bakhadyr Khoussainov (University of Auckland)
- Oded Maler (CNRS Grenoble)
- Alexei Miasnikov (McGill University and Stevens Institute of Technology)
- P.S. Thiagarajan (National University of Singapore)
The IMS Programme “Automata Theory and Applications” is dedicated to one of the central areas of Theoretical Computer Science. The class of languages recognised by finite automata occupies the bottom level of the Chomsky hierarchy and is well-studied due to the good algorithmic properties of many tasks related to finite automata. This workshop deals with the following applications:
(1) Automatic structures. This is a setting in which not only the domain but also the relevant relations and functions of the structure are recognisable by a finite automaton. The importance of the field stems from the fact that the first-order theory of each automatic structure is decidable and that any function definable in the structure is automatic and linear-time computable.
(2) Automatic groups in the framework of Thurston. This field considers finitely generated groups which have a presentation in which the group multiplication with each generator is an automatic function, every group element has a representative and the word equivalence problem restricted to the set of representatives is automatic. The groups which satisfy these conditions include the free group of finitely many generators.
(3) Automata theory and genericity and randomness. Randomness and genericity have been fruitful and important topics studied in recursion and complexity theory so far; some of the approaches carry over to automata theory and this connection is part of this programme.
(4) Applications of automata theory in inductive inference. Inductive inference has recently been applied to study the learnability of classes which are defined using automatic structures; furthermore, it had been investigated under which circumstances one can take a learner to be automatic.
(5) Hybrid systems. The main idea of the setting is that an automaton with finite control interacts with an environment which is represented by finitely many real variables. These real variables update their value according to a differential equation depending on the state of the automaton. Some sensors monitor the development of the real variables and the automata updates at discrete times 0,1,2,3,... in dependence of its state and rounded versions of the values measured by the sensors. The work in this setting is quite comprehensive and the automata theoretic approach can be used to show decidability in some special but interesting cases.
The aim of the programme is to enhance research in the above 5 areas and to bring together researchers from the various specific fields of automata theory. In particular researchers from the two approaches to automatic group theory at (1) and (2) could come together in order to apply methods from one field to solve problems in the other field. Furthermore, area (4) is quite recent and has still many open problems which might be solved by people having a strong background in automata theory.
Informal discussions and seminars: 1 - 9 Sep 2011
Workshop on Automata Theory and its Applications: 12 - 16 Sep 2011
Informal discussions and seminars: 19 - 30 Sep 2011
Students and researchers who are interested in attending these activities and who do not require financial aid are requested to complete the online registration form.
The following do not need to register:
- Those invited to participate.
- Those applying for financial support.
The Institute for Mathematical Sciences has limited funds to cover partial support for travel and living expenses for students or young scientists interested in participating in the program. Applications should be received at least three (3) months before the commencement of the program.
For enquiries, please email us at ims(AT)nus.edu.sg.
For enquiries on scientific aspects of the program, please email Frank Stephan at fstephan(AT)comp.nus.edu.sg.
Organizing Committee · Visitors and Participants · Overview · Activities · Venue · Funding for Students/Young Scientists
