کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6873771 1440705 2018 27 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Proofs of proximity for context-free languages and read-once branching programs
ترجمه فارسی عنوان
اثبات نزدیکی برای زبان های غیر متنی و برنامه های یکپارچه خواندن
کلمات کلیدی
آزمایش املاک، سیستم های اثبات احتمالی، اثبات های تعاملی،
ترجمه چکیده
ما اثبات نزدیکی را برای دو کلاس طبیعی خواص ساخته می کنیم: (1) زبان های بدون متن و (2) زبان های پذیرفته شده با برنامه های کوچک شاخه ای خواندن. نتایج اصلی ما عبارتند از:
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
اثبات نزدیکی برای زبان های غیر متنی و برنامه های یکپارچه خواندن
چکیده انگلیسی
We construct proofs of proximity for two natural classes of properties: (1) context-free languages, and (2) languages accepted by small read-once branching programs. Our main results are:
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 261, Part 2, August 2018, Pages 175-201
نویسندگان
, , ,