Formally Verifying Dynamic Properties of Knowledge Based Systems(9)

Abstract. In this paper we study dynamic properties of knowledge-based systems. We argue the importance of such dynamic properties for the construction and analysis of knowledge-based systems. We present a case-study of a simple classification method for w

3.3Anytimeproperties

ThePSMspeci edabovedoesindeedhaveanumberofpropertieswhicharetobeexpectedofareasonableanytimealgorithm.WehavestatedandprovenanumberofsuchpropertiesinKIV,andwewilldiscussthesepropertiesbelow.

Firstofall,noticethataxiom(6)abovecanbeinterpretedastheadapter[8]thatisrequiredtobridgethegapbetweenthegoaldescriptionfromformula(1)andthecompetenceoftheanytimealgorithm.Since ltercsoutputcs,axiom(6)statesthat lter-boundeddoesindeedachievetheclassi cationtaskundertheassumptionofsuf cientrun-time(namelynatleastaslargeasthenumberofclassesthatmustbechecked).

Twootherpropertiesare

lter-boundedcsnn

Thisstatesthatthenumberofelementsintheoutputsetisboundedbythenumberofcomputationsteps,and