Disambiguation of SGML content models (Q4376789)

Developing the ideas of Anne Brüggemann-Klein and Derick Wood, the author of the paper proposes a disambiguation algorithm that transforms an ambiguous content model into an unambiguous one by generalizing the language. The algorithm contains the following basic phases: (1) Minimal deterministic finite automata corresponding to the content models of each element are constructed. (2) The strongly connected components, orbits, of each automaton are then generated to conform the 1-unambiguity constraints, e.g. to obtain the orbit property. (3) Finally, the automata are converted into 1-unambiguous content models. The proposed disambiguation algorithm was implemented as part of an original automatic DTD (document type definition) generation tool. The DTD generation system succeeds to form content models from tagged documents, but the algorithm could be used to transform existing DTDs as well. For the entire collection see [Zbl 0879.00058].