Fundamenta Informaticae - Volume 103, issue 1-4

Authors: Pratt, Vaughan

Article Type: Research Article

Abstract: We present the Yoneda Lemma in terms of categories without explicit reference to the notion of functor. From this perspective we then define a commune as a common generalization of Chu spaces and presheaves, and give some applications.

Keywords: commune, yoneda, chu space

DOI: 10.3233/FI-2010-325

Citation: Fundamenta Informaticae, vol. 103, no. 1-4, pp. 203-218, 2010

Authors: Rudnicki, Ryszard | Wieczorek, Radosław

Article Type: Research Article

Abstract: We study a non-linear age-structured discrete-time population model and give necessary and sufficient conditions for stability of a positive stationary point. In the case of semelparous species we show that the population converges locally to a population consisted only of individuals at one age. It means that the long-time behaviour of the population depends only on an one-dimensional transformation g. If the reproduction age is an even number we prove that the positive stationary point is unstable and numerical simulations suggest that in this case almost all trajectories behave asymptotically as trajectories corresponding to g.

Keywords: age-structured discrete-time model, semelparous species, periodicity, chaos

DOI: 10.3233/FI-2010-326

Citation: Fundamenta Informaticae, vol. 103, no. 1-4, pp. 219-233, 2010

Authors: Setty, Yaki | Cohen, Irun R. | Harel, David

Article Type: Research Article

Abstract: Complex biological systems involve incorporated behaviors of numerous processes, mechanisms and objects. However, experimental analysis, by its nature, divides biological systems into static interactions with little dynamics. To bridge the gap between experimental data and the underlying behavior, our group has been formalizing biological findings into mathematically and algorithmically rigorous specifications, which are then compiled into reactive models. To realistically animate our models, we designed a generic architecture for the earlier idea of reactive animation, in a way that allows it to link up reactive models with animation tools. Here, we describe the reactive animation approach and some of the …benefits of employing it to simulate and analyze complex biological systems. We illustrate our approach with a model of pancreatic development, a highly complex system with a unique 3D structure, and also mention more recent work on adding animation to the generic cell project (GemCell). Show more

Keywords: Modeling, Computational Biology, Reactive Animation

DOI: 10.3233/FI-2010-327

Citation: Fundamenta Informaticae, vol. 103, no. 1-4, pp. 235-246, 2010

Authors: Shivers, Olin | Wand, Mitchell

Article Type: Research Article

Abstract: If we represent a λ-calculus term as a DAG rather than a tree, we can efficiently represent the sharing that arises from β-reduction, thus avoiding combinatorial explosion in space. By adding uplinks from a child to its parents, we can efficiently implement β-reduction in a bottom-up manner, thus avoiding combinatorial explosion in time required to search the term in a top-down fashion. We present an algorithm for performing β-reduction on λ-terms represented as uplinked DAGs; describe its proof of correctness; discuss its relation to alternate techniques such as Lamping graphs, explicit-substitution calculi and director strings; and present some timings of …an implementation. Besides being both fast and parsimonious of space, the algorithm is particularly suited to applications such as compilers, theorem provers, and type-manipulation systems that may need to examine terms in between reductions—i.e., the “readback” problem for our representation is trivial. Like Lamping graphs, and unlike director strings or the suspension λ calculus, the algorithm functions by side-effecting the term containing the redex; the representation is not a “persistent” one. The algorithm additionally has the charm of being quite simple; a complete implementation of the data structure and algorithm is 180 lines of SML. Show more

DOI: 10.3233/FI-2010-328

Citation: Fundamenta Informaticae, vol. 103, no. 1-4, pp. 247-287, 2010

Authors: Tyszkiewicz, Jerzy

Article Type: Research Article

Abstract: This paper contains the English version of my Master's thesis [6] written about 22 years ago under supervision of Jerzy Tiuryn. Its main result is the proof of PTIME-completeness of the type reconstruction problem for simply typed lambda calculus. About the time I had the English paper ready, a much simpler proof [3] by John Mitchell (later published in [4]) was announced. Therefore my thesis remained an unpublished manuscript, but has been referenced to in a number of other papers. The TEX sources went lost in the meantime, so the present paper has been re-typed from scratch, but is almost …identical to the original one written many years ago. Show more

Keywords: typed lambda calculus, simple types, typability, complexity, PTIME

DOI: 10.3233/FI-2010-329

Citation: Fundamenta Informaticae, vol. 103, no. 1-4, pp. 289-301, 2010

Authors: Urzyczyn, Paweł

Article Type: Research Article

Abstract: Is is shown that the inhabitation problem is decidable for intersection type assignment without the intersection elimination rule.

DOI: 10.3233/FI-2010-330

Citation: Fundamenta Informaticae, vol. 103, no. 1-4, pp. 303-322, 2010

Authors: Wilczyński, Bartek | Hvidsten, Torgeir R.

Article Type: Research Article

Abstract: Recent years have seen a wealth of computational methods applied to problems stemming from molecular biology. In particular, with the completion of many new full genome sequences, great advances have been made in studying the role of non-protein-coding parts of the genome, reshaping our understanding of the role of DNA sequences. Recent breakthroughs in experimental technologies allowing us to inspect the innards of cells on a genomic scale has provided us with unprecedented amounts of data, posing new computational challenges for scientists working to uncover the secrets of life. Due to the binary-like nature of the DNA code and switch-like …behavior of many regulatory mechanisms, many of the questions that are currently in focus in biology are surprisingly related to problems that have been of long-term interest to computer scientists. In this review, we present a glimpse into the current state of research in computational methods applied to modeling the regulatory genome. Our aim is to cover current approaches to selected problems from molecular biology that we consider most interesting from the perspective of computer scientists as well as highlight new challenges that will most likely draw the attention of computational biologists in the coming years. Show more

Keywords: computational biology, gene regulation, DNA motifs, regulatory elements

DOI: 10.3233/FI-2010-331

Citation: Fundamenta Informaticae, vol. 103, no. 1-4, pp. 323-332, 2010