Isto Aho 1-23
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.
Martin Büchi and Emil Sekerinski 25-61
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.
Stanislaw Chrobot 63-81
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.
Erzsébet Csuhaj-Varjú and Victor Mitrana 83-94
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.
Patrick Doherty, Witold ukaszewicz and Ewa Madali\'nska-Bugaj 95-131
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 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.
Benedetto Intrigila and Anna R. Laurenzi 133-144
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.
Lyubomir Ivanov 145-181
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 = w 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.
Lyubomir Ivanov 183-208
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.
Nadia Busi and G. Michele Pinna 209-244
The paper is centered around the study and comparison of truly concurrent semantics for P/T nets with inhibitor and read arcs (called henceforth contextual P/T nets). We start proposing a causal semantics for P/T nets, that we prove to be equivalent to history preserving bisimulation defined on nonsequential processes. Then we develop a conservative extension of the causal semantics to contextual P/T nets and we prove this one to be finer than step semantics. Finally, a comparison of causal semantics with the process based semantics for contextual P/T systems proposed in [7] is carried out.
Pavel Martinek 245-264
The grammatical inference problem is solved for the class of
context-free languages. A context-free language is supposed to be
given by means of all its strings. Considering all strings of
length bounded by k, context-free grammars Gj,k with 1 £ j < k are constructed. A continual increasing of the
index k leads to an infinite sequence (Gj,k)j < k. It is
proved that Gj,k are equivalent for all j ³ j0, k ³ k0 with some positive integers j0, k0. Moreover, the
equivalences among these grammars can be recognized on the basis
of involved nonterminals and productions only.
Étienne Payet 265-290
This paper presents some formal verification-oriented results about the class of graphs associated with Thue specifications. It is shown that this class is closed, up to isomorphism, under synchronized product. It is also established that every rational graph with no edge labeled by the empty word is isomorphic to the graph of a Thue specification. A consequence of this result is that the first-order theory of the graphs of Thue specifications is undecidable. Connections between graphs of Thue specifications and those of Turing machines are finally investigated. The main result is that the graph of each Thue specification is observationally equivalent to that of a Turing machine but the reverse does not hold.
Dominik ¦lęzak 291-319
We consider the family of normalized decision functions acting over conditional frequency distributions computed from data tables. We draw the connection between such functions and approaches to generating inexact decision rules for the new case classification. We also introduce the family of normalized decision measures corresponding to particular decision functions. They enable us to express efficiency of particular strategies of reasoning with respect to a given data. We show the properties of approximate decision rules and decision reducts based on normalized decision functions and measures. As a result, we obtain an intuitive and flexible tool for extracting approximate classification models from data.
Anastasia Analyti, Nicolas Spyratos and Panos Constantopoulos 321-351
In semantic and object-oriented data models, each class has one or more typing properties that associate it to other classes, and carry type information about all instances of the class. We introduce a new kind of property that we call instance-typing property. An instance-typing property associates an instance of a class to another class, and carries type information about that particular instance (and not about all instances of the class). Instance-typing properties are important as they allow to represent summary information about an instance, in addition to specific information.
In this paper, we study inheritance of properties from a class to an instance, using type information about the class, as well as type information about the instance. This kind of inheritance, that we call contextual instance-inheritance, provides us with the most specific type information about the instance, in a particular context. Intuitively, a context is a metaclass of interest with respect to which this most specific information is determined.
We demonstrate that contextual instance-inheritance is a powerful conceptual modeling mechanism, capable of expressing valuable information about instances. We also provide a framework in which derived instance-inherited properties can be represented and retrieved in the same way as ``usual'' properties.
Jürgen Dassow, Carlos Martín-Vide , Gheorghe P aun and Alfonso
Rodríguez-Patón
353-372
Inspired from biochemistry and DNA computing, we introduce several variants of controlled concatenation of strings and languages: a finite set of pairs of strings is given and two arbitrary strings are concatenated only when among their substrings (scattered substrings, of various forms) we can find a pair in this control set. Five types of non-iterated and iterated (like Kleene closure) conditional concatenations are considered. The closure properties of abstract families of languages (hence also of families in the Chomsky hierarchy) are settled. They are similar to the closure properties under usual concatenation and Kleene closure. A representation of regular languages in terms of these operations (and a coding) is also given. Then, we use the new concatenation operations as basic operations in Chomsky grammars: rewriting a nonterminal means concatenating a new string with the strings to the left and the right of that nonterminal, hence restricted concatenations can be used. Context-free grammars working in this restricted manner can generate non-context-free languages; in one case, characterizations of recursively enumerable or of context-sensitive languages are obtained, depending on using or not erasing rules. Some topics for further research are also suggested.
Stéphane Demri and Jarosław Stepaniuk 373-396
We characterize the computational complexity of a family of approximation multimodal logics in which interdependent modal connectives are part of the language. Those logics have been designed to reason in presence of incomplete information in the sense of rough set theory. More precisely, we show that all the logics have a PSPACE-complete satisfiability problem and we define a family of tolerance approximation multimodal logics whose satisfiability is EXPTIME-complete. This illustrates that the PSPACE upper bound for this kind of multimodal logics is a very special feature of such logics. The PSPACE upper bounds are established by adequately designing Ladner-style tableaux-based procedures whereas the EXPTIME lower bound is established by reduction from the global satisfiability problem for the standard modal logic B.
Agnes Kurucz and István Németi 397-420
We consider classes of relation algebras expanded with new operations based on the formation of ordered pairs. Examples for such algebras are pairing (or projection) algebras of algebraic logic and fork algebras of computer science. It is proved by Sain and Németi [38] that there is no `strong' representation theorem for all abstract pairing algebras in most set theories including ZFC as well as most non-well-founded set theories. Such a `strong' representation theorem would state that every abstract pairing algebra is isomorphic to a set relation algebra having projection elements which are defined with the help of the real (set theoretic) pairing function. Here we show that, by choosing an appropriate (non-well-founded) set theory as our metatheory, pairing algebras and fork algebras admit such `strong' representation theorems.