Hostname: page-component-8448b6f56d-t5pn6 Total loading time: 0 Render date: 2024-04-19T01:25:49.263Z Has data issue: false hasContentIssue false
  • English
  • Français

Demonic operators and monotype factors

Published online by Cambridge University Press:  04 March 2009

Roland Backhouse  and
Jaap van der Woude
Roland Backhouse
Affiliation:
Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
Jaap van der Woude
Affiliation:
Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper tackles the problem of constructing a compact, point-free proof of the associativity of demonic composition of binary relations and its distributivity through demonic choice. In order to achieve this goal, a definition of demonic composition is proposed in which angelic composition is restricted by means of a so-called ‘monotype factor’. Monotype factors are characterised by a Galois connection similar to the Galois connection between composition and factorisation of binary relations. The identification of such a connection is argued to be highly conducive to the desired compactness of calculation.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 3 , Issue 4 , December 1993 , pp. 417 - 433
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Backhouse, R. C, de Bruin, P., Hoogendijk, P., Malcolm, G., Voermans, T. S. and van der Woude, J. (1992) Polynomial relators. In: Nivat, M., Rattray, C. S., Rus, T. and Scollo, G. (eds.) Proceedings of the 2nd Conference on Algebraic Methodology and Software Technology, AMAST'91, Springer-Verlag Workshops in Computing.Google Scholar
Backhouse, R. C, de Bruin, P., Malcolm, G., Voermans, T. S. and van der Woude, J. (1991a) Relational catamorphisms. In: Möller, B. (ed.) Proceedings of the IFIP TC2/WG2.1 Working Conference on Constructing Programs, Elsevier Science Publishers B.V. 287–318.Google Scholar
Backhouse, R. C. and Lutz, R. K. (1977) Factor graphs, failure functions and bi-trees. In: Salomaa, A. and Steinby, M. (eds.) Fourth Colloquium on Automata, Languages and Programming. Springer-Verlag Lecture Notes in Computer Science 52 61–75.CrossRefGoogle Scholar
Backhouse, R. C, Voermans, T. S. and van der Woude, J. (1991b) A relational theory of datatypes. (In preparation: copies of draft available on request.)Google Scholar
Berghammer, R. (1991) Relational specification of data types and programs, Bericht 9109, Universität der Bundeswehr München, Fakultät fur Informatik.Google Scholar
Berghammer, R. and Zierer, H. (1986) Relational algebraic semantics of deterministic and nondeterministic programs. Theoretical Computer Science 43 123–147.CrossRefGoogle Scholar
Birkhoff, G. (1948) Lattice Theory (revised edition), American Mathematical Society, Providence, Rhode Isl and.Google Scholar
Conway, J. H. (1971) Regular algebra and finite machines, Chapman and Hall, London.Google Scholar
Dijkstra, E. W. and Scholten, C. S. (1990) Predicate Calculus and Program Semantics, Springer-Verlag, Berlin.CrossRefGoogle Scholar
Dilworth, R. P. (1939) Non-commutative residuated lattices. Transactions of the American Mathematical Society 46 426–444.CrossRefGoogle Scholar
Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M. and Scott, D. S. (1980) A Compendium of Continuous Lattices, Springer-Verlag.CrossRefGoogle Scholar
Hartmanis, J. and Stearns, R. E. (1964) Pair algebras and their application to automata theory. Information and Control 7 (4) 485–507.CrossRefGoogle Scholar
Hartmanis, J. and Stearns, R. E. (1966) Algebraic Structure Theory of Sequential Machines, Prentice-Hall.Google Scholar
Herrlich, H. and Hušek, M. (1985) Galois connections. In: Melton, A. (ed.) Mathematical Foundations of Programming Semantics. Springer-Verlag Lecture Notes in Computer Science 239 122–134.CrossRefGoogle Scholar
Hoare, C. A. R. and He, J. (1986) The weakest prespecification. Fundamenta Informaticae 9 51–84, 217–252.CrossRefGoogle Scholar
Knuth, D. E., Morris, J. H. and Pratt, V. R. (1977) Fast pattern matching in strings. SIAM Journal of Computing 6 325–350.CrossRefGoogle Scholar
McDill, J. M., Melton, A. C. and Strecker, G. E. (1987) A category of Galois connections. In: Pitt, D. H., Poigné, A. and Rydeheard, D. E. (eds.) Category Theory and Computer Science. Springer- Verlag Lecture Notes in Computer Science 283 290–300.CrossRefGoogle Scholar
Melton, A., Schmidt, D. A. and Strecker, G. E. (1986) Galois connections and computer science applications. In: Pitt, D., Abramsky, A., Poigné, A. and Rydeheard, D. E. (eds.) Category Theory and Computer Programming. Springer-Verlag Lecture Notes in Computer Science 240 299–312.CrossRefGoogle Scholar
Nguyen, T. T. (1991) A relational model of nondeterministic programs. International J. of Foundations of Computer Science 2 (2) 101–131.CrossRefGoogle Scholar
Ore, O. (1944) Galois connexions. Transactions of the American Mathematical Society 55 493–513.CrossRefGoogle Scholar
Pratt, V. (1990) Action logic and pure induction. In: van Eijck, J. (ed.) Proc. Logics in AI: European Workshop JELIA '90. Springer-Verlag Lecture Notes in Computer Science 478 97–120.CrossRefGoogle Scholar
Simons, M. (1991) Galois connections and pair algebras. (Unpublished draft.)Google Scholar
Tarski, A. and Givant, S. (1987) A Formalization of Set Theory without Variables. Colloquium Publications 41, American Mathematical Society, Providence, Rhode Isl and.Google Scholar
van der Woude, J. (1991) Free style specwrestling: Demonic composition and choice. In: Lambert Meertens, CWl, Liber Amicorum, 1966–1991, Stichting Mathematisch Centrum, Amsterdam.Google Scholar