---
title: "Flexible Matching for Noisy Structural Descriptions"
authors:
  - "Floriana Esposito"
  - "Donato Malerba"
  - "Giovanni Semeraro"
doi: ""
url: "https://ijcai.org/proceedings/1991/96"
pdf: "https://ijcai.org/proceedings/1991/0096.pdf"
venue: "Proceedings of the Twelfth International Joint Conference on Artificial Intelligence"
year: 1991
pages: "658-663"
track: "Learning Be Knowledge Acquisition"
keywords:
---

# Flexible Matching for Noisy Structural Descriptions

Floriana Esposito, Donato Malerba, Giovanni Semeraro

*Proceedings of the Twelfth International Joint Conference on Artificial Intelligence*, pages 658-663.

## Abstract

Uncertaintyondataoftenmakesthetaskofperfectlymatching two descriptions quite ineffective. In this case, a flexible matching, measuring the similarity of two descriptions rather than their equality, is more useful. According to the convention of connecting similarity to the most common concept of distance, we present a definition of distance measure, based on a probabilistic interpretation of the matching predicate, which can cope with structural deformations. As the problem of matching two formulas of the FOPL is NP-complete, two methods are presented in order to cope with complexity: firstly, a branch-and-bound algorithm, and secondly, a heuristic method. These ideas are applied to the problem of recognizing office documents in digital form according to their page layout.