Published in

Springer, Lecture Notes in Computer Science, p. 39-57, 2014

DOI: 10.1007/978-3-319-12736-1_3

Links

Tools

Export citation

Search in Google Scholar

Logic Programming and Logarithmic Space

Proceedings article published in 2014 by Clément Aubert ORCID, Marc Bagnol, Paolo Pistone, Thomas Seiller ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Red circle
Preprint: archiving forbidden
Orange circle
Postprint: archiving restricted
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

Abstract

We present an algebraic view on logic programming, related to proof theory and more specifically linear logic and geometry of interaction. Within this construction, a characterization of logspace (deterministic and non-deterministic) computation is given via a syntactic restriction, using an encoding of words that derives from proof theory. We show that the acceptance of a word by an observation (the counterpart of a program in the encoding) can be decided within logarithmic space, by reducing this problem to the acyclicity of a graph. We show moreover that observations are as expressive as two-ways multi-head finite automata, a kind of pointer machine that is a standard model of logarithmic space computation.