Electronic copies of most of the papers listed below are available:
Send email to
Check also
DBLP database,
which may provide more uptodate information.
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 and Luke Ong,
"Complexity of Model Checking Recursion Schemes for Fragments of the Modal MuCalculus",
Logical methods in Computer Science, 2011.
 Davide Sangiorgi, Naoki Kobayashi, and Eijiro Sumii, "Environmental Bisimulations for HigherOrder Languages",
ACM Transactions on Programming Languages and Systems, 33(1), 2011.
 Naoki Kobayashi and Davide Sangiorgi, "A hybrid type system for lockfreedom 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):812829, 2009.
(paper)
 Koichi Kodama, Kohei Suenaga, and Naoki Kobayashi,
"Translation of Treeprocessing Programs into Streamprocessing Programs
based on Ordered Linear Type,"
Journal of Functional Programming, 18(3), pp.331371, 2008.
A preliminary summary appeared in
Proceedings of 2nd Asian Symposium on Programming Language and Systems (APLAS 2004),
Springer LNCS 3302, pp.4156, 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 ASIAPEPM'02, pp.156168, ACM Press, 2002.
[
abstract
]
[full paper ]
 Naoki Kobayashi, Kohei Suenaga, and Lucian Wischik,
"Resource Usage Analysis for the PiCalculus,"
Logical methods in Computer Science, 2(3:4), pp.142, 2006.
A preliminary summary appeared in
Proceedings of VMCAI 2006, Springer LNCS 3855, pp.298312, 2006.
(
abstract and full version )
(short version© SpringerVerlag)

Naoki Kobayashi, "TypeBased Information Flow Analysis for the PiCalculus",
Acta Informatica, Vol. 42, No.45, pp.291347, 2005
(
abstract
)
(full version )
 Atsushi Igarashi and Naoki Kobayashi, "Resource Usage Analysis,"
ACM Transactions on Programming Languages and Systems, 27(2), pp.264313, 2005.
A summary appeared in Proceedings of POPL 2002, pp.331342, ACM Press, 2002.
(
abstract
)
(summary in POPL©2002 ACM)
(full paper©2004 ACM)

Atsushi Igarashi and Naoki Kobayashi, "A Generic Type System for the PiCalculus",
Theoretical Computer Science,
Vol 311/13, pp. 121163.
A summary appeared in Proceedings of POPL 2001, pp.128141.
(Full version (small corrections were made on April 14, 2009)©2003 Elsevier Science)
 Naoki Kobayashi and Keita Shirane,
"Typebased Information Flow Analysis for LowLevel Languages,"
Computer Software 20(2), Iwanami Press, pp.221, 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 LockFree Processes,"
Information and Computation, vol. 177, pp.122159, 2002.
A preliminary version appeared in
Proceedings of TCS2000, Springer LNCS 1872, pp.365389,
under the title "Type Systems for Concurrent Processes: From DeadlockFreedom
to LivelockFreedom, TimeBoundedness."
( abstract)
( Full Paper ©2001 Academic Press)
 Atsushi Igarashi and Naoki Kobayashi,
