کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952034 1442007 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Active symbols in grammars with valuations
ترجمه فارسی عنوان
نمادهای فعال در گرامرها با ارزیابی
کلمات کلیدی
زبان رسمی، سیستم های رسمی الهام گرفته از بیولوژیکی، پیچیدگی توصیفی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Grammars with valuations are context-free rewriting mechanisms where the derivation process is controlled by a recursive function that evaluates strings. They have been introduced by Jürgen Dassow as models for the molecular replication process taking into account its selective character. A symbol is active in a grammar with valuation if it can be rewritten non-identically. This paper studies the effect of restricting the number of active symbols in grammars with valuations and several variants thereof to their generative power. It is investigated in which cases the number of active symbols induces infinite strict hierarchies and when the hierarchies collapse. The induced language families are compared among one another.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 682, 19 June 2017, Pages 42-48
نویسندگان
,