The thesis defended in this document starts with considering some formal approaches to Machine Perception algorithm performance analysis, and how it relates to the limits (and unavoidable subjectivity) of ground truth specification. It establishes the intrinsic ambiguity of interpretation and analysis when used in conjunction with Machine Perception and considers them mainly in relation to Document Image Analysis. After establishing the fact that interpretation is open to ambiguity and that most of this ambiguity comes from inconsistent or different interpretation contexts our overall goal is to investigate whether one can: * establish a form of context description that is appropriate for machine perception (and document image analysis in particular) and whether it can be obtained auto- matically by statistical or formal learning techniques? * use this context description to evaluate algorithm performances? * use this context description to describe data, so that it can be used for information retrieval purposes? * establish formal boundaries or limitations for the previously described descriptions and establish whether there are interpretations that are provably impossible to be obtained through an algorithm. If there is indeed a class of interpretation problems that cannot be solved by an algorithm, the second question would be whether this class can be characterized in some sorts.
