Seventh NII Type Theory Workshop
Date: February 6, 2012, 13:00--17:00
Place: National Institute of Informatics, Room 2005 (20th floor)
場所: 国立情報学研究所 20階 2005室
(半蔵門線,都営地下鉄三田線・新宿線 神保町駅または東西線 竹橋駅より徒歩5分)
(地図 http://www.nii.ac.jp/introduce/access1-j.shtml)
Program:
13:00--13:30 Daisuke Kimura (National Institute of Informatics)
Title: A generalized modal lambda calculus
13:30--14:00 Kazuyuki Asada (National Institute of Informatics)
Title: Semantics of Multi-rooted Graph with Ordered Branch
14:00--14:20 Tea Break
14:20--15:00 Makoto Tatsuta (National Institute of Informatics)
Title: Type Inference for Bimorphic Recursion
15:00--15:40 Yukiyoshi Kameyama (University of Tsukuba)
Title: Pseudo-Classical Modal Logic for Staged Computation
15:40--16:00 Tea Break
16:00--17:00 Stefano Berardi (Torino University)
Title: A Game Semantic for various Subclassical Logics
Abstracts:
----------------------------------------------------------------------
Daisuke Kimura (National Institute of Informatics)
Title: A generalized modal lambda calculus
Abstract: In this talk, we introduce a lambda calculus with modal
types. The types of this system contain information of possible worlds
explicitly. This information can be considered as a position which is
an abstraction of time or place. The feature of our calculus is that
we can change the property of modalities by changing information about
the relationship between positions. The aim of our research is the
following: (1) To clarify the computational meaning of necessity and
possibility modal operators. (2) To give a uniform framework that can
treat several calculi with modal types.
----------------------------------------------------------------------
Kazuyuki Asada (National Institute of Informatics)
Title: Semantics of Multi-rooted Graph with Ordered Branch
Abstract: Buneman et al. introduced a graph transformation language
UnCAL, where graph has bisimilarity semantics. There structural
recursion plays an important role, and in order to define it, they
introduced multi-rooted graph and its algebraic representation. In
this talk we give coalgebraic semantics for multi-rooted graph, and
see that such final coalgebras has some call-by-value structure. Then
we introduce a CBV equational theory. Next we modify the results of
graph with un-ordered branch to that with ordered branch, which is
important for application to XML. For this ordered graphs,
bisimilarity is defined in some subtle way, but we can use the ordered
version of above CBV equational theory for reasoning of the
bisimilarity between ordered graphs.
----------------------------------------------------------------------
Makoto Tatsuta (National Institute of Informatics)
Title: Type Inference for Bimorphic Recursion
Abstract: This talk proposes bimorphic recursion, which is restricted
polymorphic recursion such that every recursive call in the body of a
function definition has the same type. Bimorphic recursion allows us
to assign two different types to a recursively defined function: one
is for its recursive calls and the other is for its calls outside its
definition. Bimorphic recursion in this talk can be nested. This
talk shows bimorphic recursion has principal types and decidable type
inference. Hence bimorphic recursion gives us flexible typing for
recursion with decidable type inference. This talk also shows that
its typability becomes undecidable because of nesting of recursions
when one removes the instantiation property from the bimorphic
recursion. This is a joint work with Ferruccio Damiani.
----------------------------------------------------------------------
Yukiyoshi Kameyama (University of Tsukuba)
Title: Pseudo-Classical Modal Logic for Staged Computation
Abstract: In this talk, we study a pseudo-classical modal logic, which
corresponds to the staged calculus with control operators introduced
by our earlier work. Staged computation is a means for run-time code
generation, and has been proved useful in improving efficiency and
maintainability of software. We are interested in the use of control
operators in staged computation, since they play an essential role to
avoid the code duplication problem. Combining a staged calculus with
control operators in a naive way results in an unsound calculus, and
we need a restriction on the typing rule for lambda. We show that
this restriction has a logical counterpart similar to Nakano's
catch/throw calculus.
----------------------------------------------------------------------
Stefano Berardi (Torino University)
Title: A Game Semantic for various Subclassical Logics
Abstract: In this talk we describe the state of the art of game
semantics for Logic and lambda-calculus, and the motivations for
having a game semantics. Then we define a game semantic for
Intuitionism extending both Coquands and Hyland-Ongs game
semantics. The semantics refines a paper of TLCA 2007. We have two
kind of results: (1) (Soundness and Completeness) The recursive
winning strategy of our game semantics are isomorphic to the cut-free
proofs of some variant of HA-omega (Infinitary Intuitionistic
Arithmetic) (2) (Cut Elimination) Any debate between two terminating
strategies terminates. This is an ongoing joint work with M. Tatsuta.
----------------------------------------------------------------------
連絡先
龍田 真 (国立情報学研究所)
Prof. Kwangkeun Yi Lecture at NII Logic Seminar
Date: January 10, 2012, 15:00--17:00
Place: National Institute of Informatics, Lecture Room 1208 (12th floor)
場所: 国立情報学研究所 12階 1208室
(半蔵門線,都営地下鉄三田線・新宿線 神保町駅または東西線 竹橋駅より徒歩5分)
(地図 http://www.nii.ac.jp/introduce/access1-j.shtml)
Speaker: Prof. Kwangkeun Yi (Seoul National University)
Title: Static Analysis of Multi-Staged Programs via Unstaging Translation
Abstract:
Static analysis of multi-staged programs is challenging because the
basic assumption of conventional static analysis no longer holds: the
program text itself is no longer a fixed static entity, but rather a
dynamically constructed value. This article presents a
semantic-preserving translation of multi-staged call-by-value programs
into unstaged programs and a static analysis framework based on this
translation. The translation is semantic-preserving in that every
small-step reduction of a multi-staged program is simulated by the
evaluation of its unstaged version. Thanks to this translation we can
analyze multi-staged programs with existing static analysis techniques
that have been developed for conventional unstaged programs: we first
apply the unstaging translation, then we apply conventional static
analysis to the unstaged version, and finally we cast the analysis
results back in terms of the original staged program. Our translation
handles staging constructs that have been evolved to be useful in
practice (typified in Lisp's quasi-quotation): open code as values,
unrestricted operations on references and intentional
variable-capturing substitutions. This article omits references for
which we refer the reader to our companion technical report. This is
a joint work with Wontae Choi, Baris Aktemur, and Makoto Tatsuta.
問合せ先:
龍田 真 (国立情報学研究所)
e-mail: tatsuta(a)nii.ac.jp
http://research.nii.ac.jp/~tatsuta
Logic, Algebra and Truth Degrees 2012
http://www.jaist.ac.jp/rcis/latd12/
First Call for Papers
The third official meeting of the EUSFLAT Working Group on Mathematical
Fuzzy Logic [1] will be held on 10-14 September 2012 in Kanazawa, Japan.
The conference is organized by Research Center for Integrated Science
[2],
Japan Advanced Institute of Science and Technology [3].
Mathematical Fuzzy Logic is a subdiscipline of Mathematical Logic which
studies the notion of comparative truth. The assumption that 'truth
comes
in degrees' has proved to be very useful in many, both theoretical and
applied, areas of Mathematics, Computer Science and Philosophy.
The main goal of this meeting is to foster collaboration between
researchers
in the area of Mathematical Fuzzy Logic, and to promote communication
and
cooperation with members of neighbouring fields.
The featured topics included, but are not limited to, the following:
. Proof systems for fuzzy logics: Hilbert, Gentzen, natural deduction,
tableaux, resolution, computational complexity, etc.
. Algebraic semantics: residuated lattices, MTL-algebras, BL-algebras,
MV-algebras, Abstract Algebraic Logic, functional representation, etc.
. Game-theory: Giles games, Renyi-Ulam games, evaluation games, etc.
. First-order fuzzy logics: axiomatizations, arithmetical hierarchy,
model theory, etc.
. Higher-order fuzzy logical systems: type theories, Fuzzy Class Theory,
and formal fuzzy mathematics.
. Philosophical issues: connections with vagueness and uncertainty.
. Applied fuzzy logical calculi: foundations of logical programming,
logic-based reasoning about similarity, description logics, etc.
We also welcome contributions on any relevant aspects of related logical
systems (such as substructural and quantum logics, and many-valued
logics
in general).
Conference Web Site:
http://www.jaist.ac.jp/rcis/latd12/
Important dates:
. 22 April 2012: deadline for submissions
. 3 June 2012: notifications sent
. 10-14 September 2012: conference
Programme Committee:
. Stefano Aguzzoli (University of Milano, Italy)
. Matthias Baaz (Vienna University of Technology, Austria)
. Petr Cintula (Academy of Sciences, Czech Republic)
. Carles Noguera (CSIS, Spain)
. Hiroakira Ono (JAIST, Japan), Chair
. James Raftery (University of KwaZulu-Natal, South Africa)
. Constantine Tsinakis (Vanderbilt University, USA)
Invited Speakers:
. Rostislav Horcik (Academy of Sciences, Czech Republic)
. Emil Jerabek (Academy of Sciences, Czech Republic)
. Daniele Mundici (University of Florence, Italy)
. Greg Restall (University of Melbourne, Australia)
. Luca Spada (University of Salerno, Italy)
Tutorial:
. Felix Bou (CICS, Spain)
If you are interested in presenting a paper, please submit a 2–4
pages
abstract at
http://www.easychair.org/conferences/?conf=latd2012
Your submission will be confirmed automatically on the e-mail address
you provide. The accepted abstracts will be available on-line
after the final decision of the program committee. If you have any
problems to submit an abstract, please contact us at mail to:
latd2012(a)jaist.ac.jp
The deadline for contributions is 22 April 2012. The notification of
acceptance/rejection will be sent until 3 June 2012.
Conference dates:
The scientific program will start Monday morning (10 September) and
finish
Friday noon (14 September). Wednesday afternoon we plan an excursion.
Venue:
The conference will be held in the city of Kanazawa [4,5,6], located
in the
Ishikawa prefecture of Japan on the Japan Sea.
The venue is the Ishikawa Prefectural Museum of Art [7] in the center
of Kanazawa.
Local Organizing Committee:
. Norbert Preining (JAIST, Japan), Chair
. Katsuhiko Sano (JAIST, Japan)
. Kazushige Terui (Kyoto University, Japan)
. Shunsuke Yatabe (AIST, Japan)
For further information please contact: latd2012(a)jaist.ac.jp
[1] http://www.mathfuzzlog.org/
[2] http://www.jaist.ac.jp/rcis/en/
[3] http://www.jaist.ac.jp/
[4] http://en.wikipedia.org/wiki/Kanazawa,_Ishikawa
[5] http://www.kanazawa-tourism.com/
[6] http://wikitravel.org/en/Kanazawa
[7] http://www.ishibi.pref.ishikawa.jp/index_j.html
Sixth NII Type Theory Workshop
Date: November 14, 2011, 11:00--17:00
Place: National Institute of Informatics, Room 2005 (20th floor)
場所: 国立情報学研究所 20階 2005室
(半蔵門線,都営地下鉄三田線・新宿線 神保町駅または東西線 竹橋駅より徒歩5分)
(地図 http://www.nii.ac.jp/introduce/access1-j.shtml)
Program:
11:00--11:30 Takayuki Koai (National Institute of Informatics)
Title: Verification of Substitution Theorem Using HOL
11:30--12:00 Mauricio Hernandes (The Graduate University for Advanced Studies)
Title: Game theory from a logician perspective
12:00--13:40 Lunch Break
13:40--14:10 Takanori Hida (Kyoto University)
Title: A computational interpretation of the axiom of determinacy
14:10--14:40 Makoto Tatsuta (National Institute of Informatics)
Title: Non-Commutative Infinitary Peano Arithmetic
14:40--15:00 Tea Break
15:00--16:00 Neil D. Jones (University of Copenhagen)
Title: Termination Analysis of the Untyped lambda-Calculus
16:00--17:00 Stefano Berardi (Torino University)
Title: A Topology over a set of Knowledge States and a Fixed Point Problem
Abstracts:
----------------------------------------------------------------------
Takayuki Koai (National Institute of Informatics)
Title: Verification of Substitution Theorem Using HOL
Abstract: Substitution Theorem is a new theorem in untyped lambda
calculus, which was proved in 2006. This theorem states that for a
given lambda term and given free variables in it, the term becomes
weakly normalizing when we substitute arbitrary weakly normalizing
terms for these free variables, if the term becomes weakly normalizing
when we substitute a single arbitrary weakly normalizing term for
these free variables. This paper formalizes and verifies this theorem
by using higher-order theorem prover HOL. A control path, which is
the key notion in the proof, explicitly uses names of bound variables
in lambda terms, and it is defined only for lambda terms without bound
variables renaming. The lambda terms without bound variable renaming
are formalized by using the HOL package based on contextual
alpha-equivalence. The verification uses 10119 lines of HOL code and
326 lemmas. This is a joint work with Makoto Tatsuta.
----------------------------------------------------------------------
Mauricio Hernandes (The Graduate University for Advanced Studies)
Title: Game theory from a logician perspective
Abstract: I intend in this talk to introduce a few concepts in game
theory like Nash Equilibrium and Backward-Induction, and then express
those ideas with some modal logic.
----------------------------------------------------------------------
Takanori Hida (Kyoto University)
Title: A computational interpretation of the axiom of determinacy
Abstract: Axiom of determinacy(AD) is a central topic in descriptive
set theory and there are a number of research on this axiom. In this
talk, we approach to the computational content of negative translation
of AD using realizability interpretation due to Berardi, Bezem and
Coquand (1998).
----------------------------------------------------------------------
Makoto Tatsuta (National Institute of Informatics)
Title: Non-Commutative Infinitary Peano Arithmetic
Abstract: Does there exist any sequent calculus such that it is a
subclassical logic and it becomes classical logic when the exchange
rules are added? The first contribution of this paper is answering
this question for infinitary Peano arithmetic. This paper defines
infinitary Peano arithmetic with non-commutative sequents, called
non-commutative infinitary Peano arithmetic, so that the system
becomes equivalent to Peano arithmetic with the omega-rule if the the
exchange rule is added to this system. This system is unique among
other non-commutative systems, since all the logical connectives have
standard meaning and specifically the commutativity for conjunction
and disjunction is derivable. This paper shows that the provability
in non-commutative infinitary Peano arithmetic is equivalent to
Heyting arithmetic with the recursive omega rule and the law of
excluded middle for Sigma-0-1 formulas. Thus, non-commutative
infinitary Peano arithmetic is shown to be a subclassical logic. The
cut elimination theorem in this system is also proved. The second
contribution of this paper is introducing infinitary Peano arithmetic
having antecedent-grouping and no right exchange rules. The first
contribution of this paper is achieved through this system. This
system is obtained from the positive fragment of infinitary Peano
arithmetic without the exchange rules by extending it from a positive
fragment to a full system, preserving its 1-backtracking game
semantics. This paper shows that this system is equivalent to both
non-commutative infinitary Peano arithmetic, and Heyting arithmetic
with the recursive omega rule and the Sigma-0-1 excluded middle. This
is a joint work with Stefano Berardi and was presented at CSL 2011.
----------------------------------------------------------------------
Neil D. Jones (University of Copenhagen)
Title: Termination Analysis of the Untyped lambda-Calculus
Abstract: An algorithm is developed that, given an untyped
lambda-expression, can certify that its call-by-value evaluation will
terminate. It works by an extension of the ``size-change principle''
earlier applied to first-order programs. The algorithm is sound (and
proven so) but not complete: some lambda-expressions may in fact
terminate under call-by- value evaluation, but not be recognised as
terminating. The intensional power of size-change termination is
reasonably high: It certifies as terminating all primitive recursive
programs, and many interesting and useful general recursive algorithms
including programs with mutual recursion and parameter exchanges, and
Colson's ``minimum'' algorithm. Further, the approach allows free use
of the Y combinator, and so can identify as terminating a substantial
subset of PCF. (joint work with Nina Bohr; in Logical Methods in
Computer Science, 2008, Issue 1)
----------------------------------------------------------------------
Stefano Berardi (Torino University)
Title: A Topology over a set of Knowledge States and a Fixed Point Problem
Abstract: We give an abstract formulation of the termination problem
for realizer of Heyting Arithmetic plus various subsystem of classical
logic. This termination problem is expressed as the existence of a
fixed point for a class of continuous maps in a suitable topology.
----------------------------------------------------------------------