The usual approach to the synthesis of algorithms for the solution of problems in combinatorial mathematics consists of two steps. I - Description: the problem is embedded in a general structure which is rich enough to permit a mathematical modelling of the problem. 2 - Solution: the problem is solved by means of techniques "as simple as possible"~ with respect to some given notion of complexity. We give a formalization of this approach in the framework of category theory, which is general enough to get rid of unessential details. In particular such a framework will be provided by the category of ordered complete sigma-algebras and we will describe the relation between description and solution by means of a variant of so called "Mezei-Wright like results" relating the concept of least fixed point to that of a suitable natural transformation between functors.

Bertoni, A., Mauri, G., Torelli, M. (1977). An algebraic approach to problem solution and problem semantics. In Proceedings of 6th MFCS – Mathematical Foundations of Computer Science (pp.253-262). Berlin : Springer [10.1007/3-540-08353-7_143].

An algebraic approach to problem solution and problem semantics

Mauri, G;
1977

Abstract

The usual approach to the synthesis of algorithms for the solution of problems in combinatorial mathematics consists of two steps. I - Description: the problem is embedded in a general structure which is rich enough to permit a mathematical modelling of the problem. 2 - Solution: the problem is solved by means of techniques "as simple as possible"~ with respect to some given notion of complexity. We give a formalization of this approach in the framework of category theory, which is general enough to get rid of unessential details. In particular such a framework will be provided by the category of ordered complete sigma-algebras and we will describe the relation between description and solution by means of a variant of so called "Mezei-Wright like results" relating the concept of least fixed point to that of a suitable natural transformation between functors.
slide + paper
Algorithms; Category theory; Semantics; Fixed points; Functors
English
MFCS – Mathematical Foundations of Computer Science
1977
Gruska, J
Proceedings of 6th MFCS – Mathematical Foundations of Computer Science
978-3-540-08353-5
1977
53
253
262
none
Bertoni, A., Mauri, G., Torelli, M. (1977). An algebraic approach to problem solution and problem semantics. In Proceedings of 6th MFCS – Mathematical Foundations of Computer Science (pp.253-262). Berlin : Springer [10.1007/3-540-08353-7_143].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/16952
Citazioni
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
Social impact