CFP last date
21 October 2024
Reseach Article

Finding Fuzzy Reasoning Path on Fuzzy Deduction Graph using Parallel CYK Algorithm on a PRAM model

by Pragya Shukla, Sanjiv Tokekar, Suresh Jain
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 45 - Number 22
Year of Publication: 2012
Authors: Pragya Shukla, Sanjiv Tokekar, Suresh Jain
10.5120/7083-9748

Pragya Shukla, Sanjiv Tokekar, Suresh Jain . Finding Fuzzy Reasoning Path on Fuzzy Deduction Graph using Parallel CYK Algorithm on a PRAM model. International Journal of Computer Applications. 45, 22 ( May 2012), 31-40. DOI=10.5120/7083-9748

@article{ 10.5120/7083-9748,
author = { Pragya Shukla, Sanjiv Tokekar, Suresh Jain },
title = { Finding Fuzzy Reasoning Path on Fuzzy Deduction Graph using Parallel CYK Algorithm on a PRAM model },
journal = { International Journal of Computer Applications },
issue_date = { May 2012 },
volume = { 45 },
number = { 22 },
month = { May },
year = { 2012 },
issn = { 0975-8887 },
pages = { 31-40 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume45/number22/7083-9748/ },
doi = { 10.5120/7083-9748 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:38:16.863955+05:30
%A Pragya Shukla
%A Sanjiv Tokekar
%A Suresh Jain
%T Finding Fuzzy Reasoning Path on Fuzzy Deduction Graph using Parallel CYK Algorithm on a PRAM model
%J International Journal of Computer Applications
%@ 0975-8887
%V 45
%N 22
%P 31-40
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper a new parallel version of finding the Fuzzy Reasoning Path (FRP) using the knowledge representation model, introduced by Chandwani & Chaudhari [1] known as Fuzzy Deduction Graph (FDG) is presented. In an FDG, a systematic method of finding the Fuzzy Reasoning Path (FRP) already exists, which is based on Dijkstra's shortest path framework [2]. Our FRP algorithm is conglomeration of CYK algorithm of parsing and FRP algorithm for fuzzy reasoning which generates the path with the greatest fuzzy value. In FDG the weights of edges are real numbers in the fuzzy interval [0-1]. The maximum of multiplication is obtained on weights instead of minimum of summation of weights [1]. CYK algorithm employs a bottom up approach with the principle of Dynamic Programming (DP) to determine the FRP from source node to the destination node. The concurrency and synchronization in finding FRP process are inherently maintained through parallel PRAM model of construct. We present a complete formulation along with analysis of parallel algorithm for finding FRP.

References
  1. M. Chandwani and N. S. Chaudhari, "Knowledge representation using fuzzy deduction graphs," IEEE Trans. Syst. , Man, Cybern. , vol. 26, no. 6 pp. 848-854, Dec. 1996
  2. C. L. Liu, "Elements of Discrete Mathematics", Third Edition, McGraw Hill Internationa Editions, 1985.
  3. M. Chandwani, M. Puranik and N. S. Chaudhari, "On CKY-Parsing of Context-Free Grammar in Parallel," IEEE region 10 Conference, Tencon, Australia, pp. 141-145, November 1992.
  4. M. Chandwani, N. S. Chaudhari, "Formulation and analysis of parallel context-free recognition and parsing on PARAM model," Elsevier Science, parallel Computing 22, 1996, 845-868.
  5. F. Hayes-Roth, "Rule-based Systems", Commun. ACM. vol. 28, no. 9, pp. 921-932, Sept. 1985.
  6. Hisao Ishibuchi,Takashi Yamamoto, "Rule Weight Specification in Fuzzy Rule-Based Classification Systems," IEEE Trans. Fuzzy Syst. ,vol. 13,No. 4 pp. 428-443,Aug. 2005.
  7. Elaine Rich,Kevin Knight, "Artificial Intelligence", Second Edition, Tata McGraw-Hill Editions, 1991.
  8. Ahmad M. Ibrahim, Introduction to Applied Fuzzy Electronics, Prentice-Hall of India, 1999.
  9. L. Zadeh, "Fuzzy logic," IEEE Comp. Mag. , vol. 21, no. 4, pp. 83-93, Apr. 1988.
  10. C. C. Yang, "Deduction graph: An algorithm and Application," IEEE Trans. Software Eng. , vol. 15, no. 1, pp. 60-67, Jan. 1989
  11. C. C. Yang, J. J. Chen, and H. L. Chau, "Algorithms for constructing minimal deduction graphs," IEEE Trans. Software Eng. , vol. 15, no. 6, pp. 760-771, June 1989.
  12. A. Kandel, Fuzzy Mathematical Techniques with Applications. Reading, MA:Addison-Wesley,1986.
  13. Corman, Leiserson, Rivest, Stein, "Introduction to Algorithms", Second Edition, PHI Pub. , 2006.
  14. A. Gibbons and W. Rytter, Efficient Parallel Algorithms,Cambridge University Press, Cambridge, UK, 1988.
  15. Thomas A. Sdkamp, "An Introduction to the Theory of Computer Science, Languages and Machines," Third Edition,Pearson Education, 2006.
  16. P. Shukla, M. Chandwani, "Taxonomy of Fuzzy Deduction Graph," International Journal of Computer and Electronics Engineering ( IJCEE), Vol. 3, no. 1, Page 99-115, 2010.
  17. S. M. Chen,"Representing knowledge using fuzzy deduction graphs based on fuzzy numbers, " Proceedings of the 2003 Joint Conference on AI, Fuzzy System, and Grey System, Taipai, Taiwan, Republic of China, Dec. 2003.
  18. Z. H. Tan, " Fuzzy Metagraph and Its Combination with the indexing Approach in Rule-based Systems," IEEE Transaction knowledge and Data Engineering, vol. 18,no. 6, pp. 829-841, June, 2006.
Index Terms

Computer Science
Information Sciences

Keywords

Deduction Graph Fuzzy Deduction Graphs Rule-based Systems Horn Clauses Fuzzy Reasoning Path Cyk-algorithm Dynamic Programming Pram Model Wram Model Knowledge-base System