Unification and Logarithmic Space

DOI10.1007/978-3-319-08918-8_6MaRDI QIDQ5170809zbMATHOpenAlexFDO

Authors Clément Aubert, Marc Bagnol

Publication date 24 July 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.4327

zbMATH Keywords

proof theorylogarithmic spacegeometry of interactionunificationpointer machinesimplicit complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Logic programming (68N17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Grammars and rewriting systems (68Q42) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Abstract: 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 permutations 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 represent pointer machines, an intuitive way of understanding logarithmic space computing.

Recommendations

• scientific article; zbMATH DE number 6917940
• On the logic of unification
• Algebraic and logical aspects of unification
• scientific article; zbMATH DE number 1777339
• Unification in commutative theories
• Unambiguous functions in logarithmic space
• Choiceless Logarithmic Space
• \(F\)-theory and unification
• Publication:4723704
• Unifications, deunifications, and their complexity

Cited in

(3)

• Logarithmic space and permutations
• Unary resolution: characterizing \textsc{Ptime}
• scientific article; zbMATH DE number 6917940 (Why is no real title available?)

This page was built for publication: Unification and Logarithmic Space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5170809)