LMCS-Paper/document/root.tex
author Christian Urban <urbanc@in.tum.de>
Tue, 16 Aug 2011 17:48:09 +0200
changeset 2989 5df574281b69
parent 2985 05ccb61aa628
child 2991 8146b0ad8212
permissions -rw-r--r--
more on the intro and correct style-files
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
2989
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
     1
\documentclass{lmcs}
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
     2
%%\usepackage{times}
2985
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     3
\usepackage{isabelle}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     4
\usepackage{isabellesym}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     5
\usepackage{amsmath}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     6
\usepackage{amssymb}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     7
%%\usepackage{amsthm}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     8
\usepackage{tikz}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     9
\usepackage{pgf}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    10
\usepackage{pdfsetup}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    11
\usepackage{ot1patch}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    12
\usepackage{times}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    13
\usepackage{boxedminipage}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    14
\usepackage{proof}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    15
\usepackage{setspace}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    16
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    17
\allowdisplaybreaks
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    18
\urlstyle{rm}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    19
\isabellestyle{it}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    20
\renewcommand{\isastyleminor}{\it}%
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    21
\renewcommand{\isastyle}{\normalsize\it}%
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    22
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    23
\DeclareRobustCommand{\flqq}{\mbox{\guillemotleft}}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    24
\DeclareRobustCommand{\frqq}{\mbox{\guillemotright}}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    25
\renewcommand{\isacharunderscore}{\mbox{$\_\!\_$}}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    26
\renewcommand{\isasymbullet}{{\raisebox{-0.4mm}{\Large$\boldsymbol{\hspace{-0.5mm}\cdot\hspace{-0.5mm}}$}}}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    27
\def\dn{\,\stackrel{\mbox{\scriptsize def}}{=}\,}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    28
\renewcommand{\isasymequiv}{$\dn$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    29
%%\renewcommand{\isasymiota}{}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    30
\renewcommand{\isasymxi}{$..$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    31
\renewcommand{\isasymemptyset}{$\varnothing$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    32
\newcommand{\isasymnotapprox}{$\not\approx$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    33
\newcommand{\isasymLET}{$\mathtt{let}$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    34
\newcommand{\isasymAND}{$\mathtt{and}$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    35
\newcommand{\isasymIN}{$\mathtt{in}$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    36
\newcommand{\isasymEND}{$\mathtt{end}$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    37
\newcommand{\isasymBIND}{$\mathtt{bind}$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    38
\newcommand{\isasymANIL}{$\mathtt{anil}$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    39
\newcommand{\isasymACONS}{$\mathtt{acons}$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    40
\newcommand{\isasymCASE}{$\mathtt{case}$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    41
\newcommand{\isasymOF}{$\mathtt{of}$}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    42
\newcommand{\isasymAL}{\makebox[0mm][l]{$^\alpha$}}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    43
\newcommand{\isasymPRIME}{\makebox[0mm][l]{$'$}}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    44
\newcommand{\isasymFRESH}{\#}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    45
\newcommand{\LET}{\;\mathtt{let}\;}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    46
\newcommand{\IN}{\;\mathtt{in}\;}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    47
\newcommand{\END}{\;\mathtt{end}\;}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    48
\newcommand{\AND}{\;\mathtt{and}\;}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    49
\newcommand{\fv}{\mathit{fv}}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    50
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    51
\newcommand{\numbered}[1]{\refstepcounter{equation}{\rm(\arabic{equation})}\label{#1}}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    52
%----------------- theorem definitions ----------
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    53
%%\theoremstyle{plain}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    54
%%\spnewtheorem{thm}[section]{Theorem}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    55
%%\newtheorem{property}[thm]{Property}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    56
%%\newtheorem{lemma}[thm]{Lemma}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    57
%%\spnewtheorem{defn}[theorem]{Definition}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    58
%%\spnewtheorem{exmple}[theorem]{Example}
2989
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    59
%%\spnewtheorem{myproperty}{Property}{\bfseries}{\rmfamily}
2985
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    60
%-------------------- environment definitions -----------------
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    61
\newenvironment{proof-of}[1]{{\em Proof of #1:}}{}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    62
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    63
%\addtolength{\textwidth}{2mm}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    64
\addtolength{\parskip}{-0.33mm}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    65
\begin{document}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    66
2989
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    67
\title[Genral Bindings]{General Bindings and Alpha-Equivalence in Nominal Isabelle}
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    68
\author{Christian Urban} 
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    69
\address{Technical University of Munich, Germany}	
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    70
\email{urbanc@in.tum.de}
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    71
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    72
\author{Cezary Kaliszyk}
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    73
\address{University of Tsukuba, Japan}
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    74
\email{kaliszyk@score.cs.tsukuba.ac.jp}
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    75
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    76
\keywords{Nominal Isabelle, variable convention, formal reasoning}
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    77
\subjclass{MANDATORY list of acm classifications}
2985
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    78
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    79
\begin{abstract} 
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    80
Nominal Isabelle is a definitional extension of the Isabelle/HOL theorem
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    81
prover. It provides a proving infrastructure for reasoning about
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    82
programming language calculi involving named bound variables (as
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    83
opposed to de-Bruijn indices). In this paper we present an extension of
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    84
Nominal Isabelle for dealing with general bindings, that means
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    85
term-constructors where multiple variables are bound at once. Such general
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    86
bindings are ubiquitous in programming language research and only very
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    87
poorly supported with single binders, such as lambda-abstractions. Our
2989
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    88
extension includes new definitions of alpha-equivalence and establishes
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    89
automatically the reasoning infrastructure for alpha-equated terms. We
2985
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    90
also prove strong induction principles that have the usual variable
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    91
convention already built in.
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    92
\end{abstract}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    93
2989
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    94
\maketitle
2985
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    95
\input{session}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    96
2989
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    97
\bibliographystyle{plain}
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    98
\bibliography{root}
5df574281b69 more on the intro and correct style-files
Christian Urban <urbanc@in.tum.de>
parents: 2985
diff changeset
    99
2985
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   100
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   101
%\pagebreak
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   102
%\input{Appendix} 
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   103
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   104
\end{document}
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   105
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   106
%%% Local Variables:
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   107
%%% mode: latex
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   108
%%% TeX-master: t
05ccb61aa628 started lmcs paper (isabelle make lmcs)
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   109
%%% End: