Unification and Logarithmic Space

Clément Aubert & Marc Bagnol
We present an algebraic characterization of the complexity classes Logspace and Nlogspace, using an algebra with a composition law based on unification. This new bridge between unification and complexity classes is rooted in proof theory and more specifically linear logic and geometry of interaction. We show how to build a model of computation in the unification algebra and then, by means of a syntactic representation of finite permutations in the algebra, we prove that whether...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.