Fundamenta Informaticae - Volume 24, issue 3

Authors: Jacobs, Bart

Article Type: Research Article

Abstract: A specification, as we shall use it here, consists of a signature together with a collection of (non-conditional) equations; these equations involve terms in the ‘distributive type theory’ which is built on top of the signature. This type theory has finite product (x, 1) and coproduct (+, 0) types. Particular simple examples of such specifications are Hagino specifications, which are used to describe inductively defined types. Models of specifications are described in arbitrary distributive categories. In a more categorical approach, one describes models as structure preserving functors. It enables us to define in general what are (a) models of parametrized …spefications (in terms of Kan extensions) and (b) models with parameters (in terms of so-called ‘simple slice’ categories). It is shown that in the special case of Hagino specifications, these general definitions specialize to ones in terms of algebras or coalgebras for associated ‘strong’ polynomial functors. Models with parameters of Hagino specifications were described earlier by Cockett and Spencer. Show more

DOI: 10.3233/FI-1995-2431

Citation: Fundamenta Informaticae, vol. 24, no. 3, pp. 209-250, 1995

Authors: Mitrana, Victor

Article Type: Research Article

Abstract: We introduce two new grammatical interpretations which enlarge the grammatical collection of a given grammar. Briefly, the relations between these interpretations are presented, and also the effect on the generative capacity of a grammar system of the demand that all its components are similar to a given grammar. Especially, one obtains an important increase of the gene rative power if one requires that any component of the system is a b- or w-interpretation of a context free grammar.

DOI: 10.3233/FI-1995-2432

Citation: Fundamenta Informaticae, vol. 24, no. 3, pp. 251-257, 1995

Authors: Heckmann, Reinhold

Article Type: Research Article

Abstract: Two lower bag domain constructions are introduced: the initial construction which gives free lower monoids, and the final construction which is defined explicitly in terms of second order functions. The latter is analyzed closely. For sober dcpo's, the elements of the final lower bag domains can be described concretely as bags. For continuous domains, initial and final lower bag domains coincide. They are continuous again and can be described via a basis which is constructed from a basis of the argument domain. The lower bag domain construction preserves algebraicity and the properties I and M, but does not preserve bounded …completeness, property L, or bifiniteness. Show more

DOI: 10.3233/FI-1995-2433

Citation: Fundamenta Informaticae, vol. 24, no. 3, pp. 259-281, 1995

Authors: Gabarró, J. | Serna, M.J.

Article Type: Research Article

Abstract: We introduce a new way of describing a subclass of CSP processes in the failures-divergence model. These processes will be called rational, by analogy with rational languages in formal language theory. Usually, rational languages are characterized as a solution of a linear system of equations. In this work we use a restricted set of CSP operators and recursion to define CSP-linear systems. We show that these systems are in many respects similar to linear systems in formal language theory. Our main result states that for linear systems the least fix point solution in a CPO can be obtained using Arden's …lemma. Furthermore we give an alternative definition of the class of rational processes in terms of automata. Finally we analyze how the previous result can be extended to other semantic models. Show more

DOI: 10.3233/FI-1995-2434

Citation: Fundamenta Informaticae, vol. 24, no. 3, pp. 283-302, 1995

Authors: Felea, Victor

Article Type: Research Article

Abstract: Certain second-order sentences, called conditional implicational dependencies, about relations in a relational database, are denned and studied. These dependencies include some of previously defined dependencies as special cases. Thus, the family of implicational dependencies introduced and studied by R. Fagip can be included in the family of conditional implicational dependencies. The conditional-functional dependencies defined by P. De Bra and J. Paredaens are special cases of new dependencies. A characterization of a conditional implicational dependency implied by a given class in this family, is given. The existence of Armstrong models for the class of conditional implicational dependencies with a single relational …constant symbol is shown. Show more

Keywords: Armstrong relations, functional dependency, conditional dependency, generalized dependency, conditional implicational dependency, implicational dependency, relational database, logical consequence, mathematical logic

DOI: 10.3233/FI-1995-2435

Citation: Fundamenta Informaticae, vol. 24, no. 3, pp. 303-312, 1995