کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332513 | 687662 | 2005 | 25 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A probabilistic model of computing with words
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Computing in the traditional sense involves inputs with strings of numbers and symbols rather than words, where words mean probability distributions over input alphabet, and are different from the words in classical formal languages and automata theory. In this paper our goal is to deal with probabilistic finite automata (PFAs), probabilistic Turing machines (PTMs), and probabilistic context-free grammars (PCFGs) by inputting strings of words (probability distributions). Specifically, (i) we verify that PFAs computing strings of words can be implemented by means of calculating strings of symbols (Theorem 1); (ii) we elaborate on PTMs with input strings of words, and particularly demonstrate by describing Example 2 that PTMs computing strings of words may not be directly performed through only computing strings of symbols, i.e., Theorem 1 may not hold for PTMs; (iii) we study PCFGs and thus PRGs with input strings of words, and prove that Theorem 1 does hold for PCFRs and PRGs (Theorem 2); a characterization of PRGs in terms of PFAs, and the equivalence between PCFGs and their Chomsky and Greibach normal forms, in the sense that the inputs are strings of words, are also presented. Finally, the main results obtained are summarized, and a number of related issues for further study are raised.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 70, Issue 2, March 2005, Pages 176-200
Journal: Journal of Computer and System Sciences - Volume 70, Issue 2, March 2005, Pages 176-200
نویسندگان
Daowen Qiu, Huaiqing Wang,