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)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 doesn’t 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.
版权说明：以下全部内容由刘国华上传于 2005年03月04日 20时59分09秒，版权归本人所有。