کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426377 686047 2016 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Logarithmic space and permutations
ترجمه فارسی عنوان
فضای لگاریتمی و جایگشت
کلمات کلیدی
منطق خطی؛ پیچیدگی؛ هندسه تعامل؛ دستگاه اشاره گر؛ اتوماتای متناهی؛ فضای لگاریتمی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

In a recent work, Girard proposed a new and innovative approach to computational complexity based on the proofs-as-programs correspondence. In a previous paper, the authors showed how Girard's proposal succeeds in obtaining a new characterization of co-NL languages as a set of operators acting on a Hilbert Space. In this paper, we extend this work by showing that it is also possible to define a set of operators characterizing the class L of logarithmic space languages.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 248, June 2016, Pages 2–21
نویسندگان
, ,