Fundamenta Informaticae - Volume 33, issue 2

Authors: Calude, Cristian S. | Hertling, Peter H.

Article Type: Research Article

Abstract: How fast can one approximate a real by a computable sequence of rationals? Rather surprisingly, we show that the answer to this question depends very much on the information content in the finite prefixes of the binary expansion of the real. Computable reals, whose binary expansions have a very low information content, can be approximated (very fast) with a computable convergence rate. Random reals, whose binary expansions contain very much information in their prefixes, can be approximated only very slowly by computable sequences of rationals (this is the case, for example, for Chaitin's Ω numbers) if they can be computably …approximated at all. We also show that one can computably approximate any computable real very slowly, with a convergence rate slower than any computable function. However, there is still a large gap between computable reals and random reals: any computable sequence of rationals which converges (monotonically) to a random real converges slower than any computable sequence of rationals which converges (monotonically) to a computable real. Show more

Keywords: Computable reals, random reals, approximations, program-size complexity, information content

DOI: 10.3233/FI-1998-33201

Citation: Fundamenta Informaticae, vol. 33, no. 2, pp. 105-120, 1998

Authors: Pankowski, Tadeusz

Article Type: Research Article

Abstract: A new method for viewing and manipulating identity-based object structures is proposed. The method is founded on the viewing the object structure as an object graph which in turn is represented as a set of paths. Over a power set of paths we construct a powerdomain which forms a lattice with well-defined meet and join operations. In our construction of the powerdomain of paths we combine the Hoare ordering (appropriate for ordering of tuple objects) with the Smyth ordering (appropriate for ordering of set objects) into a new ordering appropriate for set of paths capturing information conveyed by both tuple …and set objects. The approach allows to deal with incomplete tuple objects as well as with partially described sets. The goal of the powerdomain construction is to provide a semantic domain for a path calculus language [20], where path calculus variables range over paths and path calculus queries give sets of paths as their answers. Show more

Keywords: object-oriented databases, complex objects, powerdomains, object graphs

DOI: 10.3233/FI-1998-33202

Citation: Fundamenta Informaticae, vol. 33, no. 2, pp. 121-148, 1998

Authors: Pigozzi, Don | Salibra, Antonino

Article Type: Research Article

Abstract: Lambda abstraction algebras are designed to algebraize the untyped lambda calculus in the same way cylindric and polyadic algebras algebraize the first-order logic; they are intended as an alternative to combinatory algebras in this regard. Like combinatory algebras they can be defined by true identities and thus form a variety in the sense of universal algebra. One feature of lambda abstraction algebras that sets them apart from combinatory algebras is the way variables in the lambda calculus are abtracted; this provides each lambda abstraction algebra with an implicit coordinate system. Another peculiar feature is the algebraic reformulation of (β)-conversion as …the definition of abstract substitution. Functional lambda abstraction algebras arise as the “coordinatizations” of environment models or lambda models, the natural combinatory models of the lambda calculus. As in the case of cylindric and polyadic algebras, questions of the functional representation of various subclasses of lambda abstraction algebras are an important part of the theory. The main result of the paper is a stronger version of the functional representation theorem for locally finite lambda abstraction algebras, the algebraic analogue of the completeness theorem of lambda calculus. This result is used to study the connection between the combinatory models of the lambda calculus and lambda abstraction algebras. Two significant results of this kind are the existence of a strong categorical equivalence between lambda algebras and locally finite lambda abstraction algebras, and between lambda models and rich, locally finite lambda abstraction algebras. Show more

Keywords: lambda calculus, cylindric algebras, polyadic algebras, abstract substitution, combinatory algebras, lambda algebras, lambda models, representation theorems

DOI: 10.3233/FI-1998-33203

Citation: Fundamenta Informaticae, vol. 33, no. 2, pp. 149-200, 1998

Authors: Plump, Detlef

Article Type: Research Article

Abstract: It is shown that it is undecidable in general whether a graph rewriting system (in the “double pushout approach”) is terminating. The proof is by a reduction of the Post Correspondence Problem. It is also argued that there is no straightforward reduction of the halting problem for Turing machines or of the termination problem for string rewriting systems to the present problem.

Keywords: graph rewriting, termination, Post Correspondence Problem

DOI: 10.3233/FI-1998-33204

Citation: Fundamenta Informaticae, vol. 33, no. 2, pp. 201-209, 1998