کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657758 | 690565 | 2005 | 32 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Sublogarithmic ambiguity
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Context-free grammars and languages with infinite ambiguity can be distinguished by the growth rate of their ambiguity with respect to the length of the words. So far the least growth rate known for a divergent inherent ambiguity function was logarithmic. Roughly speaking we show that it is possible to stay below any computable function. More precisely let f:NâN be an arbitrary computable divergent total non-decreasing function. Then there is a context-free language L with a divergent inherent ambiguity function g below f, i.e., g(n)⩽f(n) for each nâN. This result is an immediate consequence of two other results which are of independent interest. The first result says that there is a linear context-free grammar G with so called unambiguous turn position whose ambiguity function is below f. The second one states that any ambiguity function of a cycle-free context-free grammar is an inherent ambiguity function of some context-free language.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 345, Issues 2â3, 22 November 2005, Pages 473-504
Journal: Theoretical Computer Science - Volume 345, Issues 2â3, 22 November 2005, Pages 473-504
نویسندگان
Klaus Wich,