Fundamenta Informaticae - Volume 44, issue 1-2

Authors: Aho, Isto

Article Type: Research Article

Abstract: The interactive knapsack problems are generalizations of the classical knapsack problem. Three different new NP-complete problems, interactive knapsack heuristic decision problem (IKHD), interactive knapsack decision problem (IKD) and multidimensional cloned knapsack decision problem (MDCS), are presented for the interactive knapsack models. IKD and MDCS are shown to be strongly NP-complete. By using interactive knapsacks we can model many planning and scheduling problems in an innovative way. Possible application areas include electricity …management, single and multiprocessor scheduling, and packing and tiling problems. As a by-product we show that the longest weight-constrained path problem is NP-complete. Show more

Keywords: Knapsack problem, knapsack models, longest path, NP-complete

Citation: Fundamenta Informaticae, vol. 44, no. 1-2, pp. 1-23, 2000

Authors: Büchi, Martin | Sekerinski, Emil

Article Type: Research Article

Abstract: We study the notion of class refinement in a concurrent object-oriented setting. Our model is based on a combination of action systems and classes. An action system describes the behavior of a concurrent, distributed, or interactive system in terms of the atomic actions that can take place during the execution of the system. Classes serve as templates for creating objects. To express concurrency with objects, we add actions to classes. We define class refinement based on …trace refinement of action systems. Additionally, we give a simulation-based proof rule. We show that the easier to apply simulation rule implies the trace-based definition of class refinement. Class refinement embraces algorithmic refinement, data refinement, and atomicity refinement. Atomicity refinement allows us to split large atomic actions into several smaller ones. Thereby, it paves the way for more parallelism. We investigate the special case of atomicity refinement by early returns in methods. Show more

Keywords: concurrent objects, classes, inheritance, subtyping, action systems, atomicity refinement, class refinement, simulation, early return

Citation: Fundamenta Informaticae, vol. 44, no. 1-2, pp. 25-61, 2000

Authors: Chrobot, Stanislaw

Article Type: Research Article

Abstract: In the classical shared-variable models, component processes reside on their processors and communicate by shared variables in memory shared by the processors. In this paper, we argue that shared memory is not necessary to share variables. Processes can share variables in local memories of processors if they travel among the processors. We present a formal distributed memory model in which a system can be decomposed into processes residing on processors and communicating by message passing or …into processes travelling among processors and communicating by shared variables. We call this property communication dualism of distributed systems. We point out that the shared-memory monitor can be used in distributed memory and suggest that variable sharing is a convenient alternative to message passing. We also point out that a mobile agent is a kind of travelling process, but its prominent property, code mobility, is not related to shared-variable communication. Show more

Keywords: Distributed systems, shared-variable and message-passing models, communication dualism, integrated communication model, travelling processes

Citation: Fundamenta Informaticae, vol. 44, no. 1-2, pp. 63-81, 2000

Authors: Csuhaj-Varjú, Erzsébet | Mitrana, Victor

Article Type: Research Article

Abstract: In this paper we investigate simple eco-grammar systems with dynamically formed teams of agents. Three natural conditions for constituting a team, based on the agents' current capability of activation, are considered. We study the relations of language classes of these simple eco-grammar systems to each other and to some other well-known classes of languages. Moreover, we prove that any recursively enumerable language can be obtained as the intersection of a regular language and the language of …a simple eco-grammar system where the acting teams of agents are formed according to two of the above conditions. Show more

Keywords: Simple eco-grammar system, level of excitation, team, computational power

Citation: Fundamenta Informaticae, vol. 44, no. 1-2, pp. 83-94, 2000

Authors: Doherty, Patrick | Łukaszewicz, Witold | Madalińska-Bugaj, Ewa

Article Type: Research Article

Abstract: Recently, a great deal of progress has been made using nonmonotonic temporal logics to formalize reasoning about action and change. In particular, much focus has been placed on the proper representation of non-deterministic actions and the indirect effects of actions. For the latter the use of causal or fluent dependency rule approaches has been dominant. Although much recent effort has also been spent applying the belief revision/update (BR/U) approach to the action and change domain, …there has been less progress in dealing with nondeterministic update and indirect effects represented as integrity constraints. We demonstrate that much is to be gained by cross-fertilization between the two paradigms and we show this in the following manner. We first propose a generalization of the PMA, called the modified MPMA which uses intuitions from the TL paradigm to permit representation of nondeterministic update and the use of integrity constraints interpreted as causal or fluent dependency rules. We provide several syntactic characterizations of MPMA, one of which is in terms of a simple temporal logic and provide a representation theorem showing equivalence between the two. In constructing the MPMA, we discovered a syntactic anomaly which we call the {\em redundant atom anomaly} that many TL approaches suffer from. We provide a method for avoiding the problem which is equally applicable across paradigms. We also describe a syntactic characterization of MPMA in terms of Dijkstra semantics. We set up a framework for future generalization of the BR/U approach and conclude with a formal comparison of related approaches. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 44, no. 1-2, pp. 95-131, 2000

Authors: Intrigila, Benedetto | Laurenzi, Anna R.

Article Type: Research Article

Abstract: In this paper we solve two open problems in the theory of reduction graphs in lambda calculus. The first question is whether the condensed reduction graph of a lambda term is always locally finite (conjecture of M.Venturini Zilli 1984). We give a negative answer to the conjecture by providing a counterexample. The second problem is whether there is a term such that its reduction graph is composed of two reduction cycles (not loops) intersecting in just …one point (problem of J.W.Klop 1980). We show that such a term cannot exist. Show more

Keywords: Lambda calculus, reduction graphs, reduction cycles

Citation: Fundamenta Informaticae, vol. 44, no. 1-2, pp. 133-144, 2000

Authors: Ivanov, Lyubomir

Article Type: Research Article

Abstract: The aim of this work is to axiomatize and enhance the recursion theory on monotonic hierarchies of operative spaces developed in [1]. This is to be accomplished by employing a special new variety of operative spaces called Platek spaces. The original structure studied by Platek in [2] corresponds to the particular Platek space with structural class O=ω and a bottom operative space consisting of single-valued partial functions over an arbitrary domain (Example 1.1 below). We …believe that Platek spaces not only redefine Platek's approach in an abstract manner, but also provide the appropriate setting for an intrinsic Generalized Recursion Theory. Show more

Keywords: generalised recursion theory, computability, lightface recursion, combinatory algebra, Platek spaces

Citation: Fundamenta Informaticae, vol. 44, no. 1-2, pp. 145-181, 2000

Authors: Ivanov, Lyubomir

Article Type: Research Article

Abstract: The present work develops a boldface version of the theory of Platek spaces initiated by [2]. This is done by studying recursion on spaces with special elements which embody the so called transfer operation of [1], Chapter 14 affording full lambda-abstraction. Transfer is characteristic of the monotonic hierarchies of operative spaces, which hierarchies form models of a typed lambda-mu-calculus. The principal result here is a boldface version of the abstract Platek First Recursion Theorem of …[2]; we prove appropriate boldface Enumeration and Second Recursion Theorems as well. Show more

Keywords: generalised recursion theory, computability, boldface recursion, combinatory algebra, Platek spaces

Citation: Fundamenta Informaticae, vol. 44, no. 1-2, pp. 183-208, 2000