"Type Reconstruction for Linear PiCalculus with I/O Subtyping,"
Information and Computation, 161, pp.144, 2000.
Preliminary summary appeared
as "Typebased analysis of communication for concurrent programming
languages" in Proceedings of International Static Analysis
Symposium (SAS'97), Springer LNCS 1302, pp.187201
(
abstract
)
( Full Paper )
(
Preliminary summary in SAS
)
 Naoki Kobayashi, Benjamin C. Pierce, and David N. Turner,
"Linearity and the PiCalculus, "
ACM Transactions on Programming Languages
and Systems, 21(5), pp.914947, 1999. (Preliminary summary appeared in
Proceedings of ACM SIGACT/SIGPLAN Symposium on Principles
of Programming Languages (POPL'96), pp.358371, 1996)
(abstract)
(Full paper)
(Summary in POPL'96)

Naoki Kobayashi,"TypeBased Useless Variable Elimination,"
HigherOrder and Symbolic Computation, 14(23), pp.221260, 2001.
A preliminary summary appeared in Proceedings of ACM SIGPLAN Workshop on
Partial Evaluation and SemanticsBased Program Manipulation
(PEPM'00), pp.8493, 2000.
(abstract)
(summary in PEPM'00)
(full paper)
 Naoki Kobayashi, Toshihiro Shimizu, and Akinori Yonezawa,
"Distributed Concurrent Linear Logic Programming,"
Theoretical Computer Science, vol.227, pp.185220, 1999.
 Naoki Kobayashi,
"A Partially DeadlockFree Typed Process Calculus,"
ACM Transactions on Programming Languages and Systems, Vol. 20, No. 2, pp.436482, 1998.
A preliminary summary appeared in the Proceedings of Twelfth IEEE
Symposium on
Logic in Computer Science (LICS'97), pp128139.
( abstract
)( postscript )
 Naoki Kobayashi and Akinori Yonezawa, "Towards Foundations of Concurrent
ObjectOriented 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.3145
as "TypeTheoretic Foundations for Concurrent ObjectOriented
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.113149, SpringerVerlag, 1995
(abstract)
Conference Papers
 Naoki Kobayashi, Kazutaka Matsuda, and Ayumi Shinohara,
"Functional Programs as Compressed Data",
[extended version]
A short version will appear in Proceedings of PEPM 2012, 2012, ©ACM, 2012.
 Naoki Kobayashi, Ryosuke Sato, and Hiroshi Unno,
"Predicate Abstraction and CEGAR for HigherOrder 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 HigherOrder Recursion Schemes",
A short version appears in Proceedings of FoSSaCS 2011.
[long version]
 Naoki Kobayashi, Naoshi Tabuchi, and Hiroshi Unno,
"HigherOrder MultiParameter Tree Transducers and Recursion Schemes for
Program Verification",
Proceedings of POPL 2010, pp.495508, 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© SpringerVerlag.
[PDF]
 Naoki Kobayashi,
"ModelChecking HigherOrder 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 MuCalculus."
ICALP 2009© SpringerVerlag.
(superceded by the journal version)
 Naoki Kobayashi and Luke Ong,
"A Type System Equivalent to Modal MuCalculus Model Checking of Recursion Schemes,"
A revised version will appear in LICS 2009.
[preliminary version]
 Daisuke Kikuchi and Naoki Kobayashi,
"TypeBased Automated Verification of Autheticity in Cryptographic Protocols,"
Proceedings of ESOP 2009, Springer LNCS, 2009.
[paper© SpringerVerlag]
 Naoki Kobayashi,
"Types and HigherOrder Recursion Schemes for Verification of HigherOrder Programs,"
Proceedings of POPL 2009, pp.416428, 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 LockFreedom of Mobile Processes,"
Proceedings of CAV 2008, Springer LNCS 5123, pp.8093, 2008.
 Naoki Kobayashi and Hitoshi Ohsaki,
"Tree Automata for NonLinear Arithmetic,"
Proceedings of RTA 2008, Springer LNCS 5117, pp.291305, 2008.
 Hiroshi Unno and Naoki Kobayashi,
"OnDemand Refinement of Dependent Types,"
Proceedings of FLOPS 2008, Springer LNCS 4989, pp.8196, 2008.
 Yuta Kaneko and Naoki Kobayashi,
"Linear Declassification,"
Proceedings of ESOP 2008, Springer LNCS 4960, pp.224238, 2008.
 Daisuke Kikuchi and Naoki Kobayashi,
"TypeBased Verification of Correspondence Assertions for Communication Protocols,"
Proceedings of APLAS 2007, Springer LNCS, to appear.
[
abstract
]
[paper© SpringerVerlag]
 Naoki Kobayashi and Takashi Suto,
"Undecidability of 2Label BPP Equivalences and Behavioral Type Systems for the PiCalculus,"
Proceedings of ICALP 2007, Springer LNCS 4596, pp.740751, 2007.
[
abstract
]
[short version© SpringerVerlag]
[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 HigherOrder Languages,"
LICS 2007, pp.303312, 2007.
[
abstract
]
[short version©2007 IEEE]
 Kohei Suenaga and Naoki Kobayashi,
"TypeBased Analysis of Deadlock for a Concurrent Calculus with Interrupts",
Proceedings of ESOP 2007, Springer LNCS 4421, pp.490504, 2007.
[short version© SpringerVerlag]
 Naoki Kobayashi,
"A New Type System for DeadlockFree Processes,"
Proceedings of CONCUR 2006, Springer LNCS 4137, pp.233247, 2006.
(
abstract
)
(short version© SpringerVerlag)
(full version)
 Hiroshi Unno, Naoki Kobayashi, and Akinori Yonezawa,
"Combining TypeBased Analysis and Model Checking for Finding
Counterexamples against NonInterference,"
Proceedings of ACM SIGPLAN Workshop on
Programming Languages and Analysis for Security (PLAS 2006),
pp.1726, 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.3847, 2006.
(
abstract
)
(shorter version©2006 ACM)
 Kohei Suenaga, Naoki Kobayashi, and Akinori Yonezawa,
"Extension of TypeBased Approach to Generation of StreamProcessing
Programs by Automatic Insertion of Buffering Primitives,"
Proceedings of LOPSTR 2005, 2005.
(
abstract
)
(short version© SpringerVerlag)
 Akihito Nagata, Naoki Kobayashi, and Akinori Yonezawa,
"RegionBased Memory Management for a DynamicallyTyped Language,"
Proceedings of 2nd Asian Symposium on Programming Language and Systems (APLAS 2004),
Springer LNCS 3302, pp.229245, 2004.
(
abstract
)
(short version© SpringerVerlag)

Naoki Kobayashi, "UselessCode Elimination and Program Slicing for the PiCalculus",
Proceedings of
the First Asian Symposium on Programming Languages and Systems (APLAS'03),
Springer LNCS 2895, pp.5572.
(
abstract
)
(short version© SpringerVerlag)
(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.5061, 2003.

"Type Systems for Concurrent Programs"
(
abstract
)
(paper© SpringerVerlag)
(extended version)
 Naoki Kobayashi
 Proceedings of
UNU/IIST 10th Anniversary Colloquium, LNCS 2757, pp.439453.

"An ImplicitlyTyped DeadlockFree Process Calculus"
(
abstract
) (Summary
©2000 Springer)
( Full Paper )
 Naoki Kobayashi, Shin Saito, and Eijiro Sumii
 A summary will be presented at CONCUR2000.
A preliminary version of the full paper has been published as
Technical Report TR0001, Department of Information Science,
University of Tokyo, January 2000.

"QuasiLinear Types"
(abstract)
(summary in POPL'99)
(full version)
 Naoki Kobayashi
 A revised version of the paper published as
a technical report TR9802, Department of Information Science,
University of Tokyo, September 1998.
A summary appeared in the Proceedings of ACM POPL'99, pp.2942.

"A Generalized DeadlockFree Process Calculus"
( abstract
)(full version is available from
here )
 Eijiro Sumii and Naoki Kobayashi
 Summary will appear in Proceedings of Workshop on HighLevel 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.225242, 1995.
 "HigherOrder Concurrent Linear Logic Programming"
(abstract)
 Naoki Kobayashi and Akinori Yonezawa
 Theory and Practice of Parallel Programming, LNCS 907, pp.137166,
Springer Verlag, 1995.
 "PARCS: An MPPOriented 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.254263, 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.279294, MIT Press, 1993.
Slides

"Towards a Software Model Checker for ML"
(Slides)
 Naoki Kobayashi
 Invited Talk at ML Workshop 2011

"HigherOrder Model Checking: From Theory to Practice"
(Slides)
 Naoki Kobayashi
 Invited Talk at LICS 2011

"Types and Recursion Schemes for HigherOrder Program Verification"
(Part 1)(Part 2)
 Naoki Kobayashi
 Presented at Workshop on HigherOrder Recursion Schemes and Pushdown Automata

"Types and HigherOrder Recursion Schemes for HigherOrder Program Verification"
Slides
 Naoki Kobayashi
 Invited talk at APLAS 2009
 Note: See also the slides above presented at
Workshop on HigherOrder 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 1416, Ise, Japan.

"Type Systems for Concurrent Programs"
(Slides)
Back to the Home Page