Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Automated Composition of Conversion Software



David W. Flater


Given a library of converters with known behaviors, an integration engine must determine which are useful in a given scenario and produce a plan for how they can be used to achieve specified goals. This report documents the algorithm implemented by the AMIS3 integration engine. First, the problem is formalized and shown to be NP-hard. Then, the algorithm is explained and shown to be correct for all deterministic scenarios. Next, the behavior for nondeterministic scenarios is discussed. Finally, an alternate approach is outlined.
NIST Interagency/Internal Report (NISTIR) - 7099
Report Number


algorithm, integration, search, software


Flater, D. (2004), Automated Composition of Conversion Software, NIST Interagency/Internal Report (NISTIR), National Institute of Standards and Technology, Gaithersburg, MD, [online], (Accessed June 19, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created March 1, 2004, Updated November 10, 2018