Contents |
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.
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
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
15.00-15.30 -- Break
15.30-16.30 -- Session VII: Algorithms
16.30 -- Social event and dinner
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
We provide the conference program in three portable digital formats, powered by Google Calendar: