SEMANTICS OF NONSEQUENTIAL TREE-BASED COMPUTATION SCHEMES
Andrzej Ehrenfeucht, Grzegorz Rozenberg, Kai Salomaa · Fundamenta Informaticae · 1997
We consider structured processes that compute changes of valuation functions defined for functional structures, where both the domain and range of each function are the set of sequences over a carrier set. By introducing consistency conditions and certain restrictions on the underlying graph, we obtain a determinism result guaranteeing that for each valuation the structured process computes a unique change of context, i.e., the process defines a partial function on the set of valuations. Employing the determinism theorem we obtain a decomposition result for interpreted trees using a structured process where the edges represent computations in the subtrees.