Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Unification and Logarithmic Space
verfasst von : Clément Aubert, Marc Bagnol
Erschienen in: Rewriting and Typed Lambda Calculi
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.