Fundamenta Informaticae - Volume 67, issue 4

Authors: Gire, Françoise | Plourde, Corinne

Article Type: Research Article

Abstract: We propose a new partial semantics for disjunctive deductive databases that we call disjunctive well-founded semantics. This semantics extends the classical well-founded semantics of normal databases for disjunctive databases. We give a declarative definition as well as a computational procedure for this new semantics. We prove that, in the case of disjunctive positive databases, i.e. disjunctive databases without negation, the disjunctive well-founded semantics coincides with the intersection of the minimal models.

Keywords: Disjunctive deductive databases, normal deductive databases, partial semantics, well-founded semantics

Citation: Fundamenta Informaticae, vol. 67, no. 4, pp. 323-342, 2005

Authors: Janicki, Ryszard | Wassyng, Alan

Article Type: Research Article

Abstract: Tabular Expressions (Parnas et al. [20, 28, 32, 33]) are means to represent the complex relations that are used to specify or document software systems. A formal model and a semantics for tabular expressions are presented. The model covers most known types of tables used in software engineering, and admits precise classification and definition of new types of tables. The practical importance of the semantics of tabular expressions is also discussed.

Citation: Fundamenta Informaticae, vol. 67, no. 4, pp. 343-370, 2005

Authors: Popa, Ionuţ

Article Type: Research Article

Abstract: In this paper we present a new simple method to rewrite a given input string into another one which can be more efficiently compressed (in some cases) by traditional compression methods.

Keywords: reversible transformation, data compression

Citation: Fundamenta Informaticae, vol. 67, no. 4, pp. 371-375, 2005

Authors: Xu, Jian | Zucker, Jeffery

Article Type: Research Article

Abstract: This paper compares two scheme-based models of computation on abstract many-sorted algebras A: Feferman's system ACP(A) of "abstract computational procedures" based on a least fixed point operator, and Tucker and Zucker's system μPR(A) based on primitive recursion on the naturals together with a least number operator. We prove a conjecture of Feferman that (assuming contains sorts for natural numbers and arrays of data) the two systems are equivalent. The main step in the proof is showing …the equivalence of both systems to a system Rec(A) of computation by an imperative programming language with recursive calls. The result provides a confirmation for a Generalized Church-Turing Thesis for computation on abstract data types. Show more

Keywords: models of computation, many-sorted algebras, recursive schemes, recursive procedures, fixed points, computation on abstract data types, abstract computability

Citation: Fundamenta Informaticae, vol. 67, no. 4, pp. 377-419, 2005