Automatic Presentations of Graphs and Numbers

The Institute of Mathematical Sciences

presents

Automatic Presentations of Graphs and Numbers

A One Day Workshop

Venue: Alladi Ramakrishnan Hall, Institute of Mathematical Sciences, Chennai.

Date and Time: 11 October 2016, 9:30 -- 16:30

What is the workshop about?

To present an infinite graph, one can use grammars or automata. For example, the infinite transition system of configurations of a pushdown automaton can be represented by the pushdown automaton itself, or by a graph grammar. This can be generalized to transition systems of higher-order pushdown automata, which use stacks of stacks of ...stacks, rather than just ordinary stacks.

To present a real number R, say between 0 and 1, one can again use grammars or automata of different kinds. For example, the automaton takes as input a word which represents a number N (in some predetermined base); if the automaton accepts the word representing N then the Nth bit of R is 1, and if it rejects the word representing N then the Nth bit of R is 0.

Can one have interesting algorithms which work with these representations? What kinds of graphs or numbers are representable? Can one directly work with logics which express properties of graphs, or of relationships between graphs?

List of Speakers

Travel for the international visitors is provided by project PANO, Région Réunion.

Didier Caucal, University of Paris-Est Marne-la-Vallée, France
Christian Delhommé, University of La Réunion, France
Marion Le Gonidec, University of La Réunion, France
Alexandre Mansard, University of La Réunion, France
Antoine Meyer, University of Paris-Est Marne-la-Vallée, France
T.S. Ramanathan, IMSc Chennai
Purusottam Rath, Chennai Mathematical Institute
Vikram Sharma, IMSc Chennai

Schedule

9.30: Christian Delhommé, Automatic structures and graphs
10.00: Antoine Meyer, Finite set interpretations and 2-automatic graphs
10.30: Alexandre Mansard, Unfolding of finite concurrent systems
break
11.30: Didier Caucal, Hierarchy of pushdown graphs
12.30: T.S. Ramanathan, Theories of graph orderings
break
14.00: Vikram Sharma, Introduction to automatic numbers
14.30: Purusottam Rath, Transcendence of automatic numbers
break
15.30: Marion Le Gonidec, Transcendence of Context-free automatic numbers

Registration for the workshop is closed. Lunch, tea/coffee will be provided. Participants have to make their own arrangements for travel. For any information please send an email to Vikram Sharma or Kamal Lodaya.