Wyniki wyszukiwania - BazTech

Ograniczanie wyników

4 Fundamenta Informaticae

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: model of computation

Sortuj według:

Ogranicz wyniki do:

Reaction Systems and Enabling Equivalence

Kleijn Jetty, Koutny Maciej, Mikulski Łukasz

Fundamenta Informaticae

2020

Vol. 171, nr 1-4

261--277

Reaction systems were introduced in order to provide an abstract model for the study of the biochemical processes that take place in the living cell. Processes of this kind are the result of the interactions between reactions and may be influenced by the environment. Thus, reaction systems can be considered as a model of (interactive) computation. In previous works, various equivalences defined directly on reaction systems and processes had been proposed and compared. These equivalences were all based on functional equivalence that compares a system’s behaviour at every stage of its execution. In this paper, in contrast, we investigate enabling equivalence which focuses on the system behaviour only in specific stages of its evolution, namely those where all of its reactions are active. We discuss the effect of such an approach and, in particular, its relationship to a transition system representation of the system’s behaviour.

First and Second Order Recursion on Abstract Data Types

Xu J., Zucker J.

Fundamenta Informaticae

2005

Vol. 67, nr 4

377--419

This paper compares two scheme-based models of computation on abstract many-sorted algebras A: Feferman's system of ``abstract computational procedures" based on a least fixed point operator, and Tucker and Zucker's system based on primitive recursion on the naturals together with a least number operator. We prove a conjecture of Feferman that (assuming A 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 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.

UPSILON: Universal Programming System with Incomplete Lazy Object Notation

Postow B., Regan K., Smith C.H.

Fundamenta Informaticae

2002

Vol. 50, nr 3,4

325-359

This paper presents a new model of computation that differs from prior models in that it emphasizes data over flow control, has no named variables and has an object-oriented flavor. We prove that this model is a complete and confluent acceptable programming system and has a usable type theory. A new data synchronization primitive is introduced in order to achieve the above properties. Subtle variations of the model are shown to fall short of having all these necessary properties.

Computability by Sequences of Queries

Tyszkiewicz J.

Fundamenta Informaticae

2001

Vol. 48, nr 4

389-414

We consider a model of querying remote databases, in which we compute results of queries not supported by the database system, by using sequences of supported queries and analysing locally their results. We study the expressiveness of this model of computation, as well as its complexity, measured in terms of the number of queries used.