Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Extended Floyd-Hoare Logic over Relational Nominative Data

  • Conference paper
  • First Online:
Information and Communication Technologies in Education, Research, and Industrial Applications (ICTERI 2017)

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 826))

  • 352 Accesses

Abstract

The classical Floyd-Hoare logic is defined for the case of total pre- and postconditions and partial programs (i.e. programs can be undefined on some input data, but conditions must be defined on all data). In this paper we propose an extension of this logic for the case of partial conditions and partial programs over structured data. These data are based on two constructing primitives: naming and relational structuring and are called relational nominative data. They can conveniently represent many data structures used in programming. The semantics of the proposed logic is represented by special algebras of partial functions and predicates over relational nominative data. Operations of these algebras are called compositions. We present an inference system for the mentioned logic and propose an approach to its formalization in Mizar proof assistant. The obtained results can be used in software verification.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Research on using specialized external systems to increase computational power of the Mizar system is also conducted [19,20,21].

  2. 2.

    Due to the size, the MML is a subject of research on optimization of theorems and definitions [33]. It includes the improvement of legibility of proofs [34,35,36] and removing duplications.

References

  1. Floyd, R.: Assigning meanings to programs. Math. Asp. Comput. Sci. 19, 19–32 (1967)

    Article  MathSciNet  MATH  Google Scholar 

  2. Hoare, C.: An axiomatic basis for computer programming. Commun. ACM 12(10), 576–580 (1969)

    Article  MATH  Google Scholar 

  3. Apt, K.: Ten years of Hoare’s logic: a survey - part I. ACM Trans. Program. Lang. Syst. 3(4), 431–483 (1981). http://doi.acm.org/10.1145/357146.357150

    Article  MATH  Google Scholar 

  4. Hähnle, R.: Many-valued logic, partiality, and abstraction in formal specification languages. Log. J. IGPL 13(4), 415–433 (2005). http://dx.doi.org/10.1093/jigpal/jzi032

    Article  MathSciNet  MATH  Google Scholar 

  5. Jones, C.: Reasoning about partial functions in the formal development of programs. In: AVoCS 2005. Electronic Notes in Theoretical Computer Science, vol. 145, pp. 3–25. Elsevier (2006). https://doi.org/10.1016/j.entcs.2005.10.002

  6. Gries, D., Schneider, F.B.: Avoiding the undefined by underspecification. In: van Leeuwen, J. (ed.) Computer Science Today. LNCS, vol. 1000, pp. 366–373. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0015254

    Chapter  Google Scholar 

  7. Duzi, M.: Do we have to deal with partiality? Misc. Log. 5, 45–76 (2003)

    Google Scholar 

  8. Kryvolap, A., Nikitchenko, M., Schreiner, W.: Extending Floyd-Hoare logic for partial pre- and postconditions. In: Ermolayev, V., Mayr, H.C., Nikitchenko, M., Spivakovsky, A., Zholtkevych, G. (eds.) ICTERI 2013. CCIS, vol. 412, pp. 355–378. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03998-5_18

    Google Scholar 

  9. Nikitchenko, M., Kryvolap, A.: Properties of inference systems for Floyd-Hoare logic with partial predicates. Acta Electrotech. Inform. 13(4), 70–78 (2013)

    Article  Google Scholar 

  10. Skobelev, V., Nikitchenko, M., Ivanov, I.: On algebraic properties of nominative data and functions. In: Ermolayev, V., Mayr, H., Nikitchenko, M., Spivakovsky, A., Zholtkevych, G. (eds.) Communications in Computer and Information Science, ICTERI, vol. 469, pp. 117–138. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-13206-8_6

    Google Scholar 

  11. Nikitchenko, M., Shkilniak, S.: Mathematical logic and theory of algorithms. Publishing house of Taras Shevchenko National University of Kyiv, Ukraine (2008). (in Ukrainian)

    Google Scholar 

  12. Nikitchenko, M.: Composition-nominative aspects of address programming. Cybern. Syst. Anal. 45, 864 (2009). https://doi.org/10.1007/s10559-009-9159-4

    Article  MathSciNet  MATH  Google Scholar 

  13. Wiedijk, F. (ed.): The Seventeen Provers of the World. Foreword by Dana S. Scott. LNAI, vol. 3600. Springer, Heidelberg (2006). https://doi.org/10.1007/11542384

    MATH  Google Scholar 

  14. Gordon, M.: Mechanizing programming logics in higher order logic. In: Birtwistle, G., Subrahmanyam, P. (eds.) Current Trends in Hardware Verification and Automated Theorem Proving, pp. 387–439. Springer, New York (1989). https://doi.org/10.1007/978-1-4612-3658-0_10

    Chapter  Google Scholar 

  15. Von Wright, J., Hekanaho, J., Luostarinen, P., Langbacka, T.: Mechanizing some advanced refinement concepts. Form. Methods Syst. Des. 3(1), 49–81 (1993). https://doi.org/10.1007/BF01383984

    Article  MATH  Google Scholar 

  16. Bancerek, G., Byliński, C., Grabowski, A., Korniłowicz, A., Matuszewski, R., Naumowicz, A., Pa̧k, K., Urban, J.: Mizar: state-of-the-art and beyond. In: Kerber, M., Carette, J., Kaliszyk, C., Rabe, F., Sorge, V. (eds.) CICM 2015. LNCS (LNAI), vol. 9150, pp. 261–279. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-20615-8_17

    Chapter  Google Scholar 

  17. Grabowski, A., Korniłowicz, A., Naumowicz, A.: Four decades of Mizar. J. Autom. Reason. 55(3), 191–198 (2015). http://dx.doi.org/10.1007/s10817-015-9345-1

    Article  MathSciNet  MATH  Google Scholar 

  18. Trybulec, A.: Tarski Grothendieck set theory. Formaliz. Math. 1(1), 9–11 (1990)

    Google Scholar 

  19. Naumowicz, A.: Interfacing external CA systems for Gröbner bases computation in Mizar proof checking. Int. J. Comput. Math. 87(1), 1–11 (2010). http://dx.doi.org/10.1080/00207160701864459

    Article  MATH  Google Scholar 

  20. Naumowicz, A.: SAT-enhanced Mizar proof checking. In: Watt, S.M., Davenport, J.H., Sexton, A.P., Sojka, P., Urban, J. (eds.) CICM 2014. LNCS (LNAI), vol. 8543, pp. 449–452. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08434-3_37

    Chapter  Google Scholar 

  21. Naumowicz, A.: Automating Boolean set operations in Mizar proof checking with the aid of an external SAT solver. J. Autom. Reason. 55(3), 285–294 (2015). http://dx.doi.org/10.1007/s10817-015-9332-6

    Article  MathSciNet  MATH  Google Scholar 

  22. Korniłowicz, A.: On rewriting rules in Mizar. J. Autom. Reason. 50(2), 203–210 (2013). http://dx.doi.org/10.1007/s10817-012-9261-6

    Article  MathSciNet  MATH  Google Scholar 

  23. Korniłowicz, A.: Flexary connectives in Mizar. Comput. Lang. Syst. Struct. 44, 238–250 (2015). http://dx.doi.org/10.1016/j.cl.2015.07.002

    Google Scholar 

  24. Korniłowicz, A.: Definitional expansions in Mizar. J. Autom. Reason. 55(3), 257–268 (2015). http://dx.doi.org/10.1007/s10817-015-9331-7

    Article  MathSciNet  MATH  Google Scholar 

  25. Nelson, G., Oppen, D.C.: Fast decision procedures based on congruence closure. J. ACM 27, 356–364 (1980). http://doi.acm.org/10.1145/322186.322198

    Article  MathSciNet  MATH  Google Scholar 

  26. Grabowski, A., Korniłowicz, A., Schwarzweller, C.: Equality in computer proof-assistants. In: Ganzha, M., Maciaszek, L.A., Paprzycki, M. (eds.) Proceedings of the 2015 FedCSIS. Annals of Computer Science and Information Systems, vol. 5, pp. 45–54. IEEE (2015). https://doi.org/10.15439/2015F229

  27. Naumowicz, A., Byliński, C.: Improving Mizar texts with properties and requirements. In: Asperti, A., Bancerek, G., Trybulec, A. (eds.) MKM 2004. LNCS, vol. 3119, pp. 290–301. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27818-4_21

    Chapter  Google Scholar 

  28. Korniłowicz, A.: Enhancement of Mizar texts with transitivity property of predicates. In: Kohlhase, M., Johansson, M., Miller, B., de de Moura, L., Tompa, F. (eds.) CICM 2016. LNCS (LNAI), vol. 9791, pp. 157–162. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-42547-4_12

    Chapter  Google Scholar 

  29. Naumowicz, A., Korniłowicz, A.: Introducing Euclidean relations to Mizar. [47], pp. 245–248. https://doi.org/10.15439/2017F368

  30. Grabowski, A.: Mechanizing complemented lattices within Mizar type system. J. Autom. Reason. 55(3), 211–221 (2015). http://dx.doi.org/10.1007/s10817-015-9333-5

    Article  MathSciNet  MATH  Google Scholar 

  31. Grabowski, A., Korniłowicz, A., Schwarzweller, C.: On algebraic hierarchies in mathematical repository of Mizar. In: Ganzha, M., Maciaszek, L.A., Paprzycki, M. (eds.) Proceedings of the 2016 FedCSIS. Annals of Computer Science and Information Systems, vol. 8, pp. 363–371. IEEE (2016). https://doi.org/10.15439/2016F520

  32. Grabowski, A., Jastrzębska, M.: Rough set theory from a math-assistant perspective. In: Kryszkiewicz, M., Peters, J.F., Rybinski, H., Skowron, A. (eds.) RSEISP 2007. LNCS (LNAI), vol. 4585, pp. 152–161. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73451-2_17

    Chapter  Google Scholar 

  33. Grabowski, A., Schwarzweller, C.: On duplication in mathematical repositories. In: Autexier, S., Calmet, J., Delahaye, D., Ion, P.D.F., Rideau, L., Rioboo, R., Sexton, A.P. (eds.) CICM 2010. LNCS (LNAI), vol. 6167, pp. 300–314. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14128-7_26

    Chapter  Google Scholar 

  34. Pąk, K.: Improving legibility of natural deduction proofs is not trivial. Log. Methods Comput. Sci. 10(3), 1–30 (2014). http://dx.doi.org/10.2168/LMCS-10(3:23)2014

    MathSciNet  Google Scholar 

  35. Pąk, K.: Automated improving of proof legibility in the Mizar system. [48], pp. 373–387. https://doi.org/10.1007/978-3-319-08434-3_27

  36. Pąk, K.: Improving legibility of formal proofs based on the close reference principle is NP-hard. J. Autom. Reason. 55(3), 295–306 (2015). http://dx.doi.org/10.1007/s10817-015-9337-1

    Article  MathSciNet  MATH  Google Scholar 

  37. Nielson, H., Nielson, F.: Semantics with Applications - A Formal Introduction. Wiley, Hoboken (1992)

    MATH  Google Scholar 

  38. Nikitchenko, M., Tymofieiev, V.: Satisfiability in composition-nominative logics. Cent. Eur. J. Comput. Sci. 2(3), 194–213 (2012). https://doi.org/10.2478/s13537-012-0027-3

    MATH  Google Scholar 

  39. Dijkstra, E.: A Discipline of Programming, 1st edn. Prentice Hall PTR, Upper Saddle River (1997)

    MATH  Google Scholar 

  40. Nikitchenko, M., Shkilniak, S.: Semantic properties of T-consequence relation in logics of quasiary predicates. Comput. Sci. J. Mold. 23(2(68)), 102–122 (2015)

    MathSciNet  Google Scholar 

  41. Ivanov, I., Korniłowicz, A., Nikitchenko, M.: Formalization of nominative data in Mizar. In: Proceedings of TAAPSD 2015, pp. 82–85. Taras Shevchenko National University of Kyiv, Ukraine, 23–26 December 2015

    Google Scholar 

  42. Ivanov, I., Nikitchenko, M., Kryvolap, A., Korniłowicz, A.: Simple-named complex-valued nominative data - definition and basic operations. Formaliz. Math. 25(3), 205–216 (2017). http://dx.doi.org/10.1515/forma-2017-0020

    Article  MATH  Google Scholar 

  43. Korniłowicz, A., Kryvolap, A., Nikitchenko, M., Ivanov, I.: Formalization of the algebra of nominative data in Mizar. [47], pp. 237–244. https://doi.org/10.15439/2017F301

  44. Korniłowicz, A., Kryvolap, A., Nikitchenko, M., Ivanov, I.: Formalization of the nominative algorithmic algebra in Mizar. In: Świątek, J., Borzemski, L., Wilimowska, Z. (eds.) ISAT 2017. AISC, vol. 656, pp. 176–186. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-67229-8_16

    Google Scholar 

  45. Harel, D., Tiuryn, J., Kozen, D.: Dynamic Logic. MIT Press, Cambridge (2000)

    MATH  Google Scholar 

  46. Reynolds, J.C.: Separation logic: a logic for shared mutable data structures. In: Proceedings of the 17th LICS, pp. 55–74 (2002)

    Google Scholar 

  47. Ganzha, M., Maciaszek, L.A., Paprzycki, M. (eds.): Proceedings of FedCSIS 2017. Annals of Computer Science and Information Systems, vol. 11. IEEE, Prague, Czech Republic, 3–6 September 2017

    Google Scholar 

  48. Watt, S.M., Davenport, J.H., Sexton, A.P., Sojka, P., Urban, J. (eds.): CICM 2014. LNCS (LNAI), vol. 8543. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08434-3

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Taras Shevchenko National University of Kyiv, 64/13, Volodymyrska Street, Kyiv, 01601, Ukraine

    Mykola Nikitchenko, Ievgen Ivanov & Andrii Kryvolap

  2. Institute of Informatics, University of Białystok, Ciołkowskiego 1M, 15-245, Białystok, Poland

    Artur Korniłowicz

