The concept of macro tree transducers (MTTs) is extended to macro forest transducers (MFTs) in this paper. The new concept is derived by enhancing MTTs with concatenation. It is shown that MFTs form a strict superset of MTTs. It is also proven that every MFT can be simulated by the composition of two MTTs.
Although MFTs are more powerful than MTTs, the decidability and complexity results for inverse type checking (computing the preimage of a recognizable language) are almost the same as for MTTs.
The paper presents an important extension of MTTs, which is closely related to the Extensible Markup Language (XML) data model. A discussion of future work announces extensions of MFTs to a formal model for stylesheet processors.
The paper is original, and addresses a key problem regarding type safety in XML, a data exchange standard for the Internet.