皆様
台湾 National Chung Cheng University のRen-June Wangさんの講演会のお知らせです。 どうぞふるってご参加ください。
問合せ先： 佐野勝彦 北陸先端科学技術大学院大学 情報科学系 e-mail: [email protected]
----------------------------------------------------------------- * JAIST Logic Seminar Series *
Date: Thursday, 7th July 2016, 15:30-17:00
Place: JAIST, IS school collaboration room 7, 5F (Access: http://www.jaist.ac.jp/english/top/access/index.html)
Speaker: Ren-June Wang (Department of Philosophy, National Chung Cheng University)
Title: Logical Omniscience and Deductive Rationality
Abstract: Epistemic logic as an important tool for reasoning about an intellectual agent’s epistemic states has long suffered from the so-called logical omniscience problem since the beginning of its introduction. The problem indicates an idealized assumption on the part of the agent presented by a formalism of such kind. Although alternative epistemic formalisms have been proposed for dealing with the problem, there is no sight of that the problem is settled. Thus in this talk I will try my hand firstly to give an analysis of the problem, hopefully to pin down the source of the problem, and accordingly provide an advice as to what is the right direction of solving the problem. At the end of the talk I will suggest that what we need is not a formalism with a machinery that can limit what is known by the agent, but one with more powerful expressivity such that the resource that an agent will consume in the course of his/her reasoning, such as the temporal duration, can be explicitly stated.
皆様
JAIST Logic Seminar Series のセミナー開催のお知らせを致します。 Ren-June Wang 教授の講演会に続きまして、7月12日(火) に Middeldorp 教授と Chen 教授の講演会を開催致します。 皆様のご参加をお待ち申し上げます。
廣川 直 (JAIST)
=========================================================================== JAIST Logic Seminar Series ===========================================================================
Date: July 12 (Tue) 14:00-16:45 Place: Collaboration Room 7 (I-56), JAIST Access: http://www.jaist.ac.jp/english/location/access.html
-*-*- first talk -*-*-
Prof. Aart Middeldorp (University of Innsbruck)
FORT 0.2: Confluence Properties on Open Terms in the First-Order Theory of Rewriting
Abstract: The first-order theory of rewriting is decidable for finite left-linear right-ground rewrite systems. The decision procedure for this theory is based on tree automata techniques and implemented in FORT. FORT offers the possibility to synthesize rewrite systems that satisfy properties that are expressible in the first-order theory of rewriting.
Tree automata operate on ground terms. Consequently, variables in formulas range over ground terms and hence the properties that FORT is able to decide are restricted to ground terms. Whereas for termination and normalization this makes no difference, for other properties it does, even for left-linear right-ground rewrite systems. This raises the question how one can use FORT to decide properties on open terms. We show that for properties related to confluence it suffices to add one or two fresh constants. We furthermore provide sufficient conditions which obviate the need for additional constants. These results have been implemented in FORT 0.2.
In the talk, which is based on joint work with Franziska Rapp, I will explain the decision and synthesis algorithms implemented in FORT, before discussing the new results for deciding properties on open terms. The talk is concluded with a comparison with AGCP, a tool developed by Aoto and Toyama for checking ground-confluence of many-sorted rewrite systems.
-*-*- second talk -*-*-
Prof. Yijia Chen (Fudan University, Shanghai)
Random Graphs, First-Order Logic, and AC^0 Circuits
Abstract: First-order logic (FO) has very limited expressive power. One of the best-known examples is its 0-1 law on random graphs. Among others, it implies that FO cannot express PARITY. However, once the graphs are ordered, the 0-1 law completely breaks down. Thus, to prove FO cannot define PARITY on ordered graphs, one uses the remarkable machinery of Hastad's Switching Lemma on AC^0 circuits.
In 2008, Rossman proved that the k-clique problem cannot be defined by FO using only k/4 variables, resolving a long-standing open problem in finite model theory and complexity theory. His proof is built on a brilliant application of Hastad's Switching Lemma on ordered random graphs.
In the talk, I will explain our recent work extending Rossman's result to the so-called planted clique conjecture. Among others, it shows that any super-constant clique cannot be characterized by FO, even in case that the given ordered graphs have a huge planted clique.
This is joint work with Joerg Flum (Freiburg)
-
Katsuhiko Sano -
Nao Hirokawa