Selected papers and slides of Naoki Kobayashi

Check also DBLP database, which provides a more exhaustive list of publications.

Notice: The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Journal Papers

• Naoki Kobayashi, "Inclusion Between the Frontier Language of a Non-Deterministic Recursive Program Scheme and the Dyck Language is Undecidable", accepted for publication in Theoretical Computer Science, a special issue in memory of Maurice Nivat. [paper]
• Naoki Kobayashi, "Model Checking Higher-Order Programs", Journal of the ACM, 60(3), Article No.20, June 2013. [paper This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version is available from here.]
• Naoki Kobayashi, Kazutaka Matsuda, Ayumi Shinohara, Kazuya Yaguchi, "Functional Programs as Compressed Data", to appear in Higher-Order and Symbolic Computation, PEPM2012 special issue. A short version appeared in Proceedings of PEPM 2012, pp.53-62, 2012, ©ACM, 2012.
• Naoki Kobayashi and Luke Ong, "Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus", Logical methods in Computer Science, 2011.
• Davide Sangiorgi, Naoki Kobayashi, and Eijiro Sumii, "Environmental Bisimulations for Higher-Order Languages", ACM Transactions on Programming Languages and Systems, 33(1), 2011.
• Naoki Kobayashi and Davide Sangiorgi, "A hybrid type system for lock-freedom of mobile processes", ACM Transactions on Programming Languages and Systems, 32(5), 2010. [paper © ACM, 2010. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version is available from here.]
• Hans Hüttel, Naoki Kobayashi, and Takashi Suto "Undecidable Equivalences for Basic Parallel Processes," Information and Computation, 207(7):812-829, 2009. (paper)
• Koichi Kodama, Kohei Suenaga, and Naoki Kobayashi, "Translation of Tree-processing Programs into Stream-processing Programs based on Ordered Linear Type," Journal of Functional Programming, 18(3), pp.331-371, 2008. A preliminary summary appeared in Proceedings of 2nd Asian Symposium on Programming Language and Systems (APLAS 2004), Springer LNCS 3302, pp.41-56, 2004. ( abstract ) (paper)
• Futoshi Iwama and Naoki Kobayashi, "A New Type System for JVM Lock Primitives," to appear in New Generation Computing. A summary appeared in Proceedings of ASIA-PEPM'02, pp.156-168, ACM Press, 2002. [ abstract ] [full paper ]
• Naoki Kobayashi, Kohei Suenaga, and Lucian Wischik, "Resource Usage Analysis for the Pi-Calculus," Logical methods in Computer Science, 2(3:4), pp.1-42, 2006. A preliminary summary appeared in Proceedings of VMCAI 2006, Springer LNCS 3855, pp.298-312, 2006. ( abstract and full version ) (short version© Springer-Verlag)
• Naoki Kobayashi, "Type-Based Information Flow Analysis for the Pi-Calculus", Acta Informatica, Vol. 42, No.4-5, pp.291-347, 2005 ( abstract ) (full version )
• Atsushi Igarashi and Naoki Kobayashi, "Resource Usage Analysis," ACM Transactions on Programming Languages and Systems, 27(2), pp.264-313, 2005. A summary appeared in Proceedings of POPL 2002, pp.331-342, ACM Press, 2002. ( abstract ) (summary in POPL©2002 ACM) (full paper©2004 ACM)
• Atsushi Igarashi and Naoki Kobayashi, "A Generic Type System for the Pi-Calculus", Theoretical Computer Science, Vol 311/1-3, pp. 121-163. A summary appeared in Proceedings of POPL 2001, pp.128-141. (Full version (small corrections were made on April 14, 2009)©2003 Elsevier Science)
• Naoki Kobayashi and Keita Shirane, "Type-based Information Flow Analysis for Low-Level Languages," Computer Software 20(2), Iwanami Press, pp.2-21, 2003 (in Japanese). The English version appeared in informal proceedings of the 3rd Asian Workshop on Programming Languages and Systems (APLAS'02). ( Abstract ) (Full paper (In Japanese) ) ( Shorter version written in English )
• Naoki Kobayashi, "A Type System for Lock-Free Processes," Information and Computation, vol. 177, pp.122-159, 2002. A preliminary version appeared in Proceedings of TCS2000, Springer LNCS 1872, pp.365-389, under the title "Type Systems for Concurrent Processes: From Deadlock-Freedom to Livelock-Freedom, Time-Boundedness." ( abstract) ( Full Paper ©2001 Academic Press)
• Atsushi Igarashi and Naoki Kobayashi, "Type Reconstruction for Linear Pi-Calculus with I/O Subtyping," Information and Computation, 161, pp.1-44, 2000. Preliminary summary appeared as "Type-based analysis of communication for concurrent programming languages" in Proceedings of International Static Analysis Symposium (SAS'97), Springer LNCS 1302, pp.187-201 ( abstract ) ( Full Paper ) ( Preliminary summary in SAS )
• Naoki Kobayashi, Benjamin C. Pierce, and David N. Turner, "Linearity and the Pi-Calculus, " ACM Transactions on Programming Languages and Systems, 21(5), pp.914-947, 1999. (Preliminary summary appeared in Proceedings of ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages (POPL'96), pp.358-371, 1996) (abstract) (Full paper) (Summary in POPL'96)
• Naoki Kobayashi,"Type-Based Useless Variable Elimination," Higher-Order and Symbolic Computation, 14(2-3), pp.221-260, 2001. A preliminary summary appeared in Proceedings of ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'00), pp.84-93, 2000. (abstract) (summary in PEPM'00) (full paper)
• Naoki Kobayashi, "A Partially Deadlock-Free Typed Process Calculus," ACM Transactions on Programming Languages and Systems, Vol. 20, No. 2, pp.436-482, 1998. A preliminary summary appeared in the Proceedings of Twelfth IEEE Symposium on Logic in Computer Science (LICS'97), pp128-139. ( abstract )( postscript )
• Naoki Kobayashi and Akinori Yonezawa, "Towards Foundations of Concurrent Object-Oriented Programming -- Types and Language Design," Theory and Practice of Object Systems, John Wiley & Sons, 1(4), 1995 (Preliminary summary appeared in Proceedings of ACM OOPSLA94, pp.31-45 as "Type-Theoretic Foundations for Concurrent Object-Oriented Programming") (abstract)
• Naoki Kobayashi and Akinori Yonezawa, "Asynchronous Communication Model Based on Linear Logic," Journal of Formal Aspects of Computing, Vol.7, No.2, pp.113-149, Springer-Verlag, 1995 (abstract)

Conference Papers

• Ren Fukaishi, Naoki Kobayashi, and Ryosuke Sato, "Productivity Verification for Functional Programs by Reduction to Termination Verification", Proceedings of PEPM 2024. [a long version]
• Ryo Mukai, Naoki Kobayashi, and Ryosuke Sato, "Parameterized Recursive Refinement Types for Automated Program Verification", Proceedings of SAS 2022. [a long version]
• Naoki Kobayashi, Takeshi Nishikawa, Atsushi Igarashi, and Hiroshi Unno, "Temporal Verification of Programs via First-Order Fixpoint Logic", Proceedings of SAS 2019. [a long version]
• Naoki Kobayashi, Takeshi Tsukada, and Keiichi Watanabe, "Higher-Order Program Verification via HFL Model Checking", Proceedings of ESOP 2018. [a long version]
• Adrien Champion, Tomoya Chiba, Naoki Kobayashi, and Ryosuke Sato, "ICE-based Refinement Type Discovery for Higher-Order Functional Programs", Proceedings of TACAS 2018. A revised and extended version was published in Journal of Automated Reasoning, 64(7), pp.1393-1418, 2020. [a long version]
• Kazuyuki Asada and Naoki Kobayashi, "Pumping Lemma for Higher-order Languages", Proceedings of ICALP 2017. [a long version]
• Naoki Kobayashi, Etienne Lozes, and Florian Bruse, "On the Relationship between Higher-Order Recursion Schemes and Higher-Order Fixpoint Logic", Proceedings of POPL 2017. [the conference version© ACM]. [a longer version]
• Takuya Kuwahara, Ryosuke Sato, Hiroshi Unno, and Naoki Kobayashi, "Predicate Abstraction and CEGAR for Disproving Termination of Higher-order Functional Programs", Proceedings of CAV 2015. © Springer-Verlag. [longer version]
• Yuma Matsumoto, Naoki Kobayashi, and Hiroshi Unno, "Automata-Based Abstraction for Automated Verification of Higher-Order Tree-Processing Programs", Proceedings of APLAS 2015. © Springer-Verlag. [longer version]
• Naoki Kobayashi and Xin Li, "Automata-Based Abstraction Refinement for muHORS Model Checking", Proceedings of LICS 2015. [short version© IEEE] [longer version]
• Taku Terao and Naoki Kobayashi, "A ZDD-based Efficient Higher-Order Model Checking Algorithm", Proceedings of APLAS 2014. publisher version© Springer-Verlag. authors' version. [Note: There was an error in Table 1 of the publisher version. The "D" column for the row "filter-nonzero-1" should be "Y", instead of "N". See the authors' version. ]
• Elena Giachino, Naoki Kobayashi, and Cosimo Laneve, "Deadlock analysis of unbounded process networks", Proceedings of CONCUR 2014. short version© Springer-Verlag. [longer version]
• Kazuhide Yasukata, Naoki Kobayashi, and Kazutaka Matsuda, "Pairwise Reachability Analysis for Higher Order Concurrent Programs by Higher-Order Model Checking", Proceedings of CONCUR 2014. short version© Springer-Verlag. [longer version] [Note: There was a flaw in the automata used in the experiments reported in the published version, hence Table 1 of the published version is wrong. The corrected experimental result is given in Table 1 of the longer version above. ]
• Naoki Kobayashi, Kazuhiro Inaba, and Takeshi Tsukada, "Unsafe Order-2 Tree Languages are Context-Sensitive", Proceedings of FoSSaCS 2014, 2014. © Springer-Verlag. [long version] (Note: the short version that appeared in Proceedings of FoSSaCS 2014 contained a few errors, which have been corrected in the long version)
• Christopher Broadbent and Naoki Kobayashi, "Saturation-Based Model Checking of Higher-Order Recursion Schemes", Proceedings of CSL 2013. [paper]
• Naoki Kobayashi, "Pumping by Typing", Proceedings of LICS 2013. [short version© IEEE (This is a preliminary version. The final version will be available from IEEE.)] [longer version]
• Naoki Kobayashi and Atsushi Igarashi, "Model Checking Higher-Order Programs with Recursive Types", Proceedings of ESOP 2013, 2013. © Springer-Verlag. [PDF]
• Yoshihiro Tobita, Takeshi Tsukada and Naoki Kobayashi, "Exact Flow Analysis by Higher-Order Model Checking." Proceedings of FLOPS 2012, pp.275-289, 2012 © Springer-Verlag. [PDF] [extended version]
• Naoki Kobayashi, Ryosuke Sato, and Hiroshi Unno, "Predicate Abstraction and CEGAR for Higher-Order Model Checking", To appear in Proceedings of PLDI 2011, 2011. [paper © ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version will be published in Proceedings of PLDI 2011.]
• Naoki Kobayashi, "A Practical Linear Time Algorithm for Trivial Automata Model Checking of Higher-Order Recursion Schemes", A short version appears in Proceedings of FoSSaCS 2011. [long version]
• Morten Dahl, Naoki Kobayashi, Yunde Sun, and Hans Huttel, "Type-Based Automated Verification of Authenticity in Asymmetric Cryptographic Protocols," Proceedings of ATVA 2011, Springer LNCS 6996, pp.75-89, 2011. [paper© Springer, 2011.]
• Naoki Kobayashi, Naoshi Tabuchi, and Hiroshi Unno, "Higher-Order Multi-Parameter Tree Transducers and Recursion Schemes for Program Verification", Proceedings of POPL 2010, pp.495-508, 2010. [paper © ACM, 2010. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version will be published in Proceedings of POPL'10.]
• Kohei Suenaga and Naoki Kobayashi, "Fractional Ownerships for Safe Memory Deallocation." To appear in APLAS 2009© Springer-Verlag. [PDF]
• Naoki Kobayashi, "Model-Checking Higher-Order Functions", To appear in PPDP 2009. [paper © ACM, 2009. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version will be published in Proceedings of PPDP'09.]
• Naoki Kobayashi and Luke Ong, "Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus." ICALP 2009© Springer-Verlag. (superceded by the journal version)
• Naoki Kobayashi and Luke Ong, "A Type System Equivalent to Modal Mu-Calculus Model Checking of Recursion Schemes," A revised version will appear in LICS 2009. [preliminary version] [a draft of the revised and extended version]
• Daisuke Kikuchi and Naoki Kobayashi, "Type-Based Automated Verification of Autheticity in Cryptographic Protocols," Proceedings of ESOP 2009, Springer LNCS, 2009. [paper© Springer-Verlag]
• Naoki Kobayashi, "Types and Higher-Order Recursion Schemes for Verification of Higher-Order Programs," Proceedings of POPL 2009, pp.416-428, 2009. [paper© ACM, 2009. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of POPL'09. http://doi.acm.org/10.1145/1480881.1480993.]
• Naoki Kobayashi and Davide Sangiorgi, "A Hybrid Type System for Lock-Freedom of Mobile Processes," Proceedings of CAV 2008, Springer LNCS 5123, pp.80-93, 2008.
• Naoki Kobayashi and Hitoshi Ohsaki, "Tree Automata for Non-Linear Arithmetic," Proceedings of RTA 2008, Springer LNCS 5117, pp.291-305, 2008.
• Hiroshi Unno and Naoki Kobayashi, "On-Demand Refinement of Dependent Types," Proceedings of FLOPS 2008, Springer LNCS 4989, pp.81-96, 2008.
• Yuta Kaneko and Naoki Kobayashi, "Linear Declassification," Proceedings of ESOP 2008, Springer LNCS 4960, pp.224-238, 2008.
• Daisuke Kikuchi and Naoki Kobayashi, "Type-Based Verification of Correspondence Assertions for Communication Protocols," Proceedings of APLAS 2007, Springer LNCS, to appear. [ abstract ] [paper© Springer-Verlag]
• Naoki Kobayashi and Takashi Suto, "Undecidability of 2-Label BPP Equivalences and Behavioral Type Systems for the Pi-Calculus," Proceedings of ICALP 2007, Springer LNCS 4596, pp.740-751, 2007. [ abstract ] [short version© Springer-Verlag] [full version] [ Undecidability of BPP Equivalences Revisited (a supplementary note on the flaws of Hans Huttel's proof of undecidability of BPP equivalences and a corrected proof)]
• Davide Sangiorgi, Naoki Kobayashi, and Eijiro Sumii, "Environmental Bisimulations for Higher-Order Languages," LICS 2007, pp.303-312, 2007. [ abstract ] [short version©2007 IEEE]
• Kohei Suenaga and Naoki Kobayashi, "Type-Based Analysis of Deadlock for a Concurrent Calculus with Interrupts", Proceedings of ESOP 2007, Springer LNCS 4421, pp.490-504, 2007. [short version© Springer-Verlag]
• Naoki Kobayashi, "A New Type System for Deadlock-Free Processes," Proceedings of CONCUR 2006, Springer LNCS 4137, pp.233-247, 2006. ( abstract ) (short version© Springer-Verlag) (full version)
• Hiroshi Unno, Naoki Kobayashi, and Akinori Yonezawa, "Combining Type-Based Analysis and Model Checking for Finding Counterexamples against Non-Interference," Proceedings of ACM SIGPLAN Workshop on Programming Languages and Analysis for Security (PLAS 2006), pp.17-26, 2006. (abstract) (paper©2006 ACM)
• Futoshi Iwama, Atsushi Igarashi and Naoki Kobayashi, "Resource Usage Analysis for a Functional Language with Exceptions," Proceedings of ACM SIGPLAN 2006 Workshop on Partial Evaluation and Program Manipulation (PEPM 2006), pp.38-47, 2006. ( abstract ) (shorter version©2006 ACM)
• Kohei Suenaga, Naoki Kobayashi, and Akinori Yonezawa, "Extension of Type-Based Approach to Generation of Stream-Processing Programs by Automatic Insertion of Buffering Primitives," Proceedings of LOPSTR 2005, 2005. ( abstract ) (short version© Springer-Verlag)
• Akihito Nagata, Naoki Kobayashi, and Akinori Yonezawa, "Region-Based Memory Management for a Dynamically-Typed Language," Proceedings of 2nd Asian Symposium on Programming Language and Systems (APLAS 2004), Springer LNCS 3302, pp.229-245, 2004. ( abstract ) (short version© Springer-Verlag)
• Naoki Kobayashi, "Useless-Code Elimination and Program Slicing for the Pi-Calculus", Proceedings of the First Asian Symposium on Programming Languages and Systems (APLAS'03), Springer LNCS 2895, pp.55-72. ( abstract ) (short version© Springer-Verlag) (full version)
• "Time Regions and Effects for Resource Usage Analysis" ( abstract ) (Summary ©2003 ACM) (full paper )
  • Naoki Kobayashi
  • The summary appeared in Proceedings of ACM SIGPLAN International Workshop on Types in Languages Design and Implementation (TLDI'03), pp.50-61, 2003.
• "Type Systems for Concurrent Programs" ( abstract ) (paper© Springer-Verlag) (extended version)
  • Naoki Kobayashi
  • Proceedings of UNU/IIST 10th Anniversary Colloquium, LNCS 2757, pp.439-453.
• "An Implicitly-Typed Deadlock-Free Process Calculus" ( abstract ) (Summary ©2000 Springer) ( Full Paper )
  • Naoki Kobayashi, Shin Saito, and Eijiro Sumii
  • A summary appeared in Proceedings of CONCUR2000. A preliminary version of the full paper has been published as Technical Report TR00-01, Department of Information Science, University of Tokyo, January 2000.
• "Quasi-Linear Types" (abstract) (summary in POPL'99) (full version)
  • Naoki Kobayashi
  • A revised version of the paper published as a technical report TR98-02, Department of Information Science, University of Tokyo, September 1998. A summary appeared in the Proceedings of ACM POPL'99, pp.29-42.
• "A Generalized Deadlock-Free Process Calculus" ( abstract )(full version is available from here )
  • Eijiro Sumii and Naoki Kobayashi
  • Summary will appear in Proceedings of Workshop on High-Level Concurrent Language (HLCL'98), ENTCS, Vol.16, No.3. Full version will appear as a technical report from Department of Information Science, University of Tokyo
• "Static Analysis of Communication for Asynchronous Concurrent Programming Languages" (abstract) (postscript file)
  • Naoki Kobayashi, Motoki Nakade, and Akinori Yonezawa
  • Second International Static Analysis Symposium (SAS'95), LNCS 983, pp.225-242, 1995.
• "Higher-Order Concurrent Linear Logic Programming" (abstract)
  • Naoki Kobayashi and Akinori Yonezawa
  • Theory and Practice of Parallel Programming, LNCS 907, pp.137-166, Springer Verlag, 1995.
• "PARCS: An MPP-Oriented CLP language"
  • K. Konno, M. Nagatsuka, N. Kobayashi, S. Matsuoka, and A. Yonezawa
  • Proceedings of the First International Symposium on Parallel Symbolic Computation (PASCO'94), pp.254-263, World Scientific, September 1994.
• "ACL - A Concurrent Linear Logic Programming Paradigm"
  • Naoki Kobayashi and Akinori Yonezawa
  • Logic Programming: Proceedings of the 1993 International Symposium, pp.279-294, MIT Press, 1993.

Slides and Videos for Talks

• "An Overview of the HFL Model Checking Project": Video , Slides
  • Naoki Kobayashi
  • Invited Talk at HCVS 21
• "10 Years of the Higher-Order Model Checking Project": Video , Slides
  • Naoki Kobayashi
  • Invited Talk at PPDP 2019 and LOPSTR 2019
• PPL 2018 tutorial on HORS/HFL model checking (in Japanese): Slides
• POPL 2016 tutorial: "Higher-Order Model Checking"

  See this page

• "Towards a Software Model Checker for ML" (Slides)
  • Naoki Kobayashi
  • Invited Talk at ML Workshop 2011
• "Higher-Order Model Checking: From Theory to Practice" (Slides)
  • Naoki Kobayashi
  • Invited Talk at LICS 2011
• "Types and Recursion Schemes for Higher-Order Program Verification" (Part 1)(Part 2)
  • Naoki Kobayashi
  • Presented at Workshop on Higher-Order Recursion Schemes and Pushdown Automata
• "Types and Higher-Order Recursion Schemes for Higher-Order Program Verification" Slides
  • Naoki Kobayashi
  • Invited talk at APLAS 2009
  • Note: See also the slides above presented at Workshop on Higher-Order Recursion Schemes and Pushdown Automata, which contain more technical details.
• "Substructural Type Systems for Program Analysis" (Slides)
  • Naoki Kobayashi
  • Invited Talk at FLOPS 2008, April 14-16, Ise, Japan.
• "Type Systems for Concurrent Programs" (Slides)
  • Naoki Kobayashi
  • UNU/IIST 10th Anniversary Colloquium, March 2002, Lisbon, Portugal.