Logic-ml

9 participants
1781 discussions

Nagoya logic seminar
by 吉信康夫 22 Oct '19

22 Oct '19

皆様：名古屋大学の吉信です。以下の要領で名古屋ロジックセミナーを開催します。日時：10月26日(金) 15:30〜場所：名古屋大学大学院情報学研究科棟2階206室講演者：宮元忠敏(南山大学) タイトル：A note on a countable fast function, its forcing axiom, and a weak tail club guessing アブストラクト： The countable fast function poset is strongly sigma-closed but does not have a usual chain condition. It forces a closed and cofinal subset of the second uncountable cardinal. Therefore its forcing axiom that takes care of appropriate number of dense sets kills a weak tail club guessing. This weak club guessing is a consequence of a tiny fragment of GCH. We discuss a consistency of the forcing axiom together with CH. We use an Aspero-Mota type iterated forcing with countable symmetric systems of sigma-closed uncountabe elementary substructres of relevant expanding relational structures on a fixed trasitive set universe of a large fragment of set theory. We also dicuss a class of posets that includes this poset and posts with stronger forms of relevant chain condition. 名古屋ロジックセミナーについてはセミナーのページをごらんください。 http://www.math.mi.i.nagoya-u.ac.jp/~kihara/logic-seminar.html 多数の方のご参加をお待ちしております。

1 0

Talk by Alex Kavvos (October 17th, 11.00-)
by Kazushige TERUI 15 Oct '19

15 Oct '19

みなさま今週木曜日に京都大学にてAlex Kavvosさんによるご講演があります。詳細は下記の通りです。よろしければぜひご参加ください。京都大学数理解析研究所照井一成 ========== Time: 11:00-12:00, October 17th, 2019 Place: Rm 478, Research Building 2, Main Campus, Kyoto University 京都大学本部構内総合研究2号館 4階478号室 http://www.kyoto-u.ac.jp/en/access/yoshida/main.html (Building 34) Speaker: Alex Kavvos (Aarhus University) Title: Modalities, Cohesion, and Information Flow Abstract: It is informally understood that the purpose of modal type constructors in programming calculi is to control the flow of information between types. I will introduce a number of such constructors that are useful for security-aware functional programming, i.e. for writing programs without accidental high-level leaks of information flow. Following that, I will prove that the well-typed programs in calculi of this sort preserve confidentiality and integrity by design, by using some categorical algebra and a few background ideas from topology. (This talk is based on arXiv:1809.07897.)

1 0

数学基礎論若手の会2019のご案内
by Takayuki Kihara 14 Oct '19

14 Oct '19

logic-mlの皆様，お世話になっております．名古屋大学の木原貴行です． 2019年度の数学基礎論若手の会のご案内をさせていただきます．数学基礎論若手の会は，数学基礎論を専攻する学生および若手研究者の研究交流を目的とする合宿形式の研究集会です．講演はオリジナルの成果発表に限らず，研究の途中報告や研究内容の紹介など幅広く募集しております．また，これから数学基礎論を勉強したいと思っている方のご参加も歓迎します．多くの方々のご参加およびご講演をお待ちしています．日時: 2019年12月6日 (金) 午後〜 12月8日 (日) 午前場所: 愛知県青年の家住所: 〒444-0802 愛知県岡崎市美合町並松1-2 世話人: 木原貴行 (名古屋大学) 連絡先: kihara(a)i.nagoya-u.ac.jp ウェブページ: http://www.math.mi.i.nagoya-u.ac.jp/~kihara/wakate2019.html 申し込み締め切り: 10月20日 (日) 参加費用フル参加 (2泊3日): 7,000円前後 (宿泊費・食費込) 部分参加の場合，宿泊日数や食事を取られる回数に応じて減額いたしますので，お問い合わせください．参加を希望の方は下記の情報を書いたメールを　　件名：数学基礎論若手の会参加申込にて kihara(a)i.nagoya-u.ac.jp までお送りください： —————————————————————————— 　所属大学，学部，立場（修士1年，博士2年，社会人、ポスドク，助教など）　氏名，性別　講演希望するorしない（講演希望の場合、後日題目と概要をお送りください）　6日の宿泊を希望するorしない　7日の宿泊を希望するorしない　6日の夕食を希望するorしない　7日の朝食を希望するorしない　7日の昼食を希望するorしない　7日の夕食を希望するorしない　8日の朝食を希望するorしない　8日の昼食を希望するorしない　その他（質問、講演希望日など） —————————————————————————— 以上よろしくお願い致します． -------- 木原貴行名古屋大学大学院情報学研究科数理情報学専攻 URL: http://math.mi.i.nagoya-u.ac.jp/~kihara/index-j.html Email: kihara(a)i.nagoya-u.ac.jp