Authors
  1. Mykola Nikitchenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ievgen Ivanov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Artur Korniłowicz
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Andrii Kryvolap
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mykola Nikitchenko .

Editor information

Editors and Affiliations

  1. Aristotle University of Thessaloniki, Thessaloniki, Greece

    Nick Bassiliades

  2. Zaporizhzhia National University, Zaporizhzhia, Ukraine

    Vadim Ermolayev

  3. University of Bamberg, Bamberg, Germany

    Hans-Georg Fill

  4. Lviv Polytechnic National University, Lviv, Ukraine

    Vitaliy Yakovyna

  5. University of Klagenfurt, Klagenfurt, Austria

    Heinrich C. Mayr

  6. Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

    Mykola Nikitchenko

  7. V. N. Karazin Kharkiv National University, Kharkiv, Ukraine

    Grygoriy Zholtkevych

  8. Kherson State University, Kherson, Ukraine

    Aleksander Spivakovsky

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG, part of Springer Nature

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Nikitchenko, M., Ivanov, I., Korniłowicz, A., Kryvolap, A. (2018). Extended Floyd-Hoare Logic over Relational Nominative Data. In: Bassiliades, N., et al. Information and Communication Technologies in Education, Research, and Industrial Applications. ICTERI 2017. Communications in Computer and Information Science, vol 826. Springer, Cham. https://doi.org/10.1007/978-3-319-76168-8_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-76168-8_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-76167-1

  • Online ISBN: 978-3-319-76168-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation