AL（Algorithm & Logic）セミナー

第 115回 ALセミナーのお知らせ

JAIST ではロジックを中心に情報科学の理論的な分野の話題をテーマ に して
ALセミナーを開催しています。興味をおもちの方はどなたでもフラリ と 気楽
におたちより下さい。
今回のセミナーは JAIST 情報科学研究科 COE Project: Verifiable and Evolvable
e-Society および JAIST 研究プロジェクト LCCC (Logic for Cognition,
Computation and Communication) の一環として開催されます。

********************************************************************

日時： 2006年10月10日（火）(10th October (Tue), 2006) 13:00 -- 15:00

場所： 情報科学研究科 III 棟 5 階 コラボ7室
School of Information Science, 3rd bldg. 5th floor, Collab. Room 7

-------------------------------------------------------

講演題目 (title)： A coalgebraic perspective on automata theory

話題提供者 (speaker)： Yde Venema (Univ. of Amsterdam, Institute for Logic, Language
and Computation)

There is a long tradition in theoretical computer science connecting logic and automata
theory. As paradigmatic examples we mention the seminal work of Buechi and Rabin
concerning the decidability of monadic second order logics, or the more recent work
linking the modal mu-calculus and to parity automata operating on graphs. In our talk
we will argue that many of the central results in this area of automata theory can be lifted
to a *coalgebraic* level of generality.
Coalgebras are state-based evolving systems, where typically, a `state of affairs' can be
observed and modified. Of key importance for such systems are the concept of behavior,
together with related notions such as invariance and observational (in)distinguishability.
The generality of the concept enables one to build into the type of a coalgebra many
different features like input, output, nondeterminism, probability distributions, etc.
Thus many fundamental phenomena in computer science (data streams, automata,
transition systems), logic (Kripke models and frames) and mathematics (non-well-founded
sets, power series) have in fact a very natural modelling as a state- based coalgebra.
This explains the emergence of Coalgebra as a general mathematical framework with
the potential of a deep unification of many concepts pertaining to evolving systems.
The talk will have two parts. We start with a gentle introduction to the theory of coalgebra,
concentrating on the concept of observational indistinguishability (or bisimulation). In the
second part of the talk we discuss the theory of automata operating on infinite trees (or
similar structures), and discuss how a coalgebraic perspective allows for uniform proofs
for many of the key results in the field, and (arguably) for simplification through conceptual
clarification.

[The talk does not presuppose any previous exposure to either coalgebra or automata
theory.]

-------------------------------------------------------------

なお、１１日（水）16:30 - 18:00 にも Yde Venema 氏に よる講演があります。
場所： 情報科学研究科 III 棟 5 階 コラボ6室
School of Information Science, 3rd bldg. 5th floor, Collab. Room 6

講演題目 (title)： MacNeille Completions of Lattice Expansions

話題提供者 (speaker)： Yde Venema (Univ. of Amsterdam, Institute for Logic, Language
and Computation)

Dedekind's construction of the reals as so-called cuts of the rationals, was generalized by
MacNeille to a method for embedding an arbitrary lattice into a complete lattice: its MacNeille
completion. There are two natural ways to extend this construction to maps between lattices,
yielding the upper and the lower MacNeille extension of a map.
We first discuss which properties of lattice maps are preserved under these constructions,
and for which kind of maps the two extensions coincide. Our perspective involves a number
of topologies on lattice completions, including the Scott topologies and topologies that are
induced by the original lattice. We provide a characterization of the MacNeille completion in
terms of these induced topologies.
We then turn to expansions of lattices with additional operations, addressing the question
which equational properties of such lattice expansions are preserved under various types of
MacNeille completions that can be defined for these algebras. For a number of cases, including
modal algebras and residuated (ortho)lattice expansions, we provide reasonably sharp sufficient
conditions on the syntactic shape of equations that guarantee preservation. Generally, our results
show that the more residuation properties the primitive operations satisfy, the more equations are
preserved.
Finally, we briefly compare the MacNeille completions to some other well-known kind of
completions such as the canonical extension. While these two kinds of completions are rather
different in nature, we point out some interesting connections.

The talk is based on joint work with Mai Gehrke, John Harding, and Mark Theunissen.

===========================================================
今回の世話人： 小野　寛晰
===========================================================


AL セミナーに関する一般的なお問い合わせは以下にどうぞ。

〒923-1292 石川県能美市 旭台 1-1　北陸先端科学 技術大学院大学（JAIST）

東条 敏 (tojo@jaist.ac.jp)
小野 寛晰 ( ono@jaist.ac.jp)