A GRAPH-THEORETIC APPROACH FOR RECOGNIZING THE USER INTERPRETATION WITHOUT CONFLICTS

摘要

In this paper, in order to express the user interpretation (a set of user―specified GD―constraints, see[l ])in terms of a directed graph, the definition of directed graph in graph theory is extended according to the characters of the user interpretation and the requirement of the problem, and the node in this directed graph may be either an ordinary node or a directed graph. The directed graph(having been extended)expressing the user interpretation is said to be a GD―constraint graph. Based on these, the features of the GD―constraint graph corresponding to the user interpretation without conflicts are extracted. Finally, the sufficient and necessary condition under which the user interpretation doesnt contain conflicts is given, and a polynomial time recognition algorithm which time complexity is O(m*n) is proposed on the basis of the sufficient and necessary condition, then, the correctness of the algorithm is proved and the time complexity of the algorithm is analyzed.