Vol. 4 No. 1 (2024): Issue 4
Articles

Syntactic Parsing through Cocke-Kasami-Younger Algorithm

pdf
  • Hassan Zainal,
  • Mei Ling Tan,
  • Raj Kumar
Hassan Zainal
Faculty of Computer Science, Universiti Malaysia Kelantan
Mei Ling Tan
Centre for Computational Linguistics, Universiti Malaysia Pahang
Raj Kumar
Institute of Information Technology, Universiti Tun Hussein Onn Malaysia

Published 2024-11-08

Keywords

  • Syntactic Parsing,
  • Natural Language Processing,
  • Machine Translation,
  • Dynamic Programming,
  • Parsing Performance

How to Cite

Zainal, H., Tan, M. L., & Kumar, R. (2024). Syntactic Parsing through Cocke-Kasami-Younger Algorithm. Generative Artificial Intelligence Research, 4(1). Retrieved from https://ojs.mri-pub.com/index.php/GAIR/article/view/108

Abstract

Syntactic parsing is a fundamental task in natural language processing with applications ranging from machine translation to information retrieval. Despite significant advancements, existing parsing algorithms face challenges in handling complex sentence structures efficiently. This paper addresses the limitations of current research by proposing a novel approach based on the Cocke-Kasami-Younger algorithm. Our innovative method improves parsing accuracy and computational efficiency by incorporating dynamic programming techniques. By integrating syntactic analysis and structural parsing, our work presents a promising direction for enhancing parsing performance in various natural language processing applications.

pdf

