Fundamenta Informaticae - Volume 10, issue 3

Article Type: Other

DOI: 10.3233/FI-1987-10301

Citation: Fundamenta Informaticae, vol. 10, no. 3, pp. i-vii, 1987

Authors: Kelter, Udo

Article Type: Research Article

Abstract: Systems which use parallel processing to speed up response times are normally required to be determinate. Parallel program schemata are formal models of parallel systems which serve to exactly define determinacy. Three variants of determinacy have frequently been used in the literature: Two “semantic” ones, which refer to the final contents of variables and to the sequences of contents, and a “syntactic” one, which is based upon the notion of conflict. Variants of determinacy can be derived with a universal definition of determinacy (as presented in [K73]) which uses a parameter, namely an equivalence relation on computations. Each of the …above variants corresponds to a certain equivalence relation. The main aim of this paper is to investigate the role of “read-only”-operations, e.g. pure tests. Results of tests do not matter for both semantic forms of determinacy, whereas they are relevant for the syntactic form. We will snow that different variants of semantic and syntactic determinacy can be obtained by judging read-only operations as relevant or not. Show more

Keywords: determinacy, equivalence of computations, program schemata

DOI: 10.3233/FI-1987-10302

Citation: Fundamenta Informaticae, vol. 10, no. 3, pp. 225-246, 1987

Authors: Nait Abdallah, Mohand-Areski

Article Type: Research Article

Abstract: Using topological methods, we study the operational and greatest fixpoint semantics of infinite computations in logic programming. We show the equivalence of the operational and greatest fix point semantics in the case of fair derivations. We give some canonical partition, and soundness and completeness results which generalize already known results about the finitary case. Since fair derivations are a generalization of successful derivations, we thus give a uniform treatment of all meaningful computations in logic programming.

DOI: 10.3233/FI-1987-10303

Citation: Fundamenta Informaticae, vol. 10, no. 3, pp. 247-307, 1987

Authors: Zaionc, Marec

Article Type: Research Article

Abstract: λ -language over simple type structure is considered. We investigate unification problem such that number of elementary substitutions in a potentially infinite matching tree introduced by Huet is finite (compare [8]). The substitutions are generated using term grammar technique. Such a grammar consists of productions which are on the form; nonterminal variable of certain type produces a term of the same type. The most interesting is the case when matching tree is infinite and includes an infinite number of most general unifiers. We will show an interesting property of the infinite unification trees from examined class: for every infinite branch …there is a node which occurs earlier in this tree. It means that there are some fragments which are repeated in this tree. Therefore the set of most general unifiers which are represented by terminal nodes can be described by regular expression over finite alphabet. Regular expression are constructed as a solution of linear language equalities. For every problem from this class the set of unifiers is described by some language. This language can be approximated by regular languages. Show more

Keywords: typed λ-calculus, unification, infinite trees, regular expressions, matching trees

DOI: 10.3233/FI-1987-10304

Citation: Fundamenta Informaticae, vol. 10, no. 3, pp. 309-322, 1987

Authors: Chrobak, Marek | Rytter, Wojciech

Article Type: Research Article

Abstract: We consider the unique decipherability problem for partially commutative alphabets. It is shown that the decidability of the problem depends heavily on the size of the alphabet and the structure of the graph of the commutativity relation. In particular, for alphabets with at most three letters the problem is decidable and for alphabets of bigger size the problem is undecidable.

DOI: 10.3233/FI-1987-10305

Citation: Fundamenta Informaticae, vol. 10, no. 3, pp. 323-336, 1987