[Apologies for multiple copies]

I am pleased to announce the 51th Tokyo Programming Seminar, which will be held at NII on June 21 (Tue).

Shin-ya Katsumata from Kyoto University will give a talk about a categorical approach to attribute grammars and Kazuyuki Asada from National Institute of Informatics will give a talk about bialgebraic semantics for multi-rooted graph algebra.

The programme is attached below. I'm looking forward to meeting you at ToPS.

Best regards, Kazuyuki Asada

----

The 51th ToPS http://www.ipl.t.u-tokyo.ac.jp/~tops/upcoming_seminar.html

Time: June 21th (Tue) 2011, 15:00--17:00 Place: Rm. 1208, 12F, National Institute of Informatics

Speaker:

(1) Kazuyuki Asada (National Institute of Informatics)

Title: Many-sorted Bialgebraic Semantics for a Multi-rooted Graph Algebra and a CBV Calculus

Abstract: In this talk, bialgebraic semantics for the graph algebra introduced by Buneman et al. is given. The graph algebra is a graph representation for some kind of multi-rooted graph, which is the same as Kripke model. First I give a bijective correspondence between graph algebras and terms in (the first-order part of) a call-by-value calculus equipped with output, non-termination, non-determinism, and iteration operator. Then I induce an equational theory for graph algebra from the standard one for the CBV calculus including (modified) uniformity for the iteration operator. Then, after reveiwing coalgebraic semantics for Kripke model, we see that those final coalgebras form a relative monad, and the graph algebra can be formulated as many-sorted algebra. Then I give many-sorted bialgebraic semantics for the graph algebra and the graph. Time permitting, I will explain three future works: Completeness of the equational theory, full-abstractness, and generalization.

(2) Shin-ya Katsumata (Kyoto University)

Title: A Categorical Approach to Attribute Grammars

Abstract: Attribute grammars (AGs) are a mechanism to assign computations with bidirectional information flow to trees. We introduce a categorical formulation of AGs called monoidal AGs, and demonstrate that they subsume existing formulations of AGs, such as domain-theoretic, graph-theoretic, and relational ones, and also a special class of syntactic AGs called SSUR-ACs. Using this categorical formulation, we give a syntax-free account of the descriptional composition, which is a method to fuse two term transformation algorithms described by SSUR-ACs into one.