AL（Algorithm & Logic）セミナー

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

JAIST ではロジックを中心に情報科学の理論的な分野の話題をテーマにして
ALセミナーを開催しています。興味をおもちの方はどなたでもフラリと気楽
におたちより下さい。

今回のセミナーは JAIST 情報科学研究科 COE Project: Verifiable and
Evolvable e-Society および JAIST 研究プロジェクト LCCC (Logic for Cognition,
Computation and Communication) の一環として開催されます。

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

日時： 　5月31日（火）(31st May) 14:00 -- 15:00

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

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

講演題目： Temporal Logic over transitive states

話題提供者： Frank Wolter (Dept. of Computer Science, Univ. of Liverpool)

概要：
Temporal logics are used in computer science and artificial
intelligence to model states (of soft or hardware, data or knowledge
bases, spatial regions, multi-agent systems, etc.) changing over
time. Propositional temporal logics like LTL are usually decidable
in PSpace and reasoning in these logics can be mechanized using
tableaux or resolution methods. However, propositional temporal
logics are only capable of reasoning about states of fixed finite
size which must be known in advance. This limits the scope of
applications in areas where infinite or arbitrarily finite states
are required.

In this talk, we present recent results about the computational
behaviour of temporal logics over infinite and arbitrarily finite
states which contain transitive relations. Such logics are important
for representing temporal knowledge bases and topological dynamical
systems. We show that reasoning in these logics is highly
undecidable under the constant domain assumption while they often
behave better under the expanding domain assumption (which, in
dynamic topological systems, reflects the difference between
homeomorphisms and continuous mappings). The proofs are based on
applications of Kruskal's tree theorem and reductions of
reachability problems for channel systems.

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

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

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

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