کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334374 | 690402 | 2005 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Completions in measure of languages and related combinatorial problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider measures of languages induced by Bernoulli distributions on the letters of a given alphabet. Of particular interest are languages having a measure equal to 1 with respect to all positive Bernoulli distributions (Bernoulli sets). The main object of the paper is to study conditions ensuring that a given language has a finite Bernoulli completion, i.e., it is included in a finite Bernoulli set. Some characterizations of languages having finite Bernoulli completions are given. In the case of a two-letter alphabet it is shown that one can decide whether a finite language has a finite Bernoulli completion or not. Moreover, any finite code over a two-letter alphabet has a finite Bernoulli completion. Finally, we prove that two finite languages have the same measure with respect to all Bernoulli distributions if and only if each of the two languages can be obtained from the other by using a finite number of times three suitable measure-invariant transformations.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 330, Issue 1, 31 January 2005, Pages 35-57
Journal: Theoretical Computer Science - Volume 330, Issue 1, 31 January 2005, Pages 35-57
نویسندگان
Arturo Carpi, Aldo de Luca,