کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10225763 | 1701211 | 2018 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Grammatical characterizations of NPDAs and VPDAs with counters
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We give a characterization of NPDAs with reversal-bounded counters (NPCMs) in terms of context-free grammars with monotonic counters. We show that the grammar characterization can be used to give simple proofs of previously known results such as the semilinearity of the Parikh map of any language accepted by an NPCM. We prove a Chomsky-Schutzenberger-like theorem: A language L is accepted by an NPCM if and only if there is a kâ¥1 and an alphabet Σ containing at least k distinguished symbols, p1,...,pk, such that L=h(Dâ©Ek(R)) for some homomorphism h, Dyck language DâΣâ, and regular set RâΣâ, where Ek(R)={w|wâR,|w|p1=â¯=|w|pk}. We also give characterizations of other machine models, such as visibly pushdown automata with reversal-bounded counters (VPCMs). We then investigate the complexity of some decision problems concerning these grammatical models. Finally, we introduce other grammatical models equivalent to NPCM.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 746, 25 October 2018, Pages 136-150
Journal: Theoretical Computer Science - Volume 746, 25 October 2018, Pages 136-150
نویسندگان
Oscar H. Ibarra,