Token Evolution in an Ill-posed Constraint Petri-net

Unification constraints of predicate logic or string rewriting rules of context free grammar can be represented by a Petri-net with the AND/OR tree structure. In this network, deductive inference or parsing can be formulated as a problem to find a solution subtree within which variables have consistent substitution. The paper focuses on a token-based heuristic method to solve such an ill-posed problem, and presents three prerequisite conditions to be satisfied by tokens which propagate and evolve in the network. Incorporating these requirements would enable us to design highly distributed algorithms for deduction or parsing.