キノシタ ヨシキ   Kinoshita Yoshiki
  木下 佳樹
   所属   神奈川大学  情報学部 計算機科学科
    神奈川大学大学院  理学研究科 理学専攻(情報科学領域)
   職種   教授
言語種別 日本語
発行・発表の年月 2000
形態種別 学術雑誌
査読 査読あり
標題 A general completeness result in refinement
執筆形態 共著
掲載誌名 , in "Recent Trends in Algebraic Development Techniques" (eds. Didier Bert, Christine Choppy and Peter D. Mosses) (Springer-Verlag)
巻・号・頁 1827,201-218頁
著者・共著者 Yoshiki Kinoshita and John A.power
概要 In a paper in 1986, Hoare, He and Sanders proposed a formulation of refinement for a system equivalent to the ν-calculus using a relation based semantics. To give a proof method to show that one program is a refinement of another, they introduced downward simulation and upward simulation, but the proof method based upon either of them is not complete with respect to their notion of refinement, so they claimed “joint” completeness based upon both notions of simulation with respect to their notion of refinement. We give a new definition of refinement in terms of structure respecting lax transformations, and show that the proof method based upon downward simulation is complete with respect to this notion of refinement. Although our theory works for the ν-calculus, we present the result for the μ-calculus to make the presentation simpler. We use results in enriched category theory to show this, and the central notion here is that of algebraic structure on locally ordered categories, not on sets. Our definition of refinement is neither a restriction nor a generalisation of Hoare, He and Sanders’ definition, but we include all their important examples.