Révision 153 CSL17/main.tex
| main.tex (revision 153) | ||
|---|---|---|
| 11 | 11 |
|
| 12 | 12 |
\bibliographystyle{plainurl}% the recommended bibstyle
|
| 13 | 13 |
|
| 14 |
\input{ph-macros}
|
|
| 15 |
|
|
| 14 | 16 |
% Author macros::begin %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 15 |
\title{A Sample Article for the LIPIcs series\footnote{This work was partially supported by someone.}}
|
|
| 16 |
\titlerunning{A Sample LIPIcs Article} %optional, in case that the title is too long; the running title should fit into the top page column
|
|
| 17 |
\title{An implicit characterisation of the polynomial hierarchy in an unbounded arithmetic}
|
|
| 18 |
%\titlerunning{An implicit characterisation of the polynomial hierarchy} %optional, in case that the title is too long; the running title should fit into the top page column
|
|
| 17 | 19 |
|
| 18 | 20 |
%% Please provide for each author the \author and \affil macro, even when authors have the same affiliation, i.e. for each author there needs to be the \author and \affil macros |
| 19 |
\author[1]{John Q. Open}
|
|
| 20 |
\author[2]{Joan R. Access}
|
|
| 21 |
\affil[1]{Dummy University Computing Laboratory, Address/City, Country\\
|
|
| 22 |
\texttt{open@dummyuniversity.org}}
|
|
| 23 |
\affil[2]{Department of Informatics, Dummy College, Address/City, Country\\
|
|
| 24 |
\texttt{access@dummycollege.org}}
|
|
| 25 |
\authorrunning{J.\,Q. Open and J.\,R. Access} %mandatory. First: Use abbreviated first/middle names. Second (only in severe cases): Use first author plus 'et. al.'
|
|
| 21 |
\author[1]{Patrick Baillot}
|
|
| 22 |
\author[2]{Anupam Das}
|
|
| 23 |
\affil[1]{LIP, ENS Lyon\\
|
|
| 24 |
\texttt{patrick.baillot@ens-lyon.fr}}
|
|
| 25 |
\affil[2]{LIP, ENS Lyon\\
|
|
| 26 |
\texttt{anupam.das@ens-lyon.fr}}
|
|
| 27 |
\authorrunning{P. Baillot and A. Das} %mandatory. First: Use abbreviated first/middle names. Second (only in severe cases): Use first author plus 'et. al.'
|
|
| 26 | 28 |
|
| 27 |
\Copyright{John Q. Open and Joan R. Access}%mandatory, please use full first names. LIPIcs license is "CC-BY"; http://creativecommons.org/licenses/by/3.0/
|
|
| 29 |
\Copyright{Patrick Baillot and Anupam Das}%mandatory, please use full first names. LIPIcs license is "CC-BY"; http://creativecommons.org/licenses/by/3.0/
|
|
| 28 | 30 |
|
| 29 | 31 |
\subjclass{Dummy classification -- please refer to \url{http://www.acm.org/about/class/ccs98-html}}% mandatory: Please choose ACM 1998 classifications from http://www.acm.org/about/class/ccs98-html . E.g., cite as "F.1.1 Models of Computation".
|
| 30 | 32 |
\keywords{Dummy keyword -- please provide 1--5 keywords}% mandatory: Please provide 1-5 keywords
|
| ... | ... | |
| 49 | 51 |
\maketitle |
| 50 | 52 |
|
| 51 | 53 |
\begin{abstract}
|
| 52 |
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent convallis orci arcu, eu mollis dolor. Aliquam eleifend suscipit lacinia. Maecenas quam mi, porta ut lacinia sed, convallis ac dui. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Suspendisse potenti.
|
|
| 54 |
We consider extensions of equational theories based on the Bellantoni-Cook function algebra for FPTIME by induction principles without bounds on quantifiers. Instead, we limit quantification to 'safe' variables and show that the provably total functions are just those of FPH. This closely resembles analogous results from bounded arithmetic, only for an unbounded setting, and the proof generalises those for previous approaches characterising FPTIME via the Bellantoni-Cook framework. We present further comparisons to the bounded arithmetic setting and give two-sorted arithmetic theories analogous to the Si2 and Vi hierarchies of bounded arithmetic.
|
|
| 53 | 55 |
\end{abstract}
|
| 54 | 56 |
|
| 55 |
\section{Typesetting instructions -- please read carefully}
|
|
| 56 |
Please comply with the following instructions when preparing your article for a LIPIcs proceedings volume. |
|
| 57 |
\begin{itemize}
|
|
| 58 |
\item Use pdflatex and an up-to-date LaTeX system. |
|
| 59 |
\item Use further LaTeX packages only if required. Avoid usage of packages like \verb+enumitem+, \verb+enumerate+, \verb+cleverref+. Keep it simple, i.e. use as few additional packages as possible. |
|
| 60 |
\item Add custom made macros carefully and only those which are needed in the article (i.e., do not simply add your convolute of macros collected over the years). |
|
| 61 |
\item Do not use a different main font. For example, the usage of the \verb+times+-package is forbidden. |
|
| 62 |
\item Provide full author names (especially with regard to the first name) in the \verb+\author+ macro and in the \verb+\Copyright+ macro. |
|
| 63 |
\item Fill out the \verb+\subjclass+ and \verb+\keywords+ macros. For the \verb+\subjclass+, please refer to the ACM classification at \url{http://www.acm.org/about/class/ccs98-html}.
|
|
| 64 |
\item Take care of suitable linebreaks and pagebreaks. No overfull \verb+\hboxes+ should occur in the warnings log. |
|
| 65 |
\item Provide suitable graphics of at least 300dpi (preferrably in pdf format). |
|
| 66 |
\item Use the provided sectioning macros: \verb+\section+, \verb+\subsection+, \verb+\subsection*+, \verb+\paragraph+, \verb+\subparagraph*+, ... ``Self-made'' sectioning commands (for example, \verb+\noindent{\bf My+ \verb+subparagraph.}+ will be removed and replaced by standard LIPIcs style sectioning commands.
|
|
| 67 |
\item Do not alter the spacing of the \verb+lipics-v2016.cls+ style file. Such modifications will be removed. |
|
| 68 |
\item Do not use conditional structures to include/exclude content. Instead, please provide only the content that should be published -- in one file -- and nothing else. |
|
| 69 |
\item Remove all comments, especially avoid commenting large text blocks and using \verb+\iffalse+ $\ldots$ \verb+\fi+ constructions. |
|
| 70 |
\item Keep the standard style (\verb+plainurl+) for the bibliography as provided by the\linebreak \verb+lipics-v2016.cls+ style file. |
|
| 71 |
\item Use BibTex and provide exactly one BibTex file for your article. The BibTex file should contain only entries that are referenced in the article. Please make sure that there are no errors and warnings with the referenced BibTex entries. |
|
| 72 |
\item Use a spellchecker to get rid of typos. |
|
| 73 |
\item A manual for the LIPIcs style is available at \url{http://drops.dagstuhl.de/styles/lipics-v2016/lipics-v2016-authors/lipics-v2016-manual.pdf}.
|
|
| 74 |
\end{itemize}
|
|
| 57 |
\input{intro}
|
|
| 58 |
\input{preliminaries}
|
|
| 59 |
\input{pv-theories}
|
|
| 75 | 60 |
|
| 61 |
\input{conclusions}
|
|
| 76 | 62 |
|
| 77 |
\section{Lorem ipsum dolor sit amet}
|
|
| 78 | 63 |
|
| 79 |
Lorem ipsum dolor sit amet, consectetur adipiscing elit \cite{DBLP:journals/cacm/Knuth74}. Praesent convallis orci arcu, eu mollis dolor. Aliquam eleifend suscipit lacinia. Maecenas quam mi, porta ut lacinia sed, convallis ac dui. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Suspendisse potenti. Donec eget odio et magna ullamcorper vehicula ut vitae libero. Maecenas lectus nulla, auctor nec varius ac, ultricies et turpis. Pellentesque id ante erat. In hac habitasse platea dictumst. Curabitur a scelerisque odio. Pellentesque elit risus, posuere quis elementum at, pellentesque ut diam. Quisque aliquam libero id mi imperdiet quis convallis turpis eleifend.
|
|
| 64 |
%\subparagraph*{Acknowledgements.}
|
|
| 65 |
% |
|
| 66 |
%I want to thank \dots |
|
| 67 |
% |
|
| 68 |
%\appendix |
|
| 69 |
%\section{Put appendix here if necessary}
|
|
| 70 |
% |
|
| 71 |
%test |
|
| 80 | 72 |
|
| 81 |
\begin{lemma}[Lorem ipsum]
|
|
| 82 |
\label{lemma:lorem}
|
|
| 83 |
Vestibulum sodales dolor et dui cursus iaculis. Nullam ullamcorper purus vel turpis lobortis eu tempus lorem semper. Proin facilisis gravida rutrum. Etiam sed sollicitudin lorem. Proin pellentesque risus at elit hendrerit pharetra. Integer at turpis varius libero rhoncus fermentum vitae vitae metus. |
|
| 84 |
\end{lemma}
|
|
| 85 | 73 |
|
| 86 |
\begin{proof}
|
|
| 87 |
Cras purus lorem, pulvinar et fermentum sagittis, suscipit quis magna. |
|
| 88 |
\end{proof}
|
|
| 89 |
|
|
| 90 |
\begin{theorem}[Curabitur pulvinar, \cite{DBLP:books/mk/GrayR93}]
|
|
| 91 |
\label{theorem:curabitur}
|
|
| 92 |
Nam liber tempor cum soluta nobis eleifend option congue nihil imperdiet doming id quod mazim placerat facer possim assum. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. |
|
| 93 |
\end{theorem}
|
|
| 94 |
|
|
| 95 |
\subsection{Curabitur dictum felis id sapien}
|
|
| 96 |
|
|
| 97 |
Curabitur dictum felis id sapien mollis ut venenatis tortor feugiat. Curabitur sed velit diam. Integer aliquam, nunc ac egestas lacinia, nibh est vehicula nibh, ac auctor velit tellus non arcu. Vestibulum lacinia ipsum vitae nisi ultrices eget gravida turpis laoreet. Duis rutrum dapibus ornare. Nulla vehicula vulputate iaculis. Proin a consequat neque. Donec ut rutrum urna. Morbi scelerisque turpis sed elit sagittis eu scelerisque quam condimentum. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Aenean nec faucibus leo. Cras ut nisl odio, non tincidunt lorem. Integer purus ligula, venenatis et convallis lacinia, scelerisque at erat. Fusce risus libero, convallis at fermentum in, dignissim sed sem. Ut dapibus orci vitae nisl viverra nec adipiscing tortor condimentum \cite{DBLP:journals/cacm/Dijkstra68a}. Donec non suscipit lorem. Nam sit amet enim vitae nisl accumsan pretium.
|
|
| 98 |
|
|
| 99 |
\begin{lstlisting}[caption={Useless code},label=list:8-6,captionpos=t,float,abovecaptionskip=-\medskipamount]
|
|
| 100 |
for i:=maxint to 0 do |
|
| 101 |
begin |
|
| 102 |
j:=square(root(i)); |
|
| 103 |
end; |
|
| 104 |
\end{lstlisting}
|
|
| 105 |
|
|
| 106 |
\subsection{Proin ac fermentum augue}
|
|
| 107 |
|
|
| 108 |
Proin ac fermentum augue. Nullam bibendum enim sollicitudin tellus egestas lacinia euismod orci mollis. Nulla facilisi. Vivamus volutpat venenatis sapien, vitae feugiat arcu fringilla ac. Mauris sapien tortor, sagittis eget auctor at, vulputate pharetra magna. Sed congue, dui nec vulputate convallis, sem nunc adipiscing dui, vel venenatis mauris sem in dui. Praesent a pretium quam. Mauris non mauris sit amet eros rutrum aliquam id ut sapien. Nulla aliquet fringilla sagittis. Pellentesque eu metus posuere nunc tincidunt dignissim in tempor dolor. Nulla cursus aliquet enim. Cras sapien risus, accumsan eu cursus ut, commodo vel velit. Praesent aliquet consectetur ligula, vitae iaculis ligula interdum vel. Integer faucibus faucibus felis. |
|
| 109 |
|
|
| 110 |
\begin{itemize}
|
|
| 111 |
\item Ut vitae diam augue. |
|
| 112 |
\item Integer lacus ante, pellentesque sed sollicitudin et, pulvinar adipiscing sem. |
|
| 113 |
\item Maecenas facilisis, leo quis tincidunt egestas, magna ipsum condimentum orci, vitae facilisis nibh turpis et elit. |
|
| 114 |
\end{itemize}
|
|
| 115 |
|
|
| 116 |
\section{Pellentesque quis tortor}
|
|
| 117 |
|
|
| 118 |
Nec urna malesuada sollicitudin. Nulla facilisi. Vivamus aliquam tempus ligula eget ornare. Praesent eget magna ut turpis mattis cursus. Aliquam vel condimentum orci. Nunc congue, libero in gravida convallis \cite{DBLP:conf/focs/HopcroftPV75}, orci nibh sodales quam, id egestas felis mi nec nisi. Suspendisse tincidunt, est ac vestibulum posuere, justo odio bibendum urna, rutrum bibendum dolor sem nec tellus.
|
|
| 119 |
|
|
| 120 |
\begin{lemma} [Quisque blandit tempus nunc]
|
|
| 121 |
Sed interdum nisl pretium non. Mauris sodales consequat risus vel consectetur. Aliquam erat volutpat. Nunc sed sapien ligula. Proin faucibus sapien luctus nisl feugiat convallis faucibus elit cursus. Nunc vestibulum nunc ac massa pretium pharetra. Nulla facilisis turpis id augue venenatis blandit. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. |
|
| 122 |
\end{lemma}
|
|
| 123 |
|
|
| 124 |
Fusce eu leo nisi. Cras eget orci neque, eleifend dapibus felis. Duis et leo dui. Nam vulputate, velit et laoreet porttitor, quam arcu facilisis dui, sed malesuada risus massa sit amet neque. |
|
| 125 |
|
|
| 126 |
|
|
| 127 |
\subparagraph*{Acknowledgements.}
|
|
| 128 |
|
|
| 129 |
I want to thank \dots |
|
| 130 |
|
|
| 131 |
\appendix |
|
| 132 |
\section{Morbi eros magna}
|
|
| 133 |
|
|
| 134 |
Morbi eros magna, vestibulum non posuere non, porta eu quam. Maecenas vitae orci risus, eget imperdiet mauris. Donec massa mauris, pellentesque vel lobortis eu, molestie ac turpis. Sed condimentum convallis dolor, a dignissim est ultrices eu. Donec consectetur volutpat eros, et ornare dui ultricies id. Vivamus eu augue eget dolor euismod ultrices et sit amet nisi. Vivamus malesuada leo ac leo ullamcorper tempor. Donec justo mi, tempor vitae aliquet non, faucibus eu lacus. Donec dictum gravida neque, non porta turpis imperdiet eget. Curabitur quis euismod ligula. |
|
| 135 |
|
|
| 136 |
|
|
| 137 | 74 |
%% |
| 138 | 75 |
%% Bibliography |
| 139 | 76 |
%% |
| 140 | 77 |
|
| 141 | 78 |
%% Either use bibtex (recommended), |
| 142 | 79 |
|
| 143 |
\bibliography{lipics-v2016-sample-article}
|
|
| 80 |
\bibliography{ph-biblio}
|
|
| 144 | 81 |
|
| 145 | 82 |
%% .. or use the thebibliography environment explicitely |
| 146 | 83 |
|
Formats disponibles : Unified diff