SEMANTICS OF NONSEQUENTIAL TREE-BASED COMPUTATION SCHEMES

Article type: Research Article

Authors: Ehrenfeucht, A. | Rozenberg, G. | Salomaa, K.

Affiliations: Department of Computer Science, University of Colorado at Boulder, Boulder CO 80309 U.S.A. | Department of Computer Science, Leiden University, Leiden, P.O. Box 9512. 2300 RA. The Netherlands and Department of Computer Science. University of Colorado at Boulder, Boulder CO 80309 U.S.A. | Department of Mathematics. University of Turku. FIN-20014 Turku. Finland, e-mail:ksalomaa@ sara.cc.utu.fi

Abstract: 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.

DOI: 10.3233/FI-1997-29401

Journal: Fundamenta Informaticae, vol. 29, no. 4, pp. 305-324, 1997