References

  1. G. Glavas and I. Vulic, "Is Supervised Syntactic Parsing Beneficial for Language Understanding Tasks? An Empirical Investigation," in Conference of the European Chapter of the Association for Computational Linguistics, 2020.
  2. L. Zhang et al., "Adapting Unsupervised Syntactic Parsing Methodology for Discourse Dependency Parsing," in Annual Meeting of the Association for Computational Linguistics, 2021.
  3. D. Anastasyev et al., "EXPLORING PRETRAINED MODELS FOR JOINT MORPHO-SYNTACTIC PARSING OF RUSSIAN," in Computational Linguistics and Intellectual Technologies, 2020.
  4. A. More et al., "Joint Transition-Based Models for Morpho-Syntactic Parsing: Parsing Strategies for MRLs and a Case Study from Modern Hebrew," in Transactions of the Association for Computational Linguistics, 2019.
  5. E. Biau et al., "Beat Gestures and Syntactic Parsing: An ERP Study," in Language Learning, 2018.
  6. A. Stehnii, "Generation of code from text description with syntactic parsing and Tree2Tree model," 2018.
  7. B. Plank, "Keystroke dynamics as signal for shallow syntactic parsing," in International Conference on Computational Linguistics, 2016.
  8. C. Gómez-Rodríguez et al., "How important is syntactic parsing accuracy? An empirical evaluation on rule-based sentiment analysis," in Artificial Intelligence Review, 2017.
  9. Y. Pinter et al., "Syntactic Parsing of Web Queries with Question Intent," in North American Chapter of the Association for Computational Linguistics, 2016.
  10. D. Kozen, "The Cocke—Kasami—Younger Algorithm," in Proceedings, 1977, pp. 191-197.
  11. B. Patrut and I. Boghian, "A Delphi Application for the Syntactic and Lexical Analysis of a Phrase Using Cocke, Kasami and Younger Algorithm," in Proceedings, 2010, pp. 119-126.
  12. Wijanarto et al., "Gentree of Tool for Syntactic Analysis Based On Younger Cocke Kasami Algorithm," Journal of Arabic and Islamic Studies, vol. 2, pp. 37-51, 2017.
  13. V. Makarov, "Cocke-Younger-Kasami-Schwartz-Zippel algorithm and relatives," arXiv.org, vol. abs/2212.03861, 2022.
  14. M. Bortin, "A formalisation of the Cocke-Younger-Kasami algorithm," Arch. Formal Proofs, vol. 2016, 2016.
  15. D. E. Cahyani et al., "Indonesian Parsing using Probabilistic Context-Free Grammar (PCFG) and Viterbi-Cocke Younger Kasami (Viterbi-CYK)," in 2020 3rd International Seminar on Research of Information Technology and Intelligent Systems (ISRITI), 2020, pp. 56-61.
  16. H. Molina-Lozano, "A new fast fuzzy Cocke–Younger–Kasami algorithm for DNA strings analysis," International Journal of Machine Learning and Cybernetics, vol. 2, pp. 209-218, 2011.
  17. H. Molina-Lozano, "A Fast Fuzzy Cocke-Younger-Kasami Algorithm for DNA and RNA Strings Analysis," in Mexican International Conference on Artificial Intelligence, 2010, pp. 80-91.
  18. J. Oncina, "The Cocke-Younger-Kasami algorithm for cyclic strings," in Proceedings of 13th International Conference on Pattern Recognition, 1996, pp. 413-416 vol.2.
  19. Z. Luo, H. Yan, and X. Pan, ‘Optimizing Transformer Models for Resource-Constrained Environments: A Study on Model Compression Techniques’, Journal of Computational Methods in Engineering Applications, pp. 1–12, Nov. 2023, doi: 10.62836/jcmea.v3i1.030107.
  20. H. Yan and D. Shao, ‘Enhancing Transformer Training Efficiency with Dynamic Dropout’, Nov. 05, 2024, arXiv: arXiv:2411.03236. doi: 10.48550/arXiv.2411.03236.
  21. H. Yan, ‘Real-Time 3D Model Reconstruction through Energy-Efficient Edge Computing’, Optimizations in Applied Machine Learning, vol. 2, no. 1, 2022.
  22. W. Cui, J. Zhang, Z. Li, H. Sun, and D. Lopez, ‘Kamalika Das, Bradley Malin, and Sricharan Kumar. 2024. Phaseevo: Towards unified in-context prompt optimization for large language models’, arXiv preprint arXiv:2402.11347.
  23. A. Sinha, W. Cui, K. Das, and J. Zhang, ‘Survival of the Safest: Towards Secure Prompt Optimization through Interleaved Multi-Objective Evolution’, Oct. 12, 2024, arXiv: arXiv:2410.09652. doi: 10.48550/arXiv.2410.09652.
  24. J. Zhang, W. Cui, Y. Huang, K. Das, and S. Kumar, ‘Synthetic Knowledge Ingestion: Towards Knowledge Refinement and Injection for Enhancing Large Language Models’, Oct. 12, 2024, arXiv: arXiv:2410.09629. doi: 10.48550/arXiv.2410.09629.
  25. Y.-S. Cheng, P.-M. Lu, C.-Y. Huang, and J.-J. Wu, ‘Encapsulation of lycopene with lecithin and α-tocopherol by supercritical antisolvent process for stability enhancement’, The Journal of Supercritical Fluids, vol. 130, pp. 246–252, 2017.
  26. P.-M. Lu, ‘Potential Benefits of Specific Nutrients in the Management of Depression and Anxiety Disorders’, Advanced Medical Research, vol. 3, no. 1, pp. 1–10, 2024.
  27. P.-M. Lu, ‘Exploration of the Health Benefits of Probiotics Under High-Sugar and High-Fat Diets’, Advanced Medical Research, vol. 2, no. 1, pp. 1–9, 2023.
  28. P.-M. Lu, ‘The Preventive and Interventional Mechanisms of Omega-3 Polyunsaturated Fatty Acids in Krill Oil for Metabolic Diseases’, Journal of Computational Biology and Medicine, vol. 4, no. 1, 2024.
  29. C. Li and Y. Tang, ‘The Factors of Brand Reputation in Chinese Luxury Fashion Brands’, Journal of Integrated Social Sciences and Humanities, pp. 1–14, 2023.
  30. Y. Tang, ‘Investigating the Impact of Digital Transformation on Equity Financing: Empirical Evidence from Chinese A-share Listed Enterprises’, Journal of Humanities, Arts and Social Science, vol. 8, no. 7, pp. 1620–1632, 2024.
  31. Y. Tang and C. Li, ‘Exploring the Factors of Supply Chain Concentration in Chinese A-Share Listed Enterprises’, Journal of Computational Methods in Engineering Applications, pp. 1–17, 2023.
  32. C. Li and Y. Tang, ‘Emotional Value in Experiential Marketing: Driving Factors for Sales Growth–A Quantitative Study from the Eastern Coastal Region’, Economics & Management Information, pp. 1–13, 2024.
  33. Y. C. Li and Y. Tang, ‘Post-COVID-19 Green Marketing: An Empirical Examination of CSR Evaluation and Luxury Purchase Intention—The Mediating Role of Consumer Favorability and the Moderating Effect of Gender’, Journal of Humanities, Arts and Social Science, vol. 8, no. 10, pp. 2410–2422, 2024.
  34. Y. Tang and K. Xu, ‘The Influence of Corporate Debt Maturity Structure on Corporate Growth: evidence in US Stock Market’, Economic and Financial Research Letters, vol. 1, no. 1, 2024.
  35. C. Kim, Z. Zhu, W. B. Barbazuk, R. L. Bacher, and C. D. Vulpe, ‘Time-course characterization of whole-transcriptome dynamics of HepG2/C3A spheroids and its toxicological implications’, Toxicology Letters, vol. 401, pp. 125–138, 2024.
  36. J. Shen et al., ‘Joint modeling of human cortical structure: Genetic correlation network and composite-trait genetic correlation’, NeuroImage, vol. 297, p. 120739, 2024.
  37. K. F. Faridi et al., ‘Factors associated with reporting left ventricular ejection fraction with 3D echocardiography in real‐world practice’, Echocardiography, vol. 41, no. 2, p. e15774, Feb. 2024, doi: 10.1111/echo.15774.
  38. Y. Gan and D. Zhu, ‘The Research on Intelligent News Advertisement Recommendation Algorithm Based on Prompt Learning in End-to-End Large Language Model Architecture’, Innovations in Applied Engineering and Technology, pp. 1–19, 2024.
  39. H. Zhang, D. Zhu, Y. Gan, and S. Xiong, ‘End-to-End Learning-Based Study on the Mamba-ECANet Model for Data Security Intrusion Detection’, Journal of Information, Technology and Policy, pp. 1–17, 2024.
  40. D. Zhu, Y. Gan, and X. Chen, ‘Domain Adaptation-Based Machine Learning Framework for Customer Churn Prediction Across Varing Distributions’, Journal of Computational Methods in Engineering Applications, pp. 1–14, 2021.
  41. D. Zhu, X. Chen, and Y. Gan, ‘A Multi-Model Output Fusion Strategy Based on Various Machine Learning Techniques for Product Price Prediction’, Journal of Electronic & Information Systems, vol. 4, no. 1.
  42. X. Chen, Y. Gan, and S. Xiong, ‘Optimization of Mobile Robot Delivery System Based on Deep Learning’, Journal of Computer Science Research, vol. 6, no. 4, pp. 51–65, 2024.
  43. Y. Gan, J. Ma, and K. Xu, ‘Enhanced E-Commerce Sales Forecasting Using EEMD-Integrated LSTM Deep Learning Model’, Journal of Computational Methods in Engineering Applications, pp. 1–11, 2023.
  44. F. Zhang et al., ‘Natural mutations change the affinity of μ-theraphotoxin-Hhn2a to voltage-gated sodium channels’, Toxicon, vol. 93, pp. 24–30, 2015.
  45. Y. Gan and X. Chen, ‘The Research on End-to-end Stock Recommendation Algorithm Based on Time-frequency Consistency’, Advances in Computer and Communication, vol. 5, no. 4, 2024.
  46. Z. Zhao, P. Ren, and Q. Yang, ‘Student self-management, academic achievement: Exploring the mediating role of self-efficacy and the moderating influence of gender insights from a survey conducted in 3 universities in America’, Apr. 17, 2024, arXiv: arXiv:2404.11029. doi: 10.48550/arXiv.2404.11029.
  47. Z. Zhao, P. Ren, and M. Tang, ‘Analyzing the Impact of Anti-Globalization on the Evolution of Higher Education Internationalization in China’, Journal of Linguistics and Education Research, vol. 5, no. 2, pp. 15–31, 2022.
  48. M. Tang, P. Ren, and Z. Zhao, ‘Bridging the gap: The role of educational technology in promoting educational equity’, The Educational Review, USA, vol. 8, no. 8, pp. 1077–1086, 2024.
  49. P. Ren, Z. Zhao, and Q. Yang, ‘Exploring the Path of Transformation and Development for Study Abroad Consultancy Firms in China’, Apr. 17, 2024, arXiv: arXiv:2404.11034. doi: 10.48550/arXiv.2404.11034.
  50. P. Ren and Z. Zhao, ‘Parental Recognition of Double Reduction Policy, Family Economic Status And Educational Anxiety: Exploring the Mediating Influence of Educational Technology Substitutive Resource’, Economics & Management Information, pp. 1–12, 2024.
  51. Z. Zhao, P. Ren, and M. Tang, ‘How Social Media as a Digital Marketing Strategy Influences Chinese Students’ Decision to Study Abroad in the United States: A Model Analysis Approach’, Journal of Linguistics and Education Research, vol. 6, no. 1, pp. 12–23, 2024.
  52. J. Lei, ‘Efficient Strategies on Supply Chain Network Optimization for Industrial Carbon Emission Reduction’, JCMEA, pp. 1–11, Dec. 2022.
  53. J. Lei, ‘Green Supply Chain Management Optimization Based on Chemical Industrial Clusters’, IAET, pp. 1–17, Nov. 2022, doi: 10.62836/iaet.v1i1.003.
  54. J. Lei and A. Nisar, ‘Investigating the Influence of Green Technology Innovations on Energy Consumption and Corporate Value: Empirical Evidence from Chemical Industries of China’, Innovations in Applied Engineering and Technology, pp. 1–16, 2023.
  55. J. Lei and A. Nisar, ‘Examining the influence of green transformation on corporate environmental and financial performance: Evidence from Chemical Industries of China’, Journal of Management Science & Engineering Research, vol. 7, no. 2, pp. 17–32, 2024.
  56. Y. Jia and J. Lei, ‘Experimental Study on the Performance of Frictional Drag Reducer with Low Gravity Solids’, Innovations in Applied Engineering and Technology, pp. 1–22, 2024.