Fundamenta Informaticae - Volume 29, issue 4

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

Article Type: Research Article

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

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

Authors: Fachini, Emanuela | Monti, Angelo

Article Type: Research Article

Abstract: We prove that no nonregular deterministic context-free language is accepted by any systolic Y-tree automaton while some of them, but not all, can be accepted by nondeterministic systolic Y-tree automata. We show that weak superstable systolic automata over incomplete Y-tree can accept only regular languages. We also show that the weak superstability and the superstability problems are decidable for deterministic systolic automata over a sparse and superprefix Y-tree. Moreover we prove that the regularity problem is decidable for systolic binary tree automata.

DOI: 10.3233/FI-1997-29402

Citation: Fundamenta Informaticae, vol. 29, no. 4, pp. 325-339, 1997

Authors: Ferrari, Gian-Luigi

Article Type: Research Article

Abstract: A process calculus where atomic actions cooperate via explicit synchronization policies is presented. Bisimulation semantics for the calculus is provided with a sound and complete axiomatization. The problem of modeling concurrency control strategies is also addressed. This paper intends to show that process-algebraic semantics, notably non interleaving semantics, can be used to reason about complex concurrent behaviours.

DOI: 10.3233/FI-1997-29403

Citation: Fundamenta Informaticae, vol. 29, no. 4, pp. 341-368, 1997

Authors: Järvinen, Jouni

Article Type: Research Article

Abstract: We give a simple representation of dependence spaces and a new characterization of the reducts of an arbitrary subset of a dependence space by the means of closure systems. We present an algorithm for finding the reducts of any given subset of a dependence space. The algorithm is based on a notion of difference function which connects the reduction problem to the general problem of identifying the set of all minimal vectors of values satisfying a positive (i.e., isotone) Boolean function.

DOI: 10.3233/FI-1997-29404

Citation: Fundamenta Informaticae, vol. 29, no. 4, pp. 369-382, 1997

Authors: Kundu, Sukhamay | Chen, Jianhua

Article Type: Research Article

Abstract: We propose here a new notion of a minimal model for forming circumscription in belief-logic by incorporating the notion of minimal models in the prepositional logic. This results in a new circumscription operation for belief-formulas than the one considered in [4-6]. An important feature of the new circumscription operation is its close relationship with the circumscription of prepositional formulas. For instance, we have CIRC[Bφ] = B(CIRC[φ]), where φ is a prepositional formula. We give several examples to show that the new notion of circumscription fits quite well with intuition.

Keywords: Belief-logic, circumscription, minimal models

DOI: 10.3233/FI-1997-29405

Citation: Fundamenta Informaticae, vol. 29, no. 4, pp. 383-390, 1997