Skip to main content
SpringerLink
Log in

Monoids of non-halting programs with tests

  • Published:
Algebra universalis Aims and scope Submit manuscript

Abstract

In order to study the axiomatization of the if-then-else construct over possibly non-halting programs and tests, the notion of C-sets was introduced in the literature by considering the tests from an abstract C-algebra. This paper extends the notion of C-sets to C-monoids which include the composition of programs as well as composition of programs with tests. For the class of C-monoids where the C-algebras are adas a canonical representation in terms of functional C-monoids is obtained.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bergman, G.M.: Actions of Boolean rings on sets. Algebra Universalis 28, 153–187 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bloom, S.L., Ésik, Z., Manes, E.G.: A Cayley theorem for Boolean algebras. Am. Math. Mon. 97, 831–833 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bloom, S.L., Tindell, R.: Varieties of “if-then-else”. SIAM J. Comput. 12, 677–707 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bochvar, D.A.: Ob odnom tréhznacnom isčislenii i égo priménénii k analiza paradoksov klassičéskogo rǎssirénnogo funkcional’nogo isčisléniá (in Russian). matématičeskij sbornik, 4: 287–308 (1939). Translated to English by M. Bergmann, “On a three-valued logical calculus and its application to the analysis of the paradoxes of the classical extended functional calculus”. History and Philosophy of Logic 2, 87–112 (1981)

  5. Desharnais, J., Jipsen, P., Struth, G.: Domain and antidomain semigroups. In: Relations and Kleene Algebra in Computer Science. Lecture Notes in Computer Science vol. 5827, pp. 73–87. Springer, Berlin (2009)

  6. Guessarian, I., Meseguer, J.: On the axiomatization of “if-then-else”. SIAM J. Comput. 16, 332–357 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  7. Guzmán, F., Squier, C.C.: The algebra of conditional logic. Algebra Universalis 27, 88–110 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  8. Heyting, A.: Die formalen regeln der intuitionistischen logik, sitzungsberichte der preuszischen akademie der wissenschaften, physikalischmathematische klasse (1930), 42–56 57–71 158–169 in three parts. Sitzungsber. preuss. Akad. Wiss 42, 158–169 (1934)

  9. Igarashi, S.: Semantics of ALGOL-like statements. In: Symposium on Semantics of Algorithmic Languages, pp. 117–177. Springer (1971)

  10. Jackson, M., Stokes, T.: Agreeable semigroups. J. Algebra 266, 393–417 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  11. Jackson, M., Stokes, T.: Semigroups with if-then-else and halting programs. Int. J. Algebra Comput. 19, 937–961 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  12. Jackson, M., Stokes, T.: Monoids with tests and the algebra of possibly non-halting programs. J. Log. Algebraic Methods Program. 84, 259–275 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  13. Kennison, J.F.: Triples and compact sheaf representation. J. Pure Appl. Algebra 20, 13–38 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  14. Kleene, S.: On notation for ordinal numbers. J. Symb. Log. 3, 150–155 (1938)

    Article  MATH  Google Scholar 

  15. Lukasiewicz, J.: On three-valued logic. Ruch Filozoficzny 5 (1920). English translation in Borkowski, L.(ed.) 1970. Jan Lukasiewicz: Selected Works (1920)

  16. Manes, E.G.: Adas and the equational theory of if-then-else. Algebra Universalis 30, 373–394 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  17. Manes, E.G.: A transformational characterization of if-then-else. Theor. Comput. Sci. 71, 413–417 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  18. McCarthy, J.: A basis for a mathematical theory of computation. In: Computer Programming and Formal Systems, pp. 33–70. North-Holland, Amsterdam (1963)

  19. Mekler, A.H., Nelson, E.M.: Equational bases for if-then-else. SIAM J. Comput. 16, 465–485 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  20. Panicker, G., Krishna, K.V., Bhaduri, P.: Axiomatization of if-then-else over possibly non-halting programs and tests. Int. J. Algebra Comput. 27, 273–297 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  21. Pigozzi, D.: Equality-test and if-then-else algebras: axiomatization and specification. SIAM J. Comput. 20, 766–805 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  22. Sethi, R.: Conditional expressions with equality tests. J. ACM 25, 667–674 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  23. Stokes, T.: Sets with \(B\)-action and linear algebra. Algebra Universalis 39, 31–43 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  24. Stokes, T.: Comparison semigroups and algebras of transformations. Semigroup Forum 81, 325–334 (2010)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We are thankful to the referee for providing insightful comments, which have improved the presentation of the paper.

Author information

Authors and Affiliations

  1. Department of Mathematics, Indian Institute of Technology Guwahati, Guwahati, India

    Gayatri Panicker & K. V. Krishna

  2. Department of Computer Science and Engineering, Indian Institute of Technology Guwahati, Guwahati, India

    Purandar Bhaduri

Authors
  1. Gayatri Panicker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. K. V. Krishna
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Purandar Bhaduri
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to K. V. Krishna.

Additional information

Presented by M. Jackson.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Panicker, G., Krishna, K.V. & Bhaduri, P. Monoids of non-halting programs with tests. Algebra Univers. 79, 8 (2018). https://doi.org/10.1007/s00012-018-0490-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00012-018-0490-3

Mathematics Subject Classification

Keywords

Search

Navigation