皆様,
名古屋大学の木原貴行です.この度,UC BerkeleyのAntonio Montalban氏の日本訪問の折に,下記の要領で名古屋ロジックセミナーを開催することとなりました.多数のご参加をお待ちしております.
名古屋ロジックセミナー
http://www.math.mi.i.nagoya-u.ac.jp/~kihara/logic-seminar.html
日時:6月12日 (月) 15:00〜
場所:名古屋大学大学院情報学研究科棟 322号室
講演者:Antonio Montalbán (カリフォルニア大学バークレー校)
題目:A classification of the natural many-one degrees
アブストラクト:
A common phenomenon in mathematics is that naturally-occurring objects behave better than general objects. This is definitely the case of the many-one degrees within Computability Theory. Our theorem, in a sense, completely classifies the natural many-one degrees and sets them apart from the non-natural ones. The theorem is a version of the uniform Martin's conjecture, but for the case of the many-one degrees.
講演終了後に夕食会を予定しています.夕食会にご参加いただける方は木原貴行 kihara(a)i.nagoya-u.ac.jp <mailto:kihara@i.nagoya-u.ac.jp> までご一報お願い致します.
--------
Takayuki Kihara
Graduate School of Informatics, Nagoya University, Japan
URL: http://math.mi.i.nagoya-u.ac.jp/~kihara/
Email: kihara(a)i.nagoya-u.ac.jp
FIRST CALL FOR PAPERS
Symposium on LOGICAL FOUNDATIONS OF COMPUTER SCIENCE (LFCS '18),
Deerfield Beach, Florida, January 8-11, 2018.
LFCS GENERAL CHAIR: Anil Nerode.
LFCS STEERING COMMITTEE: Anil Nerode, (Ithaca); Stephen Cook (Toronto);
Dirk van Dalen (Utrecht); Yuri Matiyasevich (St. Petersburg); Samuel
Buss (San Diego); Gerald Sacks (Cambridge, MA); Dana Scott, (Pittsburgh,
PA - Berkeley, CA).
LFCS ’18 PROGRAM COMMITTEE: Sergei Artemov (New York, NY) - PC Chair;
Eugene Asarin (Paris); Steve Awodey (Pittsburgh, PA); Matthias Baaz
(Vienna); Lev Beklemishev (Moscow); Andreas Blass (Ann Arbor, MI);
Samuel Buss (San Diego, CA); Robert Constable (Ithaca, NY); Thierry
Coquand (Göteborg); Michael Fellows (Bergen), Melvin Fitting (New York);
Sergey Goncharov (Novosibirsk); Denis Hirschfeldt (Chicago, IL); Martin
Hyland (Cambridge); Rosalie Iemhoff (Utrecht); Hajime Ishihara (JAIST -
Kanazawa); Bakhadyr Khoussainov (Auckland); Roman Kuznets (Vienna);
Daniel Leivant (Bloomington, IN); Robert Lubarsky (Boca Raton, FL);
Victor Marek (Lexington, KY); Lawrence Moss (Bloomington, IN); Anil
Nerode (Ithaca, NY) - General LFCS Chair; Hiroakira Ono (JAIST -
Kanazawa); Alessandra Palmigiano (Delft); Ramaswamy Ramanujam (Chennai);
Michael Rathjen (Leeds); Jeffrey Remmel (San Diego); Andre Scedrov
(UPenn); Helmut Schwichtenberg (Munich); Philip Scott (Ottawa); Alex
Simpson (Ljubljana); Sonja Smets (Amsterdam); Sebastiaan Terwijn(Nijmegen).
LFCS ’18 LOCAL ORGANIZING COMMITTEE CHAIR: Robert Lubarsky.
LFCS TOPICS of interest include, but are not limited to: constructive
mathematics and type theory; homotopy type theory; logic, automata, and
automatic structures; computability and randomness; logical foundations
of programming; logical aspects of computational complexity;
parameterized complexity; logic programming and constraints; automated
deduction and interactive theorem proving; logical methods in protocol
and program verification; logical methods in program specification and
extraction; domain theory logics; logical foundations of database
theory; equational logic and term rewriting; lambda and combinatory
calculi; categorical logic and topological semantics; linear logic;
epistemic and temporal logics; intelligent and multiple agent system
logics; logics of proof and justification; nonmonotonic reasoning; logic
in game theory and social software; logic of hybrid systems; distributed
system logics; mathematical fuzzy logic; system design logics; other
logics in computer science.
SUBMISSION DETAILS. Proceedings will be published in the Springer LNCS
series. There will be a post-conference volume of selected works
published. Submissions should be made electronically via
http://www.easychair.org/LFCS18/. Submitted papers must be in pdf/12pt
format and of no more than 15 pages, present work not previously
published, and must not be submitted concurrently to another conference
with refereed proceedings.
LFCS issues the BEST STUDENT PAPER AWARD named after John Barkley Rosser
Sr. (1907-1989), a prominent American logician with fundamental
contributions in both Mathematics and Computer Science.
IMPORTANT DATES. Submissions deadline: September 10, 2017, any time
zone. Notification: October 10, 2017.
LOCAL ARRANGEMENTS. The venue of LFCS ’18 will be the spectacular
Wyndham Deerfield Beach Resort, 2096 NE 2nd Street, Deerfield Beach,
Florida 33441. Website: http://www.wyndhamdeerfieldresort.com
Further Information about LFCS symposia: http://lfcs.ws.gc.cuny.edu/
About LFCS.
The LFCS series provides an outlet for the fast-growing body of work in
the logical foundations of computer science, e.g., areas of fundamental
theoretical logic related to computer science. The LFCS series began
with Logic at Botik, Pereslavl-Zalessky, 1989 and was co-organized by
Albert R. Meyer (MIT) and Michael Taitslin (Tver), after which
organization passed to Anil Nerode in 1992. LFCS has enjoyed support and
endorsements from a number of bodies, including the US National Science
Foundation (NSF) and the City University of New York Research Foundation.
皆様,
(複数のメーリングリストに送信しています.重複して受信された場合はご容赦願います)
電気通信大学の中野と申します.
来る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/
皆様
インスブリア大学(イタリア)の 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.