Formal Derivation of the Longest Common Subsequence Problem with PAR Method

被引:0
|
作者
Sun, Lingyu [1 ]
Leng, Ming [1 ]
机构
[1] Jinggangshan Univ, Dept Comp Sci, Jian 343009, Jiangxi, Peoples R China
来源
2009 INTERNATIONAL CONFERENCE ON INFORMATION MANAGEMENT, INNOVATION MANAGEMENT AND INDUSTRIAL ENGINEERING, VOL 1, PROCEEDINGS | 2009年
关键词
D O I
10.1109/ICIII.2009.36
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Partition-and-Recur (PAR) method is a simple and useful formal method used to design and prove algorithmic programs. In this paper, we address that PAR method is really an effective formal method on solving Combinatorics problems. We formally derive Combinatorics problems by PAR method, which can not only simplify the process of algorithmic program's designing and correctness testifying, but also effectively improve the automatization, standardization and correctness of algorithmic program's designing by changing many creative labors to mechanized labors. Lastly, we develop typical algorithms of Combinatorics problem instances, longest common subsequence problem, and get accurate running result by RADL algorithmic program which derived by PAR method and can be transformed to C++ programs by the automatic program transforming system of PAR platform.
引用
收藏
页码:123 / 125
页数:3
相关论文
共 50 条
  • [41] A Multiobjective Approach to the Weighted Longest Common Subsequence Problem
    Becerra, David
    Mendivelso, Juan
    Pinzon, Yoan
    PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2012, 2012, : 64 - 74
  • [42] An efficient systolic algorithm for the longest common subsequence problem
    Lin, YC
    Chen, JC
    JOURNAL OF SUPERCOMPUTING, 1998, 12 (04): : 373 - 385
  • [43] The longest common subsequence problem a finite automata approach
    Melichar, L
    Polcar, T
    IMPLEMENTATION AND APPLICATION OF AUTOMATA, PROCEEDINGS, 2003, 2759 : 294 - 296
  • [44] An Efficient Systolic Algorithm for the Longest Common Subsequence Problem
    Yen-Chun Lin
    Jyh-Chian Chen
    The Journal of Supercomputing, 1998, 12 : 373 - 385
  • [45] An A* search algorithm for the constrained longest common subsequence problem
    Djukanovic, Marko
    Berger, Christoph
    Raidl, Gunther R.
    Blum, Christian
    INFORMATION PROCESSING LETTERS, 2021, 166
  • [46] FAST ALGORITHM FOR THE LONGEST-COMMON-SUBSEQUENCE PROBLEM
    MUKHOPADHYAY, A
    INFORMATION SCIENCES, 1980, 20 (01) : 69 - 82
  • [47] Probabilistic beam search for the longest common subsequence problem
    Blum, Christian
    Blesa, Maria J.
    ENGINEERING STOCHASTIC LOCAL SEARCH ALGORITHMS: DESIGNING, IMPLEMENTING AND ANALYZING EFFECTIVE HEURISTICS, 2007, 4638 : 150 - +
  • [48] Anytime algorithms for the longest common palindromic subsequence problem
    Djukanovic, Marko
    Raidl, Guenther R.
    Blum, Christian
    COMPUTERS & OPERATIONS RESEARCH, 2020, 114
  • [49] Cyclic longest common subsequence
    Naiman, Aaron E.
    Farber, Eliav
    Stein, Yossi
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2023, 15 (04)
  • [50] The longest common subsequence problem for arc-annotated sequences
    Jiang, T
    Lin, GH
    Ma, B
    Zhang, KZ
    COMBINATORIAL PATTERN MATCHING, 2000, 1848 : 154 - 165