Paper/document/root.tex
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--
first part of sqeezing everything into 20 pages (at the moment we have 26)
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
2507
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
     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
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
     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
ac69ed8303cc tuned paper
Christian Urban <urbanc@in.tum.de>
parents: 1579
diff changeset
    12
\usepackage{times}
1687
51bc795b81fd more on the paper
Christian Urban <urbanc@in.tum.de>
parents: 1657
diff changeset
    13
\usepackage{boxedminipage}
1739
468c3c1adcba more on the paper
Christian Urban <urbanc@in.tum.de>
parents: 1737
diff changeset
    14
\usepackage{proof}
1737
8b6a285ad480 polished everything up to TODO
Christian Urban <urbanc@in.tum.de>
parents: 1735
diff changeset
    15
1961
Christian Urban <urbanc@in.tum.de>
parents: 1764
diff changeset
    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
51bc795b81fd more on the paper
Christian Urban <urbanc@in.tum.de>
parents: 1657
diff changeset
    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
Christian Urban <urbanc@in.tum.de>
parents: 1617
diff changeset
    31
\newcommand{\isasymnotapprox}{$\not\approx$}
Christian Urban <urbanc@in.tum.de>
parents: 1617
diff changeset
    32
\newcommand{\isasymLET}{$\mathtt{let}$}
Christian Urban <urbanc@in.tum.de>
parents: 1617
diff changeset
    33
\newcommand{\isasymAND}{$\mathtt{and}$}
Christian Urban <urbanc@in.tum.de>
parents: 1617
diff changeset
    34
\newcommand{\isasymIN}{$\mathtt{in}$}
Christian Urban <urbanc@in.tum.de>
parents: 1617
diff changeset
    35
\newcommand{\isasymEND}{$\mathtt{end}$}
Christian Urban <urbanc@in.tum.de>
parents: 1617
diff changeset
    36
\newcommand{\isasymBIND}{$\mathtt{bind}$}
Christian Urban <urbanc@in.tum.de>
parents: 1617
diff changeset
    37
\newcommand{\isasymANIL}{$\mathtt{anil}$}
Christian Urban <urbanc@in.tum.de>
parents: 1617
diff changeset
    38
\newcommand{\isasymACONS}{$\mathtt{acons}$}
1687
51bc795b81fd more on the paper
Christian Urban <urbanc@in.tum.de>
parents: 1657
diff changeset
    39
\newcommand{\isasymCASE}{$\mathtt{case}$}
51bc795b81fd more on the paper
Christian Urban <urbanc@in.tum.de>
parents: 1657
diff changeset
    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
a908ea36054f more on the paper
Christian Urban <urbanc@in.tum.de>
parents: 2342
diff changeset
    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
0368aef38e6a more on the paper
Christian Urban <urbanc@in.tum.de>
parents: 1566
diff changeset
    47
\newcommand{\fv}{\mathit{fv}}
1493
52f68b524fd2 slightly more of the paper
Christian Urban <urbanc@in.tum.de>
parents: 1485
diff changeset
    48
1703
ac2d0d4ea497 more of the paper
Christian Urban <urbanc@in.tum.de>
parents: 1687
diff changeset
    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
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    51
%%\theoremstyle{plain}
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    52
%%\spnewtheorem{thm}[section]{Theorem}
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    53
%%\newtheorem{property}[thm]{Property}
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    54
%%\newtheorem{lemma}[thm]{Lemma}
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    55
%%\spnewtheorem{defn}[theorem]{Definition}
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    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
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    65
\author{Christian Urban and Cezary Kaliszyk}
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    66
\institute{TU Munich, Germany}
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    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
ac69ed8303cc tuned paper
Christian Urban <urbanc@in.tum.de>
parents: 1579
diff changeset
    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
a7072d498723 more work on the paper
Christian Urban <urbanc@in.tum.de>
parents: 1550
diff changeset
    75
Nominal Isabelle for dealing with general bindings, that means
1657
Christian Urban <urbanc@in.tum.de>
parents: 1617
diff changeset
    76
term-constructors where multiple variables are bound at once. Such general
Christian Urban <urbanc@in.tum.de>
parents: 1617
diff changeset
    77
bindings are ubiquitous in programming language research and only very
1566
2facd6645599 tuned paper
Christian Urban <urbanc@in.tum.de>
parents: 1556
diff changeset
    78
poorly supported with single binders, such as lambda-abstractions. Our
2381
fd85f4921654 samll changes
Christian Urban <urbanc@in.tum.de>
parents: 2345
diff changeset
    79
extension includes new definitions of $\alpha$-equivalence and establishes
2341
f659ce282610 more work on the paper
Christian Urban <urbanc@in.tum.de>
parents: 2219
diff changeset
    80
automatically the reasoning infrastructure for $\alpha$-equated terms. We
1687
51bc795b81fd more on the paper
Christian Urban <urbanc@in.tum.de>
parents: 1657
diff changeset
    81
also prove strong induction principles that have the usual variable
1566
2facd6645599 tuned paper
Christian Urban <urbanc@in.tum.de>
parents: 1556
diff changeset
    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
f296ef291ca9 spell check
Christian Urban <urbanc@in.tum.de>
parents: 2341
diff changeset
    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
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    87
%\terms
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    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
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    90
%\keywords
f5621efe5a20 changed to llncs
Christian Urban <urbanc@in.tum.de>
parents: 2488
diff changeset
    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: