Call for Paper - January 2024 Edition
IJCA solicits original research papers for the January 2024 Edition. Last date of manuscript submission is December 20, 2023. Read More

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

Print
PDF
 
Download Full Text
International Journal of Computer Applications
© 2012 by IJCA Journal
Volume 45 - Number 22
Year of Publication: 2012
Authors:
Pragya Shukla
Sanjiv Tokekar
Suresh Jain
10.5120/7083-9748

Pragya Shukla, Sanjiv Tokekar and Suresh Jain. Article: Finding Fuzzy Reasoning Path on Fuzzy Deduction Graph using Parallel CYK Algorithm on a PRAM model. International Journal of Computer Applications 45(22):31-40, May 2012. Full text available. BibTeX

@article{key:article,
	author = {Pragya Shukla and Sanjiv Tokekar and Suresh Jain},
	title = {Article: Finding Fuzzy Reasoning Path on Fuzzy Deduction Graph using Parallel CYK Algorithm on a PRAM model},
	journal = {International Journal of Computer Applications},
	year = {2012},
	volume = {45},
	number = {22},
	pages = {31-40},
	month = {May},
	note = {Full text available}
}

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

  • 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
  • C. L. Liu, "Elements of Discrete Mathematics", Third Edition, McGraw Hill Internationa Editions, 1985.
  • 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.
  • 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.
  • F. Hayes-Roth, "Rule-based Systems", Commun. ACM. vol. 28, no. 9, pp. 921-932, Sept. 1985.
  • 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.
  • Elaine Rich,Kevin Knight, "Artificial Intelligence", Second Edition, Tata McGraw-Hill Editions, 1991.
  • Ahmad M. Ibrahim, Introduction to Applied Fuzzy Electronics, Prentice-Hall of India, 1999.
  • L. Zadeh, "Fuzzy logic," IEEE Comp. Mag. , vol. 21, no. 4, pp. 83-93, Apr. 1988.
  • C. C. Yang, "Deduction graph: An algorithm and Application," IEEE Trans. Software Eng. , vol. 15, no. 1, pp. 60-67, Jan. 1989
  • 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.
  • A. Kandel, Fuzzy Mathematical Techniques with Applications. Reading, MA:Addison-Wesley,1986.
  • Corman, Leiserson, Rivest, Stein, "Introduction to Algorithms", Second Edition, PHI Pub. , 2006.
  • A. Gibbons and W. Rytter, Efficient Parallel Algorithms,Cambridge University Press, Cambridge, UK, 1988.
  • Thomas A. Sdkamp, "An Introduction to the Theory of Computer Science, Languages and Machines," Third Edition,Pearson Education, 2006.
  • 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.
  • 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.
  • 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.