[logic-ml] The 51th ToPS [June 21]

[Kazuyuki ASADA]

[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.