Scientific Annals of Computer Science
"Alexandru Ioan Cuza" University of Iaşi
Volume XVIII, 2008
New Results on Minimal Strongly Imperfect Graphs,
pages 1-12
V. Anastasoaei and E. Olaru
Abstract |
Full text |
BibTeX
The characterization of strongly perfect graphs by a restricted
list of forbidden induced subgraphs has remained an open question
for a long time. The minimal strongly imperfect graphs which are
simultaneous imperfect are only odd holes and odd antiholes (E.
Olaru, 1996), but the entire list is not known, in spite of
a lot of particular results in this direction. In this paper we
give some new properties of the minimal strongly imperfect graphs.
Thus we introduce the notion of critical (co-critical) pair of
vertices, and we prove that any vertex of a minimal s-imperfect
(minimal c-imperfect) graph is contained in a critical
(co-critical) pair, and, in a minimal s-imperfect graph different
from a cycle of length at least 5, any vertex is the center of a
star cutset, or, if not, it belongs to a house or a domino. Also,
we characterize the triangle-free minimal s-imperfect graphs. (By
s-perfect we mean the complement of a strongly perfect graph.)
Synchronization Algorithms on Oriented Chains,
pages 13-34
D. Bein, A.K. Datta and L.L. Larmore
Abstract |
Full text |
BibTeX
We present a space- and time-optimal self-stabilizing algorithm, SSDS,
for a given synchronization problem on asynchronous oriented chains.
SSDS is uniform and works under the unfair distributed daemon.
From SSDS we derive solutions for the local mutual
exclusion and distributed sorting.
Algorithm SSDS can also be used to obtain optimal space solutions
for other problems such as broadcasting, leader election, and
mutual exclusion.
Tuplix Calculus,
pages 35-61
J.A. Bergstra, A. Ponse and M.B. Van Der Zwaag
Abstract |
Full text |
BibTeX
We introduce a calculus for tuplices,
which are expressions that generalize matrices and vectors.
Tuplices have an underlying data type for quantities
that are taken from a zero-totalized field.
We start with the core tuplix calculus CTC
for entries and tests,
which are combined using conjunctive composition.
We define a standard model and prove
that CTC is relatively complete with respect to it.
The core calculus is extended with operators for
choice, information hiding,
scalar multiplication, clearing and encapsulation.
We provide two examples of applications;
one on incremental financial budgeting,
and one on modular financial budget design.
A Calculus of Evolving Objects,
pages 63-98
M. Dezani-Ciancaglini, P. Giannini and O. Nierstrasz
Abstract |
Full text |
BibTeX
The demands of developing modern, highly dynamic applications
have led to an increasing interest in dynamic programming languages
and mechanisms. Not only must applications evolve over time, but
the object models themselves may need to be adapted to the requirements
of different run-time contexts. Class-based models and
prototype-based models, for example, may need to co-exist to meet the
demands of dynamically evolving applications. Multi-dimensional dispatch,
fine-grained and dynamic software composition, and run-time
evolution of behaviour are further examples of diverse mechanisms
which may need to co-exist in a dynamically evolving run-time environment.
How can we model the semantics of these highly dynamic
features, yet still offer some reasonable safety guarantees?
To this end we present an original calculus in which objects can
adapt their behaviour at run-time. Both objects and environments
are represented by first-class mappings between variables and values.
Message sends are dynamically resolved to method calls. Variables
may be dynamically bound, making it possible to model a variety
of dynamic mechanisms within the same calculus. Despite the highly
dynamic nature of the calculus, safety properties are assured by a type
assignment system.
An Event Based Semantics of P Systems,
pages 99-127
G.M. Pinna and A. Saba
Abstract |
Full text |
BibTeX
Membrane systems have many similarities with classical concurrency models. In particular notions like parallelism, causality and concurrency seem to belong to membrane computing, though they are not yet regarded as central or cornerstone notions.
Recently the interest in comparing membrane systems and other models for concurrency has grown. In this paper we propose a translation of membrane system into zero safe nets and then we show how to associate an event automaton to the 1-unfolding of these nets. Thus we propose an event based view of computations of a membrane system.
Involutions on Relational Program Calculi,
pages 129-171
I.M. Rewitzky and J.W. Sanders
Abstract |
Full text |
BibTeX
The standard Galois connection between the relational
and predicate-transformer models of sequential programming
(defined in terms of weakest precondition) confers
a certain similarity between them. This paper investigates the
extent to which the important involution on transformers
(which, for instance, interchanges demonic and angelic nondeterminism, and
reduces the two kinds of simulation in the relational model to one kind in
the transformer model)
carries over to relations. It is shown that no exact analogue
exists; that the two complement-based involutions are too weak
to be of much use; but that the translation to relations
of transformer involution under the Galois connection is just
strong enough to support Boolean-algebra-style reasoning, a
claim that is substantiated by proving properties of deterministic
computations. Throughout, the setting is that of the guarded-command
language augmented by the usual specification commands; and where
possible algebraic
reasoning is used in place of the more conventional semantic reasoning.
