author | Christian Urban <urbanc@in.tum.de> |
Mon, 04 Oct 2010 12:39:57 +0100 | |
changeset 2508 | 6d9018d62b40 |
parent 2507 | f5621efe5a20 |
child 2509 | 679cef364022 |
permissions | -rw-r--r-- |
2507 | 1 |
\documentclass{llncs} |
2508
6d9018d62b40
first part of sqeezing everything into 20 pages (at the moment we have 26)
Christian Urban <urbanc@in.tum.de>
parents:
2507
diff
changeset
|
2 |
\usepackage{times} |
1493
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
3 |
\usepackage{isabelle} |
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
4 |
\usepackage{isabellesym} |
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
5 |
\usepackage{amsmath} |
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
6 |
\usepackage{amssymb} |
2507 | 7 |
%%\usepackage{amsthm} |
1506
7c607df46a0a
slightly more in the paper
Christian Urban <urbanc@in.tum.de>
parents:
1493
diff
changeset
|
8 |
\usepackage{tikz} |
7c607df46a0a
slightly more in the paper
Christian Urban <urbanc@in.tum.de>
parents:
1493
diff
changeset
|
9 |
\usepackage{pgf} |
7c607df46a0a
slightly more in the paper
Christian Urban <urbanc@in.tum.de>
parents:
1493
diff
changeset
|
10 |
\usepackage{pdfsetup} |
1523
eb95360d6ac6
another little bit for the introduction
Christian Urban <urbanc@in.tum.de>
parents:
1520
diff
changeset
|
11 |
\usepackage{ot1patch} |
1607 | 12 |
\usepackage{times} |
1687 | 13 |
\usepackage{boxedminipage} |
1739 | 14 |
\usepackage{proof} |
1737
8b6a285ad480
polished everything up to TODO
Christian Urban <urbanc@in.tum.de>
parents:
1735
diff
changeset
|
15 |
|
1961 | 16 |
\allowdisplaybreaks |
754
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
17 |
\urlstyle{rm} |
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
18 |
\isabellestyle{it} |
1617
99cee15cb5ff
more tuning in the paper
Christian Urban <urbanc@in.tum.de>
parents:
1607
diff
changeset
|
19 |
\renewcommand{\isastyleminor}{\it}% |
99cee15cb5ff
more tuning in the paper
Christian Urban <urbanc@in.tum.de>
parents:
1607
diff
changeset
|
20 |
\renewcommand{\isastyle}{\normalsize\it}% |
754
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
21 |
|
1523
eb95360d6ac6
another little bit for the introduction
Christian Urban <urbanc@in.tum.de>
parents:
1520
diff
changeset
|
22 |
\DeclareRobustCommand{\flqq}{\mbox{\guillemotleft}} |
eb95360d6ac6
another little bit for the introduction
Christian Urban <urbanc@in.tum.de>
parents:
1520
diff
changeset
|
23 |
\DeclareRobustCommand{\frqq}{\mbox{\guillemotright}} |
1493
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
24 |
\renewcommand{\isacharunderscore}{\mbox{$\_\!\_$}} |
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
25 |
\renewcommand{\isasymbullet}{{\raisebox{-0.4mm}{\Large$\boldsymbol{\cdot}$}}} |
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
26 |
\def\dn{\,\stackrel{\mbox{\scriptsize def}}{=}\,} |
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
27 |
\renewcommand{\isasymequiv}{$\dn$} |
1687 | 28 |
%%\renewcommand{\isasymiota}{} |
1737
8b6a285ad480
polished everything up to TODO
Christian Urban <urbanc@in.tum.de>
parents:
1735
diff
changeset
|
29 |
\renewcommand{\isasymxi}{$..$} |
1493
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
30 |
\renewcommand{\isasymemptyset}{$\varnothing$} |
1657 | 31 |
\newcommand{\isasymnotapprox}{$\not\approx$} |
32 |
\newcommand{\isasymLET}{$\mathtt{let}$} |
|
33 |
\newcommand{\isasymAND}{$\mathtt{and}$} |
|
34 |
\newcommand{\isasymIN}{$\mathtt{in}$} |
|
35 |
\newcommand{\isasymEND}{$\mathtt{end}$} |
|
36 |
\newcommand{\isasymBIND}{$\mathtt{bind}$} |
|
37 |
\newcommand{\isasymANIL}{$\mathtt{anil}$} |
|
38 |
\newcommand{\isasymACONS}{$\mathtt{acons}$} |
|
1687 | 39 |
\newcommand{\isasymCASE}{$\mathtt{case}$} |
40 |
\newcommand{\isasymOF}{$\mathtt{of}$} |
|
1764
9f55d7927e5b
more on the strong induction section
Christian Urban <urbanc@in.tum.de>
parents:
1754
diff
changeset
|
41 |
\newcommand{\isasymAL}{\makebox[0mm][l]{$^\alpha$}} |
2345 | 42 |
\newcommand{\isasymPRIME}{\makebox[0mm][l]{$'$}} |
1520
6ac75fd979d4
more of the introduction
Christian Urban <urbanc@in.tum.de>
parents:
1517
diff
changeset
|
43 |
\newcommand{\LET}{\;\mathtt{let}\;} |
6ac75fd979d4
more of the introduction
Christian Urban <urbanc@in.tum.de>
parents:
1517
diff
changeset
|
44 |
\newcommand{\IN}{\;\mathtt{in}\;} |
6ac75fd979d4
more of the introduction
Christian Urban <urbanc@in.tum.de>
parents:
1517
diff
changeset
|
45 |
\newcommand{\END}{\;\mathtt{end}\;} |
6ac75fd979d4
more of the introduction
Christian Urban <urbanc@in.tum.de>
parents:
1517
diff
changeset
|
46 |
\newcommand{\AND}{\;\mathtt{and}\;} |
1572 | 47 |
\newcommand{\fv}{\mathit{fv}} |
1493
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
48 |
|
1703 | 49 |
\newcommand{\numbered}[1]{\refstepcounter{equation}{\rm(\arabic{equation})}\label{#1}} |
1328
531dcebbf483
start of paper - does not compile yet
Christian Urban <urbanc@in.tum.de>
parents:
754
diff
changeset
|
50 |
%----------------- theorem definitions ---------- |
2507 | 51 |
%%\theoremstyle{plain} |
52 |
%%\spnewtheorem{thm}[section]{Theorem} |
|
53 |
%%\newtheorem{property}[thm]{Property} |
|
54 |
%%\newtheorem{lemma}[thm]{Lemma} |
|
55 |
%%\spnewtheorem{defn}[theorem]{Definition} |
|
56 |
%%\spnewtheorem{exmple}[theorem]{Example} |
|
1328
531dcebbf483
start of paper - does not compile yet
Christian Urban <urbanc@in.tum.de>
parents:
754
diff
changeset
|
57 |
|
531dcebbf483
start of paper - does not compile yet
Christian Urban <urbanc@in.tum.de>
parents:
754
diff
changeset
|
58 |
%-------------------- environment definitions ----------------- |
531dcebbf483
start of paper - does not compile yet
Christian Urban <urbanc@in.tum.de>
parents:
754
diff
changeset
|
59 |
\newenvironment{proof-of}[1]{{\em Proof of #1:}}{} |
754
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
60 |
|
1485
c004e7448dca
temporarily disabled tests in Nominal/ROOT
Christian Urban <urbanc@in.tum.de>
parents:
1484
diff
changeset
|
61 |
|
754
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
62 |
\begin{document} |
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
63 |
|
2508
6d9018d62b40
first part of sqeezing everything into 20 pages (at the moment we have 26)
Christian Urban <urbanc@in.tum.de>
parents:
2507
diff
changeset
|
64 |
\title{General Bindings and Alpha-Equivalence\\ in Nominal Isabelle} |
2507 | 65 |
\author{Christian Urban and Cezary Kaliszyk} |
66 |
\institute{TU Munich, Germany} |
|
67 |
%%%{\{urbanc, kaliszyk\}@in.tum.de} |
|
754
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
68 |
\maketitle |
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
69 |
|
1328
531dcebbf483
start of paper - does not compile yet
Christian Urban <urbanc@in.tum.de>
parents:
754
diff
changeset
|
70 |
\begin{abstract} |
2508
6d9018d62b40
first part of sqeezing everything into 20 pages (at the moment we have 26)
Christian Urban <urbanc@in.tum.de>
parents:
2507
diff
changeset
|
71 |
Nominal Isabelle is a definitional extension of the Isabelle/HOL theorem |
1517
62d6f7acc110
corrected the strong induction principle in the lambda-calculus case; gave a second (oartial) version that is more elegant
Christian Urban <urbanc@in.tum.de>
parents:
1506
diff
changeset
|
72 |
prover. It provides a proving infrastructure for convenient reasoning about |
1607 | 73 |
programming language calculi involving named bound variables (as |
1528
d6ee4a1b34ce
more tuning on the paper
Christian Urban <urbanc@in.tum.de>
parents:
1524
diff
changeset
|
74 |
opposed to de-Bruijn indices). In this paper we present an extension of |
1556 | 75 |
Nominal Isabelle for dealing with general bindings, that means |
1657 | 76 |
term-constructors where multiple variables are bound at once. Such general |
77 |
bindings are ubiquitous in programming language research and only very |
|
1566 | 78 |
poorly supported with single binders, such as lambda-abstractions. Our |
2381 | 79 |
extension includes new definitions of $\alpha$-equivalence and establishes |
2341 | 80 |
automatically the reasoning infrastructure for $\alpha$-equated terms. We |
1687 | 81 |
also prove strong induction principles that have the usual variable |
1566 | 82 |
convention already built in. |
1328
531dcebbf483
start of paper - does not compile yet
Christian Urban <urbanc@in.tum.de>
parents:
754
diff
changeset
|
83 |
\end{abstract} |
754
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
84 |
|
2342 | 85 |
%\category{F.4.1}{subcategory}{third-level} |
2219
dff64b2e7ec3
adapted to the official sigplan style file (this gives us more space)
Christian Urban <urbanc@in.tum.de>
parents:
2216
diff
changeset
|
86 |
|
2507 | 87 |
%\terms |
88 |
%formal reasoning, programming language calculi |
|
2219
dff64b2e7ec3
adapted to the official sigplan style file (this gives us more space)
Christian Urban <urbanc@in.tum.de>
parents:
2216
diff
changeset
|
89 |
|
2507 | 90 |
%\keywords |
91 |
%nominal logic work, variable convention |
|
2219
dff64b2e7ec3
adapted to the official sigplan style file (this gives us more space)
Christian Urban <urbanc@in.tum.de>
parents:
2216
diff
changeset
|
92 |
|
1493
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
93 |
|
754
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
94 |
\input{session} |
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
95 |
|
1493
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
96 |
\bibliographystyle{plain} |
52f68b524fd2
slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents:
1485
diff
changeset
|
97 |
\bibliography{root} |
754
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
98 |
|
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
99 |
\end{document} |
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
100 |
|
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
101 |
%%% Local Variables: |
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
102 |
%%% mode: latex |
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
103 |
%%% TeX-master: t |
b85875d65b10
added a paper for possible notes
Christian Urban <urbanc@in.tum.de>
parents:
diff
changeset
|
104 |
%%% End: |