321.
Centrum voor Wiskunde en Informatica
- Ivan Damgaard,Ronald Cramer,Ivan Damgard,Berry Schoenmakers
Suppose we are given a proof of knowledge P in which a prover demonstrates that he knows a solution to a
given problem instance. Suppose also that we have a secret sharing scheme S on n participants. Then under
certain assumptions on P and S , we show how to transform P into a witness indistinguishable protocol, in
which the prover demonstrates knowledge of the solution to a subset of n problem instances corresponding
to a qualified set of participants. For example, using a threshold scheme, the prover can show that he
knows at least d out of n solutions without revealing which d instances...
322.
Centrum voor Wiskunde en Informatica
- K. R. Apt,R. Bol,Krzysztof R. Apt,Roland Bol
We survey here various approaches which were proposed to incorporate negation in logic
programs. We concentrate on the proof-theoretic and model-theoretic issues and the relationships
between them.
1991 Mathematics Subject Classification: 68Q40, 68T15.
CR Categories: F.3.2., F.4.1, H.3.3, I.2.3.
Keywords and Phrases: negation, general logic programs, non-monotonic reasoning.
Notes. The work of the first author was partly supported by ESPRIT Basic Research Action
6810 (Compulog 2). The work of the second author was partly supported by the Netherlands
Organization for Scientific Research (NWO). This paper will appear in Journal of Logic
Programming.
1 Introduction
1.1 Motivation
Non-monotonic reasoning grew out of attempts to capture the essential aspects of commonsense
reasoning. It resulted in...
323.
Centrum voor Wiskunde en Informatica
- M. Holsheimer,A. P. J. M. Siebes,Marcel Holsheimer,Arno Siebes
Data mining is the search for relationships and global patterns that exist in large databases, but are `hidden'
among the vast amounts of data, such as a relationship between patient data and their medical diagnosis.
These relationships represent valuable knowledge about the database and objects in the database and, if the
database is a faithful mirror, of the real world registered by the database.
One of the main problems for data mining is that the number of possible relationships is very large, thus
prohibiting the search for the correct ones by simple validating each of them. Hence, we need intelligent search
strategies, as taken from the...
324.
Centrum voor Wiskunde en Informatica
- Frits Va,Doeko Bosscher,Indra Polak,Frits Vaandrager
We analyze a simple version of a protocol developed by Philips for the physical layer of an interface bus
that connects the various devices of some stereo equipment (tuner, CD player,...). The protocol, which uses
Manchester encoding, has to deal with a significant uncertainty in the timing of events, due to both hardware
and software constraints. We present a formal specification of the protocol, and a proof of correctness for
the case where the tolerance of the clocks used within the system is less than
1
17 . A counterexample shows
that the protocol fails for tolerances greater than or equal to this value. The verification is...
325.
Centrum voor Wiskunde en Informatica
- A. Panconesi,M. Papatriantafilou,P. Tsigas,P. Vitanyi,Alessandro Panconesi,Marina Papatriantafilou
We present new distributed randomized naming protocols improving previous results in renaming and unique
processor identity protocols. They are wait-free (which implies maximal fault-tolerance) and allow stronger
adversaries. They also have low complexity. We give the first wait-free protocol achieving optimal key space
range. (This is impossible for deterministic wait-free methods, so we use randomization.) We also introduce
a novel wait-free object, a test-and-set object which upon invocation succeeds with probability less than 1,
and we give a low complexity implementation of such objects.
AMS Subject Classification (1991): 68M10, 68Q22, 68Q25
CR Subject Classification (1991): B.3.2, D.4.1, D.4.5, G.3
Keywords & Phrases: Asynchrony, Distributed Computing, Fault-tolerance, Naming, Processor...
326.
Centrum voor Wiskunde en Informatica
- N. A. Lynch,F. W. Va,Nancy Lynch,Frits Vaandrager
A comprehensive presentation of simulation techniques is given in terms of a simple (untimed)
automaton model. In particular, we discuss (1) refinements, (2) forward and backward
simulations, (3) forward-backward and backward-forward simulations, and (4) history and
prophecy relations. History and prophecy relations are new and are abstractions of the history
and prophecy variables of Abadi and Lamport, as well as the auxiliary variables of Owicki and
Gries. We give elegant and short proofs of soundness and completeness results for complicated
simulations in terms of soundness and (partial) completeness results for simple simulations.
In Part II of this paper, it is shown how most of the results for...
327.
Centrum voor Wiskunde en Informatica
- E. P. B. M. Rutten,F. Arbab,I. Herman
This report is an initial version of a formal specification of the Manifold language.
A detailed informal specification of Manifold already exists and has been used as
the basis of its first implementation. The work on formal specification of Manifold
overlapped this implementation effort and they both affected the details of the informal
specification of the language. In this report, we present an operational semantics of the
event-driven mechanism of the Manifold language.
Manifold is a parallel programming language where processes called manifolds use
an event-driven control mechanism to coordinate the communications among other
processes (manifolds as well as external). Inter-process communication in Manifold
is through broadcast of events...
328.
Centrum voor Wiskunde en Informatica
- N. A. Lynch,F. W. Va,Nancy Lynch,Frits Vaandrager
A general automaton model for timing-based systems is presented and is used as the context for
developing a variety of simulation proof techniques for such systems. These techniques include
(1) refinements, (2) forward and backward simulations, (3) forward-backward and backwardforward
simulations, and (4) history and prophecy relations. Soundness and completeness
results are given for these simulations. These results are largely analogous to the results in
Part I of this paper for untimed systems. In fact, many of the results for the timed case are
obtained as consequences of the analogous results for the untimed case.
1991 Mathematics Subject Classification: 68Q60, 68Q68.
1991 CR Categories: C.3, F.1.1, F.3.1.
Keywords and...
329.
Centrum voor Wiskunde en Informatica
- K. R. Apt,R. Bol,Krzysztof R. Apt,Roland Bol
We survey here various approaches which were proposed to incorporate negation in logic
programs. We concentrate on the proof-theoretic and model-theoretic issues and the relationships
between them.
1991 Mathematics Subject Classification: 68Q40, 68T15.
CR Categories: F.3.2., F.4.1, H.3.3, I.2.3.
Keywords and Phrases: negation, general logic programs, non-monotonic reasoning.
Notes. The work of the first author was partly supported by ESPRIT Basic Research Action
6810 (Compulog 2). The work of the second author was partly supported by the Netherlands
Organization for Scientific Research (NWO). This paper will appear in Journal of Logic
Programming.
1
330.
Centrum voor Wiskunde en Informatica
- J. R. Van Ossenbruggen,H. L. Hardman,Jacco Van Ossenbruggen,Lynda Hardman
Web publishing systems have to take into account a plethora of Web-enabled devices, user preferences and
abilities. Technologies generating these presentations will need to be explicitly aware of the context in which
the information is being presented. Semantic Web technology can be a fundamental part of the solution to
this problem by explicitly modeling the knowledge needed to adapt presentations to a specific delivery context.
331.
Centrum voor Wiskunde en Informatica
- M. De Jonge,J. M. W. Visser,Merijn De Jonge,Joost Visser
Component-based development of language tools stands in need of meta-tool support. This support can be
o#ered by generation of code -- libraries or full-fledged components -- from syntax definitions. We develop a
comprehensive architecture for such syntax-driven meta-tooling in which grammars serve as contracts between
components. This architecture addresses exchange and processing both of full parse trees and of abstract syntax
trees, and it caters for the integration of generated parse and pretty-print components with tree processing
components.
332.
Centrum voor Wiskunde en Informatica
- K. G. Dbicki,Krzystof Dbicki,Michel M
Highly-aggregated traffic in communication networks is often modeled as fractional Brow-
nian motion (fBm). This is justified by the theoretical result that the sum of a large
number of on-off inputs, with either on-times or off-times having a heavy-tailed distri-
bution with infinite variance, converges to fBm, after rescaling time appropriately. For
performance analysis purposes, the key question is whether this convergence carries over
to the stationary buffer content process. In this paper it is shown that, in a heavy-traffic
queueing environment, this property indeed holds.
333.
Centrum voor Wiskunde en Informatica
- S. M. Bohte,E. H. Gerding,J. A. La Poutr,Sander Bohte,Enrico Gerding,Han La Poutre
The amount of attention space available for recommending suppliers to consumers on e-commerce sites is
typically limited. We present a competitive distributed recommendation mechanism based on adaptive software
agents for e#ciently allocating the "consumer attention space", or banners. In the example of an electronic
shopping mall, the task is delegated to the individual shops, each of which evaluates the information that is
available about the consumer and his or her interests (e.g. keywords, product queries, and available parts of a
profile). Shops make a monetary bid in an auction where a limited amount of "consumer attention space" for
the arriving consumer is sold. Each shop is...
334.
Centrum voor Wiskunde en Informatica
- Zs. M. Ruttkay,A. D. F. Lelivre,Zsfia Ruttkay,Alban Lelivre
D faces and other graphical objects. This
report contains the extensions made for version 2.1, effecting only the Animation Editor module. The
new features allow the re-usage of a repertoire of expression snapshots and animations and
automatic generation of lip-sync from phoneme and/or viseme sequences.
335.
Centrum voor Wiskunde en Informatica
- P. W. Hemker,P. A. Farrell,G. I. Shishkin
Singularly perturbed boundary value problems for equations of elliptic and parabolic type are studied.
336.
Centrum voor Wiskunde en Informatica
- Kateryna Falkovych,Frank Nack,Jacco Van Ossenbruggen,Lloyd Rutledge
Much current research on hypermedia generation accepts user input only at the start of an
otherwise fully-automated process. However, since multimedia presentation creation is often a
complex and creative process, it has multiple phases which would each benefit from human
intervention. This paper presents a hypermedia generation model that lets the user influence all
phases of this computer-assisted human-guided process. The main focus is on providing extra
support for helping the user find relevant media items and combine them meaningfully into a
rich and coherent multimedia presentation. Like fully-automated systems, our approach uses
explicit knowledge about the presentation's topic domain, narrative structures, hypermedia
presentation and distinctions between media...
337.
Centrum voor Wiskunde en Informatica
- Wan Fokkink,Jaap-henk Hoepman,Jun Pang
We show that, contrary to common belief, Dijkstra's K-state mutual exclusion algorithm on a ring
[1, 2] also stabilizes when the number K of states per process is one less than the number N+1
of processes in the ring. We formalize the algorithm and verify the proof in PVS, based on
Qadeer and Shankar's work [8]. We show that K=N is sharp by giving a counter-example for
K=N-1.
338.
Centrum voor Wiskunde en Informatica
- A. Van Deursen,C. Hofmeister,R. Koschke,L. M. F. Moonen,C. Riva
Authentic descriptions of a software architecture are required as a reliable foundation for any
but trivial changes to a system. Far too often, architecture descriptions of existing systems are
out of sync with the implementation. If they are, they must be reconstructed. There are many
existing techniques for reconstructing individual architecture views, but no information about
how to select views for reconstruction, or about process aspects of architecture reconstruction
in general. In this paper we describe view-driven process for reconstructing software
architecture that fills this gap. To describe Symphony, we present and compare different case
studies, thus serving a secondary goal of sharing real-life reconstruction experience. The
Symphony...
339.
Centrum voor Wiskunde en Informatica
- W. H. Hundsdorfer,J. G. Verwer,J. Frank
In many applications, large systems of ordinary differential equations (ODEs) have to be
solved numerically that have both stiff and nonstiff parts. A popular approach in such
cases is to integrate the stiff parts implicitly and the nonstiff parts explicitly. In this paper
we study a class of implicit-explicit (IMEX) linear multistep methods intended for such
applications. The paper focuses on the linear stability of popular second order methods like
extrapolated BDF, Crank-Nicolson Leap-Frog and a particular class of Adams methods.
340.
Centrum voor Wiskunde en Informatica
- W. H. Hundsdorfer,J. G. Verwer,J. Frank
In many applications, large systems of ordinary di#erential equations #ODEs# havetobe
solved numerically that have both sti# and nonsti# parts. A popular approachinsuch
cases is to integrate the sti# parts implicitly and the nonsti# parts explicitly. In this paper
we study a class of implicit-explicit #IMEX# linear multistep methods intended for such
applications. The paper focuses on the linear stability of popular second order methods like
extrapolated BDF, Crank-Nicolson Leap-Frog and a particular class of Adams methods.