1 1

27th WoLLIC 2020 (Lima, Peru) - 1st Call for Papers
by 小野寛晰 10 Oct '19

10 Oct '19

CALL FOR PAPERS WoLLIC 2020 27th Workshop on Logic, Language, Information and Computation August 4th to 7th, 2020 Lima, Peru ORGANISATION Universidad de Ingenieria y Tecnologia, Lima, Peru Centro de Informática, Universidade Federal de Pernambuco, Brazil CALL FOR PAPERS WoLLIC is an annual international forum on inter-disciplinary research involving formal logic, computing and programming theory, and natural language and reasoning. Each meeting includes invited talks and tutorials as well as contributed papers. The twenty-seventh WoLLIC will be held at Universidad de Ingenieria y Tecnologia, Lima, Peru from August 4th to 7th, 2020. It is scientifically sponsored by the Association for Symbolic Logic (ASL), the Interest Group in Pure and Applied Logics (IGPL), the The Association for Logic, Language and Information (FoLLI), the European Association for Theoretical Computer Science (EATCS), ACM Special Interest Group on Logic and Computation (ACM-SIGLOG) (TBC), the Sociedade Brasileira de Computação (SBC), and the Sociedade Brasileira de Lógica (SBL). PAPER SUBMISSION Contributions are invited on all pertinent subjects, with particular interest in cross-disciplinary topics. Typical but not exclusive areas of interest are: foundations of computing and programming; novel computation models and paradigms; broad notions of proof and belief; proof mining, type theory, effective learnability; formal methods in software and hardware development; logical approach to natural language and reasoning; logics of programs, actions and resources; foundational aspects of information organization, search, flow, sharing, and protection; foundations of mathematics; philosophy of mathematics; philosophical logic; philosophy of language. Proposed contributions should be in English, and consist of a scholarly exposition accessible to the non-specialist, including motivation, background, and comparison with related works. Articles should be written in the LaTeX format of LNCS by Springer (see authors instructions at http://www.springer.com/computer/lncs?SGWID=0-164-6-793341-0 <http://www.springer.com/computer/lncs?SGWID=0-164-6-793341-0>). They must not exceed 12 pages, with up to 5 additional pages for references and technical appendices. The paper's main results must not be published or submitted for publication in refereed venues, including journals and other scientific meetings. It is expected that each accepted paper be presented at the meeting by one of its authors. (At least one author is required to pay the registration fee before granting that the paper will be published in the proceedings.) Papers must be submitted electronically at the WoLLIC 2020 EasyChair website. (Please go to http://wollic.org/wollic2020/instructions.html <http://wollic.org/wollic2020/instructions.html> for instructions.) PROCEEDINGS The proceedings of WoLLIC 2020, including both invited and contributed papers, will be published in advance of the meeting as a volume in Springer's LNCS series. In addition, abstracts will be published in the Conference Report section of the Logic Journal of the IGPL, and selected contributions will be published (after a new round of reviewing) as a special post-conference WoLLIC 2020 issue of a scientific journal (to be confirmed). INVITED SPEAKERS (tba) STUDENT GRANTS ASL sponsorship of WoLLIC 2020 will permit ASL student members to apply for a limited travel grant (deadline: 90 days before the event starts). Visit https://aslonline.org/meetings/student-travel-awards/ <https://aslonline.org/meetings/student-travel-awards/> for details. IMPORTANT DATES April 15, 2020: Full paper deadline May 23, 2020: Author notification May 30, 2019: Final version deadline (firm) PROGRAMME COMMITTEE Carlos Areces (Cordoba, Argentina) Arthur Amorim Azevedo (CMU, USA) Paul Brunet (UCL, UK) Nina Gierasimczuk (Technical University of Denmark, Denmark) Helle Hansen (TU Delft, The Netherlands) Justin Hsu (University of Wisconsin–Madison, USA) Fairouz Kamareddine (Heriot-Watt University, UK) Sandra Kiefer (Aachen University, Germany) Clemens Kupke (Strathclyde University, Scotland) Konstantinos Mamouras (Rice University, USA) Maria Vanina Martinez (Universidad de Buenos Aires, Argentina) Larry Moss (Indiana Univ, USA) Claudia Nalon (University of Brasília, Brazil) Valeria de Paiva (Samsung Research, USA) Elaine Pimentel (UFRN, Brazil) Revantha Ramanayake (TU Wien, Austria) Jurriaan Rot (Radboud University, The Netherlands) Yamilet Serrano (UTEC, Peru) Alexandra Silva (Univ College London) (Co-Chair) Christine Tasson (IRIF, France) Sebastiaan Terwijn (Radboud University, The Netherlands) Renata Wassermann (Univ São Paulo) (Co-Chair) STEERING COMMITTEE Samson Abramsky, Anuj Dawar, Juliette Kennedy, Ulrich Kohlenbach, Daniel Leivant, Leonid Libkin, Lawrence Moss, Luke Ong, Valeria de Paiva, Ruy de Queiroz. ADVISORY COMMITTEE Johan van Benthem, Joe Halpern, Wilfrid Hodges, Angus Macintyre, Hiroakira Ono, Jouko Väänänen. ORGANISING COMMITTEE Ernesto Quadro-Vargas (Universidad de Ingenieria y Tecnologia, Lima, Peru) (Local chair) Anjolina G. de Oliveira (Univ Federal de Pernambuco, Brasil) Ruy de Queiroz (Univ Federal de Pernambuco, Brasil) (co-chair) SCIENTIFIC SPONSORSHIP Interest Group in Pure and Applied Logics (IGPL) The Association for Logic, Language and Information (FoLLI) Association for Symbolic Logic (ASL) European Association for Theoretical Computer Science (EATCS) ACM Special Interest Group on Logic and Computation (ACM-SIGLOG) (TBC) Sociedade Brasileira de Computação (SBC) Sociedade Brasileira de Lógica (SBL) SPECIAL SESSION: SCREENING OF MOVIES ABOUT MATHEMATICIANS It is planned to have a special session with the exhibition of a one-hour documentary film about a remarkable mathematician whose contributions were recognized with a Fields Medal just a few years before her untimely death. It is a joint production (still on its course) of The Mathematical Sciences Research Institute (MSRI) and George Csicsery (Zala Films): ‘Secrets of the Surface - The Mathematical Vision of Maryam Mirzakhani’. “The biographical film is about Maryam Mirzakhani, a brilliant woman, and Muslim immigrant to the United States who became a superstar in her field. The story of her life will be complemented with sections about Mirzakhani’s mathematical contributions, as explained by colleagues and illustrated with animated sequences. Throughout, we will look for clues about the sources of Mirzakhani’s insights and creativity." (http://www.zalafilms.com/secrets/ <http://www.zalafilms.com/secrets/>) FURTHER INFORMATION Contact one of the Co-Chairs of the Organising Committee. WEB PAGE http://wollic.org/wollic2020/ <http://wollic.org/wollic2020/>

1 0

Norbert Müller's Talk, Tue 15 Oct, Fukuoka
by Akitoshi Kawamura 09 Oct '19

09 Oct '19

皆様九州大学の河村と申します。ノルベルト・ミュラー先生（トリール大）の講演を下記の通り来週火曜日に九大で開催いたします。宜しければぜひお越し下さい。 http://www.fc.inf.kyushu-u.ac.jp/seminars/R011015.html ---------------------------------------------------------------------- October 15, 2019, Tuesday, 15:00– Room 1019, Ito Campus West Building 2, Kyushu University (九州大学伊都キャンパスウエスト二号館1019室) ---------------------------------------------------------------------- Joint approximations for multivariate real functions Norbert Müller (Universität Trier) ---------------------------------------------------------------------- As a generalization of the well-known NP-complete problem SAT from propositional logic, the task in SMT (Satisfiability Modulo Theories) is to determine whether certain quantifier-free formulae in first-order logic are satisfiable. Popular solvers for such problems are Z3, CVC4 or MathSAT. We are interested in the case where the first-order logic is on real numbers. For formulae describing linear arithmetic on this set, the implementations mentioned above are quite efficient (as far as possible, having to deal with NP-completeness). However, nonlinear arithmetic on real numbers is far harder, as general issues concerning decidability arise. In addition, techniques for the treatment of nonlinear formulae are still under development. Our approach combines ideas from CDCL-style SMT solving, computable analysis and the numerical approach of Taylor models. In the talk we will give brief introductions into these topics and present a prototypical implementation meant for augmenting existing SMT solvers with nonlinear arithmetic. ---------------------------------------------------------------------- -- 河村彰星九州大学システム情報科学研究院情報学部門〒819-0395　福岡市西区元岡744 092-802-3806 kawamura(a)inf.kyushu-u.ac.jp

1 0

FSCD 2020 - First CFP
by Nao Hirokawa 04 Oct '19

04 Oct '19

皆様 6月末にパリで行われます FSCD 2020 の論文募集案内をお送り致します。ぜひ論文の投稿をご検討下さい。廣川 (JAIST) CALL FOR PAPERS Fifth International Conference on Formal Structures for Computation and Deduction (FSCD 2020) June 29 -- July 5, 2020, Paris, France http://fscd2020.org/ IMPORTANT DATES --------------- All deadlines are midnight anywhere-on-earth (AoE); late submissions will not be considered. Abstract: February 6, 2020 Submission: February 9, 2020 Rebuttal: March 27-29, 2020 Notification: April 13, 2020 Final version: April 27, 2020 FSCD (http://fscdconference.org/) covers all aspects of formal structures for computation and deduction from theoretical foundations to applications. Building on two communities, RTA (Rewriting Techniques and Applications) and TLCA (Typed Lambda Calculi and Applications), FSCD embraces their core topics and broadens their scope to closely related areas in logics, models of computation, semantics and verification in new challenging areas. The suggested, but not exclusive, list of topics for submission is: 1. Calculi: Rewriting systems (string, term, higher-order, graph, conditional, modulo, infinitary, etc.); Lambda calculus; Logics (first-order, higher-order, equational, modal, linear, classical, constructive, etc.); Proof theory (natural deduction, sequent calculus, proof nets, etc.); Type theory and logical frameworks; Homotopy type theory; Quantum calculi. 2. Methods in Computation and Deduction: Type systems (polymorphism, dependent, recursive, intersection, session, etc.); Induction, coinduction; Matching, unification, completion, orderings; Strategies (normalization, completeness, etc.); Tree automata; Model building and model checking; Proof search and theorem proving; Constraint solving and decision procedures. 3. Semantics: Operational semantics and abstract machines; Game Semantics and applications; Domain theory and categorical models; Quantitative models (timing, probabilities, etc.); Quantum computation and emerging models in computation. 4. Algorithmic Analysis and Transformations of Formal Systems: Type inference and type checking; Abstract Interpretation; Complexity analysis and implicit computational complexity; Checking termination, confluence, derivational complexity and related properties; Symbolic computation. 5. Tools and Applications: Programming and proof environments; Verification tools; Proof assistants and interactive theorem provers; Applications in industry; Applications of formal systems in other sciences. 6. Semantics and Verification in new challenging areas: Certification; Security; Blockchain protocols; Data Bases; Deep learning and machine learning algorithms; Planning. PUBLICATION ----------- The proceedings will be published as an electronic volume in the Leibniz International Proceedings in Informatics (LIPIcs) of Schloss Dagstuhl. All LIPIcs proceedings are open access. SPECIAL ISSUE ------------- Authors of selected papers will be invited to submit an extended version to a special issue of Logical Methods in Computer Science. SUBMISSION GUIDELINES --------------------- Submissions can be made in two categories. Regular research papers are limited to 15 pages (including references, with the possibility to add an annex for technical details, e.g. proofs) and must present original research which is unpublished and not submitted elsewhere. System descriptions are limited to 15 pages (including references) and must present new software tools in which FSCD topics play an important role, or significantly new versions of such tools. Complete instructions on submitting a paper can be found on the conference web site. BEST PAPER AWARD BY JUNIOR RESEARCHERS -------------------------------------- The program committee will select a paper in which at least one author is a junior researcher, i.e. either a student or whose PhD award date is less than three years from the first day of the meeting. Other authors should declare to the PC Chair that at least 50% of contribution is made by the junior researcher(s). PROGRAM COMMITTEE CHAIR ----------------------- Zena M. Ariola, University of Oregon fscd2020(a)easychair.org PROGRAM COMMITTEE ----------------- M. Alpuente, Technical Univ. of Valencia S. Alves, University of Porto A. Bauer, University of Ljubljana M. P. Bonacina, Università degli studi di Verona P-L. Curien, CNRS - Univ. of Paris Diderot P. Dybjer, Chalmers Univ. of Technology U. De’Liguoro, University of Torino M. Fernandez, King’s College London M. Gaboardi, Boston University D. Ghica, University of Birmingham S. Ghilezan, University of Novi Sad J. Giesl, RWTH Aachen University S. Guerrini, University of Paris 13 R. Harper, Carnegie Mellon University M. Hasegawa, Kyoto University N. Hirokawa, JAIST P. Johann, Appalachian State University O. Kammar, University of Edinburgh D. Kesner, University of Paris Diderot C. Kop, Radboud University O. Laurent, ENS Lyon D. Licata, Wesleyan University A. Middeldorp, University of Innsbruck J. Mitchell, Stanford University K. Nakata, SAP Postdam M. Pagani, University of Paris Diderot E. Pimentel, Fed. Univ. Rio Grande do Norte Vrije F. van Raamsdonk, University Amsterdam G. Rosu, University of Illinois A. Sabry, Indiana University A. Stump, University of Iowa P. Urzyczyn, University of Warsaw T. Uustalu, Reykjavik University S. Zdancewic, University of Pennsylvania CONFERENCE CHAIR ---------------- Stefano Guerrini, University of Paris 13 WORKSHOP CHAIR -------------- Giulio Manzonetto, University of Paris 13 STEERING COMMITTEE WORKSHOP CHAIR -------------------------------- J. Vicary, Oxford University PUBLICITY CHAIR --------------- S. Alves, University of Porto FSCD STEERING COMMITTEE ----------------------- S. Alves (University of Porto), M. Ayala-Rincón (University of Brasilia) C. Fuhs (Birkbeck, London University) H. Geuvers (Radboud University) D. Kesner (Chair, University of Paris Diderot ) H. Kirchner (Inria) C. Kop (Radboud University) D. Mazza (University of Paris 13) D. Miller (Inria) L. Ong (Oxford University) J. Rehof (TU Dortmund) S. Staton (Oxford University)

1 0

基礎論セミナー
by arai toshiyasu 02 Oct '19

02 Oct '19

みなさま新井です。この度「基礎論セミナー」を不定期で開催していくことにしました。第1回の予定は下記にあります。どなたでも聴講できますのでご興味のおありの方はどうぞいらして下さい。なお、当該 web page を現在、準備中です。新井敏康第1回基礎論セミナー日時：2019年10月24日（木）13:30-15:00 場所：東京大学大学院数理科学研究科 156号室講演者：大川裕矢（千葉大学） title: 部分保存性に対する，Bennet の結果の一般化について abstract:: 文 $\varphi$ が理論 $T$ 上 $\Gamma$-保存的であるとは, 任意の $\Gamma$ 文 $\psi$ について, $T + \varphi \vdash \psi$ ならば $T \vdash \psi$ が成立することをいう. 1979 年 Guaspari は複数の理論に対して, 同時に $\Gamma$-保存的であり, 各理論では証明できない文の存在に関する部分的な議論を行ったが, その一般的な状況を解明するという問いを残していた. この問いに対し, 1986年 Bennet は特に2つの理論に対する分析を行い, 存在条件をある程度特徴付けることに成功した. 今回木更津工業高等専門学校の倉橋太志講師との共同研究により , この Bennet の結果は任意有限個の理論に拡張可能であることが判明した. 本講演ではその拡張した結果を紹介する. 問合せ先：新井敏康 tosarai(a)ms.u-tokyo.ac.jp

1 0

The 3rd International Conference on Logic and Argumentation CLAR 2020, 6-9 April 2020, Hangzhou, China
by Katsuhiko Sano 01 Oct '19

01 Oct '19

------------------------------------------------------------ The 3rd International Conference on Logic and Argumentation CLAR 2020, 6-9 April 2020, Hangzhou, China CALL FOR PAPERS ------------------------------------------------------------ The 3rd International Conference on Logic and Argumentation (CLAR 2020) invites interdisciplinary contributions from logic, artificial intelligence, philosophy, computer science, linguistics, law, and other areas studying logic and formal argumentation. CLAR 2020 will be held in Hangzhou, 6-9 April 2020, as part of the Zhejiang Logic for AI Summit (ZJULogAI 2020). With a special focus on *methods and tools for explainable AI*, a core objective of ZJULogAI is to present the latest developments and progress made on the crucial question of how to make AI more transparent, trustworthy and accountable, both in China as well as in the rest of the world. All participants to CLAR 2020 have access to all other events of ZJULogAI as well. Proceedings with accepted submissions will be available during the conference, and extended versions will be published after the conference in special issues of the Journal of Logic and Computation and the Journal of Applied Logics. More information can be found at the websites: http://www.xixilogic.org/events/clar2020 (CLAR 2020) https://www.xixilogic.org/zjulogai/ (ZJULogAI) CLAR 2020 conference highlights recent advances in the two fields of logic and argumentation and promotes communication between researchers in logic and argumentation within and outside China. Previous conferences can be accessed at: http://www.xixilogic.org/events/clar2018 http://www.xixilogic.org/events/clar2016 ************************ List of Topics ************************ Suggested topics include, but are not limited to the following: * Abstract argumentation * Applications of logic and/or argumentation * Applied logic * Argumentation and game theory * Argumentation and law * Argumentation and linguistics * Argumentation and medical reasoning * Argumentation in AI * Argument mining * Argumentation schemes * BDI logic * Computational argumentation * Deontic logic * Dynamic epistemic logic and belief revision * Formal models for dialog and argumentation * Informal logic * Judgment aggregation * Knowledge representation and reasoning * Logic for game theory * Logic for multi-agent systems * Logic for semantic web * Logic for social network * Mathematical logic * Modal logic * Nonmonotonic logics * Numerical and uncertainty reasoning * Philosophical logic * Pragma-Dialectics * Preference logic * Structured argumentation * Uncertain argumentation ************************ Submission Guidelines ************************ We invite two types of submissions: full papers (between 8 and 20 pages) describing original and unpublished work and extended abstracts (max 5 pages) of preliminary original work or extended abstracts of already published work, from either the field of logic or the field of formal argumentation. Additional support material may be included in an appendix, which may be considered or ignored by the program committee. Submissions must be prepared in LaTeX, using the LaTex template myifcolog.cls: http://icr.uni.lu/flap/ Submissions not complying with these guidelines will be desk rejected. Papers in PDF format should be submitted via EasyChair: https://easychair.org/conferences/?conf=clar2020 Each submitted paper will be carefully peer-reviewed by a panel of PC members based on originality, significance, technical soundness, clarity of exposition and relevance for the conference. For each accepted paper, at least one author is expected to register and present the paper at the conference. ************************ Important Dates ************************ Submission: 30 November 2019 Conference: 6-9 April 2020 ************************ PC Chairs ************************ Mehdi Dastani, Utrecht University Huimin Dong, Zhejiang University Leon van der Torre, University of Luxembourg ************************ Contact ************************ All questions about submissions should be emailed to: clar2020(a)xixilogic.org

1 0

公募：神戸大学大学院システム情報学研究科専任教員
by Makoto Kikuchi 01 Oct '19

01 Oct '19

皆様，神戸大学大学院システム情報学研究科情報科学専攻では，情報数理教育研究分野に属する准教授または講師1名を公募します． [専門分野] 数学基礎論・数理論理学 [募集人員（職名・採用人数）] 准教授または講師・1名 [着任時期] 2020年4月1日以降のなるべく早い時期 [募集期間] 2019年11月1日必着 [照会先] 神戸大学大学院システム情報学研究科情報科学専攻　　　専攻長ブレンドレ・ヤーグ brendle(a)kobe-u.ac.jp 詳細は添付ファイルご覧ください．菊池誠

1 0

Talk by Thomas Seiller (October 3rd, 11.00-)
by Kazushige TERUI 01 Oct '19

01 Oct '19

みなさま今週木曜日に京都大学にてThomas Seillerさんによるご講演があります。詳細は下記の通りです。よろしければぜひご参加ください。京都大学数理解析研究所照井一成 ========== Time: 11:00-12:00, October 3rd, 2019 Place: Rm 478, Research Building 2, Main Campus, Kyoto University 京都大学本部構内総合研究2号館 4階478号室 http://www.kyoto-u.ac.jp/en/access/yoshida/main.html (Building 34) Speaker: Thomas Seiller (LIPN, University of Paris 13) Title: Dynamical systems and computational complexity Abstract: Based on previous work on semantics of linear logic which used the notion of “graphing”, I started to study how these mathematical objects, which generalize partial dynamical systems, can shed new light on computability. Focussing on questions of complexity, Pellissier and I recently showed how interpreting programs as dynamical systems can lead to an abstract method for proving lower bounds that capture several previously known results. More importantly, the method can be refined to strengthen the previously best-known partial result towards settling the Ptime vs NC question negatively. Building on some realisability construction for linear logic capturing standard complexity classes, this leads to wonder about how much can be learned from dynamical systems, and if the field can provide new insights on important questions such that “Is Ptime equal to Logspace?”.

1 0

Jump to page:

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

Logic-ml