\documentclass[12pt]{article}
\usepackage{amssymb,latexsym,logik,abb2e}
\setlength{\unitlength}{1em}
\bibliographystyle{plain}
\title{The Combinatorics of Cases}
\author{Marcus Kracht 
\thanks{This paper has been prepared in long discussions with 
Alan Dench and Jens Michaelis, both of whom have contributed 
significantly to the genesis of this paper. The stay of Alan Dench 
at Potsdam has been made possible through the Innovationskolleg INK 12. 
Furthermore, the paper contains ideas presented at a workshop 
on Morphology and Complexity of Language at the University 
of Potsdam, in December 1996, likewise financed through the 
Innovationskolleg INK 12. I wish to thank the audience there, 
especially Gisbert Fanslow, Ed Keenan and David Perlmutter for 
constructive criticism. Finally, I wish to thank Christian 
Ebert for discussions on the complexity of case marking.} \\
II.~Mathematisches Institut \\
Arnimallee 3 \\ 
D -- 14195 Berlin}
\begin{document}
\maketitle
%%
\begin{abstract}
In this paper we will introduce a semantics for languages 
with stacked cases. In these languages, the burden of building 
up the structure is carried entirely by the morphology and 
syntactic structure is redundant. This is the exact opposite 
of standard Montague semantics, which is based on $\lambda$--calculus, 
where morphology is redundant and the meaning is computed from the 
structure alone. Furthermore, we shall demonstrate that only case 
marking languages can afford free word order. Although the languages 
fall out of standard hierachies of languages (they are not even 
multiply context--free since they are not semilinear) we will show 
that their complexity is very low, with an upper bound of 
$O(n^{3/2} \log n)$. The semantics is also of low complexity and 
far easier to implement than $\lambda$--calculus. 
\end{abstract}
%%
\input{comb-1}
\input{comb-2}
\input{comb-3}
\input{comb-4}
\input{comb-5}
\input{comb-6}
\input{comb-7}
\input{comb-8}
\input{comb-9}
\input{comb-10}
%%
\bibliography{gb,typology,kombi}
\end{document}
