AL（Algorithm & Logic）セミナー

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


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

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

日時： 　10月21日（木）(21st October) 13:30 -- 16:30

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

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

講演題目： Many-dimensional logical systems

話題提供者： Agnes Kurucz (King's College London, UK)

概要： Many-dimensional logical systems are natural and clear formalisms
arising in both pure logic and numerous applications. We introduce
several different formalisms, and investigate their computational properties and
interconnections. Basic techniques and tools for dealing with axiomatisation,
decision and complexity problems of many-dimensional logical systems are
also presented.

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

講演題目： Spatio-temporal logics: expressiveness vs. complexity

話題提供者： Michael Zakharyaschev (King's College London, UK)

概要： We construct and investigate a hierarchy of spatio-temporal
formalisms that result from various combinations of propositional
spatial and temporal logics such as the propositional temporal logic
PTL, the spatial logics RCC-8, BRCC-8, S4u and their fragments. The
obtained results give a clear picture of the trade-off between
expressiveness and `computational realisability' within the hierarchy.
We demonstrate how different combining principles as well as spatial
and temporal primitives can produce NP-, PSPACE-, EXPSPACE-,
2EXPSPACE-complete, and even undecidable spatio-temporal logics
out of components that are at most NP- or PSPACE-complete.

===========================================================

今回の世話人： 小野寛晰

===========================================================

ALセミナーは JAIST の研究プロジェクト LCCC (Logic for Cognition,
Computation and Communication) の一環として開催されています。

JAIST への交通アクセスについては以下のホームページをご覧下さい。

http://www.jaist.ac.jp/~kouhou/General_info/access/access.html

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

〒923-1292 石川県 辰口町 旭台 1-1
北陸先端科学技術大学院大学（JAIST）

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