Logic-ml

logic-ml@fos.kuis.kyoto-u.ac.jp

7 participants
1772 discussions

Talk by Prof. Sebastian Maneth
by Keisuke Nakano 18 May '17

18 May '17

皆様， (複数のメーリングリストに送信しています．重複して受信された場合はご容赦願います) 電気通信大学の中野と申します．来る5月26日(金)，ブレーメン大学のSebastian Maneth先生がご講演を行います．木トランスデューサ理論とその応用についてお話ししていただきますので，お時間のある方は是非ご参加ください．日時： 2017年5月26日(金) 15:00-17:00 場所：電気通信大学西9号館3階AVホール http://www.uec.ac.jp/about/profile/access/pdf/map.pdf 　　　 (こちらの地図の68番の建物です．地図にはありませんが68番の南側に　　　　門が設置されましたので，そちらをご利用されると便利です) 講演者：Prof. Sebastian Maneth (University of Bremen) タイトル：View-Query Determinacy for Tree Transducers 概要： This talk consists of two parts each with a duration of approximately 40 minutes. The first part focuses on the view-query determinacy problem. Given transformations v and q, the problem asks whether there exists a function f such that f(v(s))=q(s) for all possible inputs s. View-query determinacy is a strong static analysis with many important applications; for instance, it was used by Buneman, Davidson and Frey for data citation [CACM 59 (2016)]. For tree transducers, Hashimoto, Sawada, Ishihara, Seki, and Fujiwara showed in 2013 that determinacy is decidable for views realized by extended linear bottom-up tree transducers, and queries realized by single-valued bottom-up tree transducers. Their solution tests functionality of the inverse of the view composed with the query. We extend this result using known results about transducers and properties of uniformizers. A uniformizer of a relation R is a function that has the same domain as R. A query q is determined by a view v if and only if the composition v ; u ; q is equivalent to q, where u is a uniformizer of the inverse of v. Thus, our technique reduces the determinacy problem to the existence of uniformizers and to the decidability of equivalence. Henceforth, recent new results on decidability of equivalence immediately give rise to new results about determinacy. These results about transducer determinacy only work for views given by linear (extended) transducers. It is easy to see that even if a view transducer copies once, at the input root node, then determinacy becomes undecidable. This is unfortunate, because some very basic translations cannot be realized by linear transducers but require copying. Consider for instance a view that regroups a list of publications into sublists of books, articles, etc. A tree transducer realizing this view needs copying (i.e., it needs to process the original list multiple times). The issue that we cannot deal with non-linear views lead us to study transducers with origin (Part 2 of the talk). Under origin semantics, transducers that produce their output in "different ways" are considered different, even if they realize the same tree translation. Under this more rigid semantics, determinacy can be decided even for non-linear views. In particular, origin determinacy is decidable if the view and query are either both given by deterministic top-down tree transducers with look-ahead, or, if they are both given by deterministic MSO definable transducers. Intuitively, the world becomes safer with origin, but more restrictive (e.g., the query “is book X before article Y in the original list?” becomes determined under origin semantics). -- 中野圭介 <ksk(a)cs.uec.ac.jp> 電気通信大学大学院情報理工学研究科 http://millsmess.cs.uec.ac.jp/~ksk/

1 0

SLACS2017講演募集のお知らせ
by 安部達也 17 May '17

17 May '17

