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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.