Advertisement
Published in:
2014 | OriginalPaper | Chapter
Unification and Logarithmic Space
Authors : Clément Aubert, Marc Bagnol
Published in: Rewriting and Typed Lambda Calculi
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 inspired from proof theory and more specifically linear logic and Geometry of Interaction.
We show how unification can be used to build a model of computation by means of specific subalgebras associated to finite permutation groups.
We then prove that whether an observation (the algebraic counterpart of a program) accepts a word can be decided within logarithmic space. We also show that the construction can naturally encode pointer machines, an intuitive way of understanding logarithmic space computing.