IFIP Theoretical Computer Science 2012


Personal tools
From TCS 2012
Jump to: navigation, search


Detailed Program

The following individual talks are hyperlinked to their corresponding slides, if they have been sent in. If you would like for us to link to your slides, please send them to Frank de Boer.

Wednesday September 26

09.00-10.00 -- Invited Talk by Rajeev Alur: Streaming Transducers

Streaming transducers is an analyzable, executable, and expressive model for transforming strings as well as trees. The transducer makes a single left-to-right pass through the input, and computes the output in linear time using a finite-state control, a visibly-pushdown stack when the input is a tree, and a finite number of registers that store output chunks that can be combined using operations such as string-concatenation and tree-insertion. The expressiveness of streaming transducers coincides with the class of "regular" transductions that can be equivalently defined using monadic second-order logic. The problems of checking functional equivalence of two streaming transducers, and of checking whether a streaming transducer satisfies pre/post verification conditions are decidable. In this talk, we will survey the basic model, ongoing theoretical work such as the extension to infinite strings, applications to algorithmic verification of programs manipulating heap-allocated data, and open questions.

10.00-10.30 -- Break

10.30-12.00 -- Session I: Automata

12.00-13.30 -- Lunch

13.30-15.00 -- Session II: Logics

15.00-15.30 -- Break

15.30-16.30 -- Session III: Stochastic modelling

16.30-17.00 -- Break

17.00-18.00 -- Session IV: Formal languages

18.30 -- Reception

Thursday September 27

09.30-10.30 -- Invited Talk by Jiri Wiedermann: Computability and Non-Computability Issues in Amorphous Computing

Amorphous computing systems consist of a huge set of tiny simple stationary or mobile processors whose computational, communication and sensory part is reduced to an absolute minimum. In an airborne medium the processors communicate via a short-range radio while in a waterborne medium via molecular communication. In some cases the computational part of the processors can be simplified down to finite state automata or even combinatorial circuits and the system as a whole can still possess universal computational power with a high probability. We will argue that the amorphous systems belong among the simplest (non-uniform) universal computational devices. On the other hand, it is questionable as to what extent the standard universal models of computation can faithfully capture the behavior of amorphous computing systems whose functionality also depends on the non-computational and/or unpredictable operations of certain parts of the entire system.

10.30-11.00 -- Break

11.00-12.30 -- Session V: Complexity

12.30-14.00 -- Lunch

14.00-15.00 -- Session VI: Decidability

  • A context-free linear ordering with an undecidable first-order theory. Arnaud Carayol and Zoltan Esik
  • Unidirectional channel systems can be tested. Petr Jancar, Prateek Karandikar and Philippe Schnoebelen

15.00-15.30 -- Break

15.30-16.30 -- Session VII: Algorithms

16.30 -- Social event and dinner

Friday September 28

09.30-10.30 -- Invited Talk by Yuri Gurevich: Foundational Analyses of Computation

How can one possibly analyze computation in general? The task is daunting if not impossible. There are too many different kinds of computation, and the notion of general computation seems amorphous.

We review the celebrated Turing’s analysis of human computation, emphasising the fulcrum that enabled Turing to pull off the analysis, and pointing out some limitations of his analysis. We discuss whether one can carry a similar analysis of computation with physical devices. We finish with a review of our own analysis of sequential computation on an arbitrary abstraction level.

10.30-11.00 -- Break

11.00-12.30 -- Session VIII: Semantics I

12.30-14.00 -- Lunch

14.00-15.30 -- Session IX: Verification

15.30-16.00 -- Break

16.00-17.00 -- Session X: Semantics II

Program in Portable Format

We provide the conference program in three portable digital formats, powered by Google Calendar:

Keynote Speakers