Towards an Approximation Theory of Discrete Problems. Part I

Article type: Research Article

Authors: Skowron, Andrzej | Stepaniuk, Jaroslaw

Affiliations: Institute of Mathematics, University of Warsaw, Banacha 2, 00-913 Warsaw, Poland

Abstract: The purpose of this paper is to make the first step towards an approximation theory of discrete problems in which one can express and prove properties of approximating algorithms as well as carry out an approximate reasoning. We introduce an approximation propositional dynamic logic (APDL) with approximations of programs and formulas. We discuss the expressibility of APDL. The main theorem is the completeness theorem for a fragment of APDL. We consider also the approximation problem of properties expressible in APDL by a distinguished set of so called simple approximate formulas and programs, generated only from approximations of atomic properties and approximations of atomic programs. The solution of the uniform approximation problem is presented and a result about an appoximation of decision algorithms is given.

DOI: 10.3233/FI-1991-15208

Journal: Fundamenta Informaticae, vol. 15, no. 2, pp. 187-208, 1991