收藏切换
Isabelle-Driven Modeling and Automated Verification of Search Tree Algorithms
收藏切换
Zhengkang Zuo1, 2, 3, Xiaoying Zhu1, Zhen You1, Changjing Wang1, 2, 3, *
Journal of Computer Research and Development | 2026, 63(5) : 1117 - 1138
Less
收藏切换
Journal of Computer Research and Development | 2026, 63(5): 1117-1138
• Special Issue on Security and Trustworthiness for AI-Enabled Human-Cyber-Physical Systems •
Isabelle-Driven Modeling and Automated Verification of Search Tree Algorithms
Full
Zhengkang Zuo1, 2, 3, Xiaoying Zhu1, Zhen You1, Changjing Wang1, 2, 3, *
Affiliations
  • 1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
  • 2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University) , Nanchang 330022
  • 3Language Intelligence Research Center (Jiangxi Normal University) , Nanchang 330022
  • born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

    born in 2001. Master candidate. Student member of CCF. Her main research interest includes formal method

    born in 1982. PhD, associate professor, master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

    born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

About Author:

born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

born in 2001. Master candidate. Student member of CCF. Her main research interest includes formal method

born in 1982. PhD, associate professor, master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

Published: 2026-05-01 doi: 10.7544/issn1000-1239.202550899
Outline
收藏切换

Search tree algorithms are widely used in areas such as database indexing, compiler design, and file systems, where the functional correctness of these algorithms is a critical factor in ensuring software reliability. However, traditional development process faces two major challenges: first, algorithm design often lacks rigorous mathematical modeling, causing correctness verification to remain at an empirical level; second, existing verification approaches heavily rely on manual or interactive theorem proving, making the verification complexity grow exponentially with increasing algorithm scale. To address the above issues, an Isabelle-driven method for modeling and automated verification of search tree algorithms is proposed. This method builds on a formally verified functional modeling library to construct a modular modeling strategy that supports various search tree structures, and introduces a formal specification-driven framework for automatically synthesizing algorithmic code. Developers are required to supply only minimal functional expressions to complete the implementation. In addition, a reusable lemma library has been developed to support an automated block-wise verification strategy, significantly reducing verification costs. Furthermore, a method for generating functional executable programs is proposed. Experimental evaluation using a representative case study demonstrates that the proposed method substantially reduces verification costs. Compared with interactive verification approaches, the average reductions in code size and manual effort are 88.60% and 61.51%, respectively; compared with generative AI plus interactive verification methods, the average reductions in code size and manual effort are 88.09% and 41.76%, respectively. Overall, the proposed framework provides a systematic and highly automated solution for the formal verification of complex data structure algorithms in specific domains, while also offering a feasible pathway and methodological support for generating correct functional executable programs.

search tree  /  Isabelle theorem prover  /  functional modeling  /  automated verification  /  program generation
左正康, 朱小影, 游珍, 王昌晶. Isabelle驱动的搜索树类算法建模及自动化验证. 计算机研究与发展, 2026 , 63 (5) : 1117 -1138 . DOI: 10.7544/issn1000-1239.202550899
Zhengkang Zuo, Xiaoying Zhu, Zhen You, Changjing Wang. Isabelle-Driven Modeling and Automated Verification of Search Tree Algorithms[J]. Journal of Computer Research and Development, 2026 , 63 (5) : 1117 -1138 . DOI: 10.7544/issn1000-1239.202550899
Year 2026 volume 63 Issue 5
70
34
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202550899
  • Receive Date:2025-12-15
  • Online Date:2026-11-17
  • Published:2026-05-01
Article Data
Affiliations
History
  • Received:2025-12-15
  • Revised:2026-03-05
Affiliations
    1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
    2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University) , Nanchang 330022
    3Language Intelligence Research Center (Jiangxi Normal University) , Nanchang 330022
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202550899
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT