کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426745 | 686259 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Language equivalence of probabilistic pushdown automata
ترجمه فارسی عنوان
همبستگی زبان از اتوماتای فشرده سازی احتمالی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the language equivalence problem for probabilistic pushdown automata (pPDA) and their subclasses. We show that the problem is interreducible with the multiplicity equivalence problem for context-free grammars, the decidability of which has been open for several decades. Interreducibility also holds for pPDA with one control state.In contrast, for the case of a one-letter input alphabet we show that pPDA language equivalence (and hence multiplicity equivalence of context-free grammars) is in PSPACE and at least as hard as the polynomial identity testing problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 237, October 2014, Pages 1–11
Journal: Information and Computation - Volume 237, October 2014, Pages 1–11
نویسندگان
Vojtěch Forejt, Petr Jančar, Stefan Kiefer, James Worrell,