皆様（複数のメイリングリストに送信しています。重複して受信の際はご容赦ください。） SLACS 2017（記号論理と情報科学）幹事の千葉工業大学の安部達也です。今年度の講演募集を以下のとおり行います。ご検討よろしくお願いいたします。 SLACS 2017（記号論理と情報科学） http://super.para.media.kyoto-u.ac.jp/~abet/slacs2017/ 日時 2017年8月8日（火）から2017年8月9日（水）場所千葉県習志野市津田沼2-17-1 千葉工業大学津田沼キャンパス6号館3階633室参加費無料。ただし、懇親会（初日夕方に開催予定）費は別途徴収します。幹事千葉工業大学人工知能・ソフトウェア技術研究センター安部達也連絡先 abet(a)stair.center SLACSとは以下はSLACSのページの冒頭からの抜粋です。 http://www.math.s.chiba-u.ac.jp/SLACS/ 「SLACS（スラックス）は，記号論理学と情報科学の境界領域に関する研究発表・研究討論の場を提供することを目的にして開催されている研究集会です． 1985年1月に第１回が開催されて以来，毎年１回のペースで開催されています． SLACS は，堅苦しい研究会ではなく，その年の幹事を中心とした参加者自らの手作りによるフレンドリーな雰囲気を持った集会です．気軽に発表できる場ですから，研究が進行中の話題を持ってきて議論したり，学生さんが発表する場としても適当です．もちろん，発展を続けるこの分野の最先端の研究テーマに関する発表も数多く聞くことができます．参加者の資格は問いませんので，原則として，どなたでも講演発表・聴講いただけます．発表はごく少数の例外を除いて日本語です．」より詳しい情報はSLACSのページや最近の開催情報をご確認ください。 SLACS 2016 (名古屋大学) http://www.st.nanzan-u.ac.jp/info/sasaki/2016slacs/SLACS2016.html SLACS 2015 (南山大学) https://sites.google.com/site/ptslacs2015/ SLACS 2014 (東京工業大学) http://www.jaist.ac.jp/~y-keita/2014SLACS-NSA/ 講演・聴講・懇親会申込方法講演を希望される方は、幹事に連絡をお願いいたします。その際、以下について回答をお願いいたします。Subject を「SLACS2017講演申込」にしておいていただけるとありがたいです。講演申込期限は2017年7月31日としますが、講演する意思があるという方は早目にご連絡いただけると幸いです。 ----- 8< ----- 8< ----- 8< ----- 8< ----- 8< ----- 8< ----- 8< ----- 1. 氏名：（例）安部達也 2. 所属：（例）千葉工業大学人工知能・ソフトウェア技術研究センター 3. 区分：一般/学生 ← プログラム作成・懇親会費設定に利用する場合があります 4. 演題：（例）TBA 5. 懇親会：参加する/追って連絡する/参加できない 6. 要望等：（例）初日しか参加できませんので初日の枠に入れてください ----- 8< ----- 8< ----- 8< ----- 8< ----- 8< ----- 8< ----- 8< ----- 講演を伴わない聴講のみを希望される場合、事前連絡は不要です。当日、会場に直接お越しください。懇親会に参加を希望される方は、幹事に連絡をお願いいたします。その際、講演申込と同様のフォーマット（演題不要）での回答をお願いいたします。 Subject を「SLACS2017懇親会参加申込」にしておいていただけるとありがたいです。申込期限は2017年7月31日としますが、参加する意思があるという方は早目にご連絡いただけると幸いです。

1 0

JAIST Logic Seminar Series
by Takako Nemoto 15 May '17

15 May '17

皆様インスブリア大学（イタリア）の Marco Benini 先生の講演のお知らせです。どうぞふるってご参加ください。問い合わせ先：根元　多佳子北陸先端科学技術大学院大学　情報科学系 email: t-nemoto(a)jaist.ac.jp --------------------------------------------- *JAIST Logic Seminar Series* Date: Tuesday, 6 June, 2017, 15:30-17:00 Place: JAIST, Collaboration room 7 (I-56) (Access: http://www.jaist.ac.jp/english/location/access.html) Speaker: Marco Benini (Università degli Studi dell'Insubria) Title: The Graph Minor Theorem: a walk on the wild side of graphs Abstract: The Graph Minor Theorem says that the collection of finite graphs ordered by the minor relation is a well quasi order. This apparently innocent statement hides a monstrous proof: the original result by Robertson and Seymour is about 500 pages and twenty articles, in which a new and deep branch of Graph Theory has been developed. The theorem is famous and full of consequences both on the theoretical side of Mathematics and in applications, e.g., to Computer Science. But there is no concise proof available, although many attempts have been made. In this talk, arising from one such failed attempts, an analysis of the Graph Minor Theorem is presented. Why is it so hard? Assuming to use the by-now standard Nash-Williams's approach to prove it, we will illustrate a number of methods which allow to solve or circumvent some of the difficulties. Finally, we will show that the core of this line of thought lies in a coherence question which is common to many parts of Mathematics: elsewhere it has been solved, although we were unable to adapt those solutions to the present framework. So, there is hope for a short proof of the Graph Minor Theorem but it will not be elementary.

1 0

訃報：竹内外史先生
by Makoto Kikuchi 12 May '17

12 May '17

皆様，昨日，竹内外史先生がお亡くなりになられたそうです．菊池誠

2 1

ランダムネス集中講義
by Toshio Suzuki 28 Apr '17

28 Apr '17

ランダムネス集中講義のご案内（重複して受け取られた折はご容赦ください）お世話になっております。首都大学東京の鈴木登志雄です。さて５月・６月に首都大で，明治大学の宮部先生にランダムネスの集中講義をしていただきます。公式にオープンセミナーとうたっているわけではありませんが，当専攻ではこの種の集中講義に数名程度まで学外の院生等が聴きに来ても黙認する慣習のようです。お近くに関心のありそうな方がいらっしゃいましたら、お知らせいただければ幸いです。 %%%%%%% ここから＊＊担当者宮部賢志先生（明治大学理工学部講師）　＊＊授業科目名情報数理科学２ (博士前期課程、Ｒ０７９）、情報数理科学特論２(博士後期課程、Ｒ０８０）タイトルランダムネス入門場所　首都大学東京（南大沢キャンパス）８号館６階６１０時期５月１８日（木），５月２５日（木），６月　８日（木），６月１５日（木）の１４：４０−１７：５０（途中休憩あり）当専攻での連絡係鈴木登志雄 toshio-suzuki[atmark]tmu.ac.jp 概要アルゴリズム的ランダムネスの理論では，科学の基本概念であるランダムについて，計算論を使って厳密な定義を与え，その性質を調べる。本講義では，計算論の再帰定理やTuring次数などの概念の復習から始める。その後，MLランダムネスの定義といくつかの性質を見る。特に，ランダムな列の構成技術に焦点を当てて解説する。 %%%%%%% ここまで首都大学東京南大沢キャンパスへの交通 http://www.tmu.ac.jp/university/campus_guide/access.html 同・構内図 http://www.tmu.ac.jp/university/campus_guide/map.html -- 鈴木登志雄首都大学東京理工学研究科数理情報科学専攻 toshio-suzuki(a)tmu.ac.jp

1 0

早稲田大学高等研究所セミナー「Logic and Game Theory」 (5/16)のご案内
by Makoto Fujiwara 28 Apr '17

28 Apr '17

皆様 (English follows) 以下の通り、5/16(火)に金子守先生(早稲田大学政治経済学術院、特任教授)に非専門家向けのご講演(英語)をしていただきます。事前申込みは不要ですので、どうぞふるってご参加ください。詳細は下記ホームページをご覧ください。 https://www.waseda.jp/inst/wias/news/2017/04/25/4250/ <https://www.waseda.jp/inst/wias/news/2017/04/25/4250/> 問い合わせ先：藤原誠(早稲田大学高等研究所) makoto_fujiwara(a)aoni.waseda.jp <mailto:makoto_fujiwara@aoni.waseda.jp> Dear all, It is our pleasure to announce WIAS Seminar "Logic and Game Theory" (May 16, 2017). The talk by Professor Mamoru Kaneko and the following discussion would be held in English. It is free for charge and the prior registration for your attendance is not needed. You are welcome to join us. Best regards, Coordinators ================================================================== WIAS Seminar "Logic and Game Theory" Date & Time: Tuesday, 16 May 2017, 11:00 - 12:15 Venue: Meeting room. 1 on the 5th floor, Building #9, Waseda University Speaker: Mamoru KANEKO（Professor, Waseda University） Title: Logic and Game Theory Abstract: In this presentation, I make conceptual connections between logic and game theory. First, I give a small introduction to each filed. Then, a Japanese comic story called “Konnyaku Mondo” is introduced to describe a basic problem on one’s understanding about the other person’s thought. The Konnyaku Mondo phenomena are often observed in our real lives. It is indicative of the distinction between a symbolic expression and its intended meaning; this is a very basic distinction in the modern logic. The story leads also to a new field in game theory called “Inductive Game Theory” that I and several collaborators have developed. Indeed, we construct a game theory example having the feature of the Konnyaku Mondo that two players are playing a game with mutual misunderstanding of the situation, but they cannot correct their mutual misunderstanding even after they have played the game several times. Coordinators: Makoto FUJIWARA （Assistant Professor, Waseda University） Ryota AKIYOSHI （Associate Professor, Waseda University） Kazuto OHTSUKI （Assistant Professor, Waseda University） For more information, please see the following page: https://www.waseda.jp/inst/wias/news-en/2017/04/25/4251/ <https://www.waseda.jp/inst/wias/news-en/2017/04/25/4251/> Contact: Makoto FUJIWARA E-mail: makoto_fujiwara(a)aoni.waseda.jp <mailto:makoto_fujiwara@aoni.waseda.jp> ================================================================== ============================================ 藤原誠 (Makoto Fujiwara) 早稲田大学高等研究所 (Waseda Institute for Advanced Study, Waseda University) E-mail: makoto_fujiwara(a)aoni.waseda.jp ============================================

1 0

Project colloquium talk by Sean Sedwards on 28 April
by Akira Yoshimizu 27 Apr '17

27 Apr '17

Dear colleagues, (apology for multiple copies) Let us advertise the next ERATO MMSD project colloquium talk by Sean Sedwards. Please find the title and abstract of the talk below. You are all cordially invited. Remote attendance is also welcome (Polycom is available in the room). Please let us know beforehand if you would like to join remotely. Sincerely, Akira Yoshimizu Technical Assistant at ERATO MMSD project ---------- https://docs.google.com/document/d/1Qrg4c8XDkbO3tmns6tQwxn5lGHOrBON5LtHXXTp… <https://docs.google.com/document/d/1Qrg4c8XDkbO3tmns6tQwxn5lGHOrBON5LtHXXTp…> Fri 28 April 2017, 15:15–17:00 NII meeting room 2010 https://www.nii.ac.jp/en/about/access/ <https://www.nii.ac.jp/en/about/access/> Sean Sedwards (ERATO MMSD), Rare Event Simulation for Statistical Model Checking Statistical model checking (SMC) avoids the intractable number of states associated with numerical model checking by estimating the probability of a property from a number of execution traces (simulations). Rare events nevertheless pose an important challenge to SMC because interesting properties, such as bugs and optima, are often very rare and occur infrequently in simulations. A key objective for SMC is thus to reduce the number and length of simulations necessary to produce an estimate with a given level of statistical confidence. In this talk I will describe two variance reduction approaches that address this problem: importance sampling and importance splitting. Importance sampling weights the probabilities of a system to make a rare property occur more frequently in simulations, then compensates the results by the weights. Importance splitting decomposes a rare property into the product of sub-properties that are less rare and easier to simulate. I will outline the challenges of using these techniques in SMC and highlight some practical solutions, including the recent successful application of importance sampling to stochastic timed automata.

1 0

JAIST Logic Seminar Series
by Takako Nemoto 25 Apr '17

25 Apr '17

皆様インスブリア大学（イタリア）の Marco Benini 先生の講演のお知らせです。どうぞふるってご参加ください。問い合わせ先：根元　多佳子北陸先端科学技術大学院大学　情報科学系 email: t-nemoto(a)jaist.ac.jp --------------------------------------------- *JAIST Logic Seminar Series* Date: Friday, 12 May, 2017, 15:30-17:00 Place: JAIST, Collaboration room 7 (I-56) (Access: http://www.jaist.ac.jp/english/location/access.html) Speaker: Marco Benini (Università degli Studi dell'Insubria) Title: Explaining the Kruskal's Tree Theorem Abstract: The famous Kruskal's tree theorem states that the collection of finite trees labelled over a well quasi order and ordered by homeomorphic embedding, forms a well quasi order. Its intended mathematical meaning is that the collection of finite, connected and acyclic graphs labelled over a well quasi order is a well quasi order when it is ordered by the graph minor relation. Oppositely, the standard proof(s) shows the property to hold for trees in the Computer Science's sense together with an ad-hoc, inductive notion of embedding. The mathematical result follows as a consequence in a somewhat unsatisfactory way. In this talk, a variant of the standard proof will be illustrated explaining how the Computer Science and the graph-theoretical statements are strictly coupled, thus explaining why the double statement is justified and necessary.

1 0

国際会議 IWC 2017 (with FSCD at Oxford)
by Fujita Kenetsu 19 Apr '17

19 Apr '17

(* Apologies for any cross-postings. *) ===================================================================== Call for Papers IWC 2017 6th International Workshop on Confluence September 8th, 2017, Oxford, United Kingdom Collocated with FSCD 2017 http://cl-informatik.uibk.ac.at/events/iwc-2017/ ===================================================================== Confluence provides a general notion of determinism and is widely viewed as one of the central properties of rewriting. Confluence relates to many topics of rewriting (completion, modularity, termination, commutation, etc.) and has been investigated in many formalisms of rewriting such as first-order rewriting, lambda-calculi, higher-order rewriting, constrained rewriting, conditional rewriting, etc. Recently there is a renewed interest in confluence research, resulting in new techniques, tool support, certification as well as new applications. The International Workshop on Confluence (IWC) aims at promoting further research in confluence and related properties. IWC 2017 is collocated with FSCD 2017. Previous editions of the workshop were held in Nagoya (2012), Eindhoven (2013), Vienna (2014), Berlin (2015), and Obergurgl (2016). During the workshop, the 6th Confluence Competition (CoCo 2017) takes place. IMPORTANT DATES: * submission Saturday, July 1st, 2017 * notification Saturday, July 22nd, 2017 * final version Saturday, August 5th, 2017 * workshop Friday, September 8th, 2017 (deadlines are AoE) TOPICS: Specific topics of interest include: * confluence and related properties (unique normal forms, commutation, ground confluence) * completion * critical pair criteria * decidability issues * complexity issues * system descriptions * certification * applications of confluence INVITED SPEAKERS: tba PROGRAM COMMITTEE: * Beniamino Accattoli (INRIA) * Jörg Endrullis (Vrije Universiteit Amsterdam) * Bertram Felgenhauer (University of Innsbruck) * Ken-Etsu Fujita (Gumma University) * Philippe Malbos (Université Claude Bernard Lyon 1) * Jakob Grue Simonsen (University of Copenhagen) SUBMISSION: We solicit short papers or extended abstracts of at most five pages. There will be no formal reviewing. In particular, we welcome short versions of recently published articles and papers submitted elsewhere. The program committee checks relevance and may provide additional feedback. The accepted papers will be made available electronically before the workshop. The page limit for papers is 5 pages in EasyChair style. Short papers or extended abstracts must be submitted electronically through the EasyChair system at: https://www.easychair.org/conferences/?conf=iwc2017 EasyChair style: http://easychair.org/publications/for_authors -------

1 0

JAIST Logic Seminar Series
by Hajime Ishihara 16 Apr '17

16 Apr '17

皆様バーミンガム大学のSteve Vickers先生の講演のお知らせです。どうぞふるってご参加ください。問合せ先：石原　哉北陸先端科学技術大学院大学情報科学系 e-mail: ishihara(a)jaist.ac.jp ----------------------------------------------- * JAIST Logic Seminar Series * * The seminar below is held as a part of JSPS Core-to-Core Program, A. Advanced Research Networks, EU FP7 Marie Curie Actions IRSES project CORCON. (http://www.jaist.ac.jp/logic/ja/core2core, https://corcon.net/), and EU Horizon 2020 Marie Skłodowska-Curie actions RISE project CID. Date: Monday 17, April, 2017, 15:20-17:00 Place: JAIST, Collaboration room 6 (I-57g) (Access: http://www.jaist.ac.jp/english/location/access.html) Speaker: Steve Vickers (University of Birmingham) Title: Arithmetic universes as generalized point-free spaces Abstract: Point-free topology in all its guises (e.g. locales, formal topology) can be understood as presenting a space as a _logical theory_, for which the points are the models and the opens are the formulae. The logic in question is geometric logic, its connectives being finite conjunctions and arbitrary disjunctions, and then the Lindenbaum algebra (formulae modulo equivalence) for a theory T is a frame O[T], a complete lattice with binary meet distributing over all joins. Locales are frames but with the morphisms reversed. Grothendieck proposed Grothendieck toposes as the generalized point-free spaces got when one moves to the first-order form of geometric logic. Then the opens (giving truth values for each point) are not enough, and one must move to sheaves (giving sets for each point). The Lindenbaum algebra now becomes a Grothendieck topos Set[T], the classifying topos for T, constructed using presheaves with a pasting condition, and closed under finite limits and arbitrary colimits in accordance with Giraud's theorem. The topos Set[T] canonically represents the generalized space of models of T. Grothendieck used the category Set of classical sets, but we now know that it can be replaced by any elementary topos S. This base will determine the infinities available for "arbitrary" disjunctions, as well as governing the construction of the classifier S[T]. However, for theories in which all the disjunctions are countable (such as the formal space of reals) it doesn't matter which S is used, as long as it has a natural numbers object (nno). Thus the generalized space of models of T is not absolutely fixed as a mathematical object. In my talk I shall present the idea of using Joyal's _arithmetic universes_ (AUs), pretoposes with parameterized list objects, as a base-independent substitute for Grothendieck toposes in which countable disjunctions are intrinsic to the logic rather than being supplied extrinsically by a base S. In [1] I have defined a 2-category Con whose objects ("contexts") serve as geometric theories that are sufficiently countable in nature, and whose morphisms are the maps of models. In [2] I showed how to use Con to prove results for Grothendieck toposes, fibred over choice of base topos. Thus we start to see AUs providing a free-standing foundations for a significant fragment of geometric logic and Grothendieck toposes, independent of base S. My two papers - [1] "Sketches for arithmetic universes" (arXiv:1608.01559) [2] "Arithmetic universes and classifying toposes" (arXiv:1701.04611)

2 1

Jump to page:

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

Logic-ml