OpenRaiser/Intern-Atlas huggingface dataset:
Analysis of Implementation Hierocrypt-3 algorithm (and its comparison to Camellia algorithm) using ALTERA devices
Venue: arXiv cs.CR 2003
Year: 2003

Alghoritms: HIEROCRYPT-3, CAMELLIA and ANUBIS, GRAND CRU, NOEKEON, NUSH, Q, RC6, SAFER++128, SC2000, SHACAL were requested for the submission of block ciphers (high level block cipher) to NESSIE (New European Schemes for Signatures, Integrity, and Encryption) project. The main purpose of this project was to put forward a portfolio of strong cryptographic primitives of various types. The NESSIE project was a three year long project and has been divided into two phases. The first was finished in June 2001r. CAMELLIA, RC6, SAFER++128 and SHACAL were accepted for the second phase of the evaluation process. HIEROCRYPT-3 had key schedule problems, and there were attacks for up to 3,5 rounds out of 6, at least hardware implementations of this cipher were extremely slow [12]. HIEROCRYPT-3 was not selected to Phase II. CAMELLIA was selected as an algorithm suggested for future standard. In the paper we present the hardware implementations these two algorithms with 128-bit blocks and 128-bit keys, using ALTERA devices and their comparisons.
What Causes a System to Satisfy a Specification?
Venue: arXiv cs.LO 2003
Year: 2003

Even when a system is proven to be correct with respect to a specification, there is still a question of how complete the specification is, and whether it really covers all the behaviors of the system. Coverage metrics attempt to check which parts of a system are actually relevant for the verification process to succeed. Recent work on coverage in model checking suggests several coverage metrics and algorithms for finding parts of the system that are not covered by the specification. The work has already proven to be effective in practice, detecting design errors that escape early verification efforts in industrial settings. In this paper, we relate a formal definition of causality given by Halpern and Pearl [2001] to coverage. We show that it gives significant insight into unresolved issues regarding the definition of coverage and leads to potentially useful extensions of coverage. In particular, we introduce the notion of responsibility, which assigns to components of a system a quantitative measure of their relevance to the satisfaction of the specification.
Greedy Algorithms in Datalog
Venue: arXiv cs.DB 2003
Year: 2003

In the design of algorithms, the greedy paradigm provides a powerful tool for solving efficiently classical computational problems, within the framework of procedural languages. However, expressing these algorithms within the declarative framework of logic-based languages has proven a difficult research challenge. In this paper, we extend the framework of Datalog-like languages to obtain simple declarative formulations for such problems, and propose effective implementation techniques to ensure computational complexities comparable to those of procedural formulations. These advances are achieved through the use of the "choice" construct, extended with preference annotations to effect the selection of alternative stable-models and nondeterministic fixpoints. We show that, with suitable storage structures, the differential fixpoint computation of our programs matches the complexity of procedural algorithms in classical search and optimization problems.
Weight Constraints as Nested Expressions
Venue: arXiv cs.AI 2003
Year: 2003

We compare two recent extensions of the answer set (stable model) semantics of logic programs. One of them, due to Lifschitz, Tang and Turner, allows the bodies and heads of rules to contain nested expressions. The other, due to Niemela and Simons, uses weight constraints. We show that there is a simple, modular translation from the language of weight constraints into the language of nested expressions that preserves the program's answer sets. Nested expressions can be eliminated from the result of this translation in favor of additional atoms. The translation makes it possible to compute answer sets for some programs with weight constraints using satisfiability solvers, and to prove the strong equivalence of programs with weight constraints using the logic of here-and there.
Mapping weblog communities
Venue: arXiv cs.NE 2003
Year: 2003

Websites of a particular class form increasingly complex networks, and new tools are needed to map and understand them. A way of visualizing this complex network is by mapping it. A map highlights which members of the community have similar interests, and reveals the underlying social network. In this paper, we will map a network of websites using Kohonen's self-organizing map (SOM), a neural-net like method generally used for clustering and visualization of complex data sets. The set of websites considered has been the Blogalia weblog hosting site (based at http://www.blogalia.com/), a thriving community of around 200 members, created in January 2002. In this paper we show how SOM discovers interesting community features, its relation with other community-discovering algorithms, and the way it highlights the set of communities formed over the network.
Using virtual processors for SPMD parallel programs
Venue: arXiv cs.DC 2003
Year: 2003

In this paper I describe some results on the use of virtual processors technology for parallelize some SPMD computational programs. The tested technology is the INTEL Hyper Threading on real processors, and the programs are MATLAB scripts for floating points computation. The conclusions of the work concern on the utility and limits of the used approach. The main result is that using virtual processors is a good technique for improving parallel programs not only for memory-based computations, but in the case of massive disk-storage operations too.
A Flexible Pragmatics-driven Language Generator for Animated Agents
Venue: arXiv cs.CL 2003
Year: 2003

This paper describes the NECA MNLG; a fully implemented Multimodal Natural Language Generation module. The MNLG is deployed as part of the NECA system which generates dialogues between animated agents. The generation module supports the seamless integration of full grammar rules, templates and canned text. The generator takes input which allows for the specification of syntactic, semantic and pragmatic constraints on the output.
On the Expressibility of Stable Logic Programming
Venue: arXiv cs.AI 2003
Year: 2003

(We apologize for pidgin LaTeX) Schlipf \cite{sch91} proved that Stable Logic Programming (SLP) solves all $\mathit{NP}$ decision problems. We extend Schlipf's result to prove that SLP solves all search problems in the class $\mathit{NP}$. Moreover, we do this in a uniform way as defined in \cite{mt99}. Specifically, we show that there is a single $\mathrm{DATALOG}^{\neg}$ program $P_{\mathit{Trg}}$ such that given any Turing machine $M$, any polynomial $p$ with non-negative integer coefficients and any input $σ$ of size $n$ over a fixed alphabet $Σ$, there is an extensional database $\mathit{edb}_{M,p,σ}$ such that there is a one-to-one correspondence between the stable models of $\mathit{edb}_{M,p,σ} \cup P_{\mathit{Trg}}$ and the accepting computations of the machine $M$ that reach the final state in at most $p(n)$ steps. Moreover, $\mathit{edb}_{M,p,σ}$ can be computed in polynomial time from $p$, $σ$ and the description of $M$ and the decoding of such accepting computations from its corresponding stable model of $\mathit{edb}_{M,p,σ} \cup P_{\mathit{Trg}}$ can be computed in linear time. A similar statement holds for Default Logic with respect to $Σ_2^\mathrm{P}$-search problems\footnote{The proof of this result involves additional technical complications and will be a subject of another publication.}.
Hinged Dissection of Polyominoes and Polyforms
Venue: arXiv cs.CG 2003
Year: 2003

A hinged dissection of a set of polygons S is a collection of polygonal pieces hinged together at vertices that can be folded into any member of S. We present a hinged dissection of all edge-to-edge gluings of n congruent copies of a polygon P that join corresponding edges of P. This construction uses kn pieces, where k is the number of vertices of P. When P is a regular polygon, we show how to reduce the number of pieces to ceiling(k/2)*(n-1). In particular, we consider polyominoes (made up of unit squares), polyiamonds (made up of equilateral triangles), and polyhexes (made up of regular hexagons). We also give a hinged dissection of all polyabolos (made up of right isosceles triangles), which do not fall under the general result mentioned above. Finally, we show that if P can be hinged into Q, then any edge-to-edge gluing of n congruent copies of P can be hinged into any edge-to-edge gluing of n congruent copies of Q.
One-way communication complexity and the Neciporuk lower bound on formula size
Venue: arXiv cs.CC 2004
Year: 2004

In this paper the Neciporuk method for proving lower bounds on the size of Boolean formulae is reformulated in terms of one-way communication complexity. We investigate the scenarios of probabilistic formulae, nondeterministic formulae, and quantum formulae. In all cases we can use results about one-way communication complexity to prove lower bounds on formula size. In the latter two cases we newly develop the employed communication complexity bounds. The main results regarding formula size are as follows: A polynomial size gap between probabilistic/quantum and deterministic formulae. A near-quadratic size gap for nondeterministic formulae with limited access to nondeterministic bits. A near quadratic lower bound on quantum formula size, as well as a polynomial separation between the sizes of quantum formulae with and without multiple read random inputs. The methods for quantum and probabilistic formulae employ a variant of the Neciporuk bound in terms of the VC-dimension. Regarding communication complexity we give optimal separations between one-way and two-way protocols in the cases of limited nondeterministic and quantum communication, and we show that zero-error quantum one-way communication complexity asymptotically equals deterministic one-way communication complexity for total functions.
An Elementary Fragment of Second-Order Lambda Calculus
Venue: arXiv cs.LO 2004
Year: 2004

A fragment of second-order lambda calculus (System F) is defined that characterizes the elementary recursive functions. Type quantification is restricted to be non-interleaved and stratified, i.e., the types are assigned levels, and a quantified variable can only be instantiated by a type of smaller level, with a slightly liberalized treatment of the level zero.
A Digital Preservation Appliance Based on OpenBSD
Venue: arXiv cs.DC 2004
Year: 2004

The LOCKSS program has developed and deployed in a world-wide test a system for preserving access to academic journals published on the Web. The fundamental problem for any digital preservation system is that it must be affordable for the long term. To reduce the cost of ownership, the LOCKSS system uses generic PC hardware, open source software, and peer-to-peer technology. It is packaged as a ``network appliance'', a single-function box that can be connected to the Internet, configured and left alone to do its job with minimal monitoring or administration. The first version of this system was based on a Linux boot floppy. After three years of testing it was replaced by a second version, based on OpenBSD and booting from CD-ROM. We focus in this paper on the design, implementation and deployment of a network appliance based on an open source operating system. We provide an overview of the LOCKSS application and describe the experience of deploying and supporting its first version. We list the requirements we took from this to drive the design of the second version, describe how we satisfied them in the OpenBSD environment, and report on the initial
Updating beliefs with incomplete observations
Venue: arXiv cs.AI 2004
Year: 2004

Currently, there is renewed interest in the problem, raised by Shafer in 1985, of updating probabilities when observations are incomplete. This is a fundamental problem in general, and of particular interest for Bayesian networks. Recently, Grunwald and Halpern have shown that commonly used updating strategies fail in this case, except under very special assumptions. In this paper we propose a new method for updating probabilities with incomplete observations. Our approach is deliberately conservative: we make no assumptions about the so-called incompleteness mechanism that associates complete with incomplete observations. We model our ignorance about this mechanism by a vacuous lower prevision, a tool from the theory of imprecise probabilities, and we use only coherence arguments to turn prior into posterior probabilities. In general, this new approach to updating produces lower and upper posterior probabilities and expectations, as well as partially determinate decisions. This is a logical consequence of the existing ignorance about the incompleteness mechanism. We apply the new approach to the problem of classification of new evidence in probabilistic expert systems, where it leads to a new, so-called conservative updating rule. In the special case of Bayesian networks constructed using expert knowledge, we provide an exact algorithm for classification based on our updating rule, which has linear-time complexity for a class of networks wider than polytrees. This result is then extended to the more general framework of credal networks, where computations are often much harder than with Bayesian nets. Using an example, we show that our rule appears to provide a solid basis for reliable updating with incomplete observations, when no strong assumptions about the incompleteness mechanism are justified.
Integrating cardinal direction relations and other orientation relations in Qualitative Spatial Reasoning
Venue: arXiv cs.AI 2004
Year: 2004

We propose a calculus integrating two calculi well-known in Qualitative Spatial Reasoning (QSR): Frank's projection-based cardinal direction calculus, and a coarser version of Freksa's relative orientation calculus. An original constraint propagation procedure is presented, which implements the interaction between the two integrated calculi. The importance of taking into account the interaction is shown with a real example providing an inconsistent knowledge base, whose inconsistency (a) cannot be detected by reasoning separately about each of the two components of the knowledge, just because, taken separately, each is consistent, but (b) is detected by the proposed algorithm, thanks to the interaction knowledge propagated from each of the two compnents to the other.
Euclidean algorithms are Gaussian
Venue: arXiv cs.DS 2004
Year: 2004

This study provides new results about the probabilistic behaviour of a class of Euclidean algorithms: the asymptotic distribution of a whole class of cost-parameters associated to these algorithms is normal. For the cost corresponding to the number of steps Hensley already has proved a Local Limit Theorem; we give a new proof, and extend his result to other euclidean algorithms and to a large class of digit costs, obtaining a faster, optimal, rate of convergence. The paper is based on the dynamical systems methodology, and the main tool is the transfer operator. In particular, we use recent results of Dolgopyat.
Disabled Access for Museum Websites
Venue: arXiv cs.CY 2004
Year: 2004

Physical disabled access is something that most museums consider very seriously. Indeed, there are normally legal requirements to do so. However, online disabled access is still a relatively novel field. Most museums have not yet considered the issues in depth. The Human-Computer Interface for their websites is normally tested with major browsers, but not with specialist browsers or against the relevant accessibility and validation standards. We consider the current state of the art in this area and mention an accessibility survey of some museum websites.
Randomized selection with tripartitioning
Venue: arXiv cs.DS 2004
Year: 2004

We show that several versions of Floyd and Rivest's algorithm Select [Comm.\ ACM {\bf 18} (1975) 173] for finding the $k$th smallest of $n$ elements require at most $n+\min\{k,n-k\}+o(n)$ comparisons on average, even when equal elements occur. This parallels our recent analysis of another variant due to Floyd and Rivest [Comm. ACM {\bf 18} (1975) 165--172]. Our computational results suggest that both variants perform well in practice, and may compete with other selection methods, such as Hoare's Find or quickselect with median-of-3 pivots.
Unifying Computing and Cognition: The SP Theory and its Applications
Venue: arXiv cs.AI 2004
Year: 2004

This book develops the conjecture that all kinds of information processing in computers and in brains may usefully be understood as "information compression by multiple alignment, unification and search". This "SP theory", which has been under development since 1987, provides a unified view of such things as the workings of a universal Turing machine, the nature of 'knowledge', the interpretation and production of natural language, pattern recognition and best-match information retrieval, several kinds of probabilistic reasoning, planning and problem solving, unsupervised learning, and a range of concepts in mathematics and logic. The theory also provides a basis for the design of an 'SP' computer with several potential advantages compared with traditional digital computers.
On the Cost of Participating in a Peer-to-Peer Network
Venue: arXiv cs.NI 2004
Year: 2004

In this paper, we model the cost incurred by each peer participating in a peer-to-peer network. Such a cost model allows to gauge potential disincentives for peers to collaborate, and provides a measure of the ``total cost'' of a network, which is a possible benchmark to distinguish between proposals. We characterize the cost imposed on a node as a function of the experienced load and the node connectivity, and show how our model applies to a few proposed routing geometries for distributed hash tables (DHTs). We further outline a number of open questions this research has raised.
A Use-Case Driven Approach in Requirements Engineering : The Mammogrid Project
Venue: arXiv cs.DB 2004
Year: 2004

We report on the application of the use-case modeling technique to identify and specify the user requirements of the MammoGrid project in an incremental and controlled iterative approach. Modeling has been carried out in close collaboration with clinicians and radiologists with no prior experience of use cases. The study reveals the advantages and limitations of applying this technique to requirements specification in the domains of breast cancer screening and mammography research, with implications for medical imaging more generally. In addition, this research has shown a return on investment in use-case modeling in shorter gaps between phases of the requirements engineering process. The qualitative result of this analysis leads us to propose that a use-case modeling approach may result in reducing the cycle of the requirements engineering process for medical imaging.
Resolving Clinicians Queries Across a Grids Infrastructure
Venue: arXiv cs.DB 2004
Year: 2004

The past decade has witnessed order of magnitude increases in computing power, data storage capacity and network speed, giving birth to applications which may handle large data volumes of increased complexity, distributed over the Internet. Grids computing promises to resolve many of the difficulties in facilitating medical image analysis to allow radiologists to collaborate without having to co-locate. The EU-funded MammoGrid project aims to investigate the feasibility of developing a Grid-enabled European database of mammograms and provide an information infrastructure which federates multiple mammogram databases. This will enable clinicians to develop new common, collaborative and co-operative approaches to the analysis of mammographic data. This paper focuses on one of the key requirements for large-scale distributed mammogram analysis: resolving queries across a grid-connected federation of images.
A perspective on the Healthgrid initiative
Venue: arXiv cs.DB 2004
Year: 2004

This paper presents a perspective on the Healthgrid initiative which involves European projects deploying pioneering applications of grid technology in the health sector. In the last couple of years, several grid projects have been funded on health related issues at national and European levels. A crucial issue is to maximize their cross fertilization in the context of an environment where data of medical interest can be stored and made easily available to the different actors in healthcare, physicians, healthcare centres and administrations, and of course the citizens. The Healthgrid initiative, represented by the Healthgrid association (http://www.healthgrid.org), was initiated to bring the necessary long term continuity, to reinforce and promote awareness of the possibilities and advantages linked to the deployment of GRID technologies in health. Technologies to address the specific requirements for medical applications are under development. Results from the DataGrid and other projects are given as examples of early applications.
On the Inertia of the Asynchronous Circuits
Venue: arXiv cs.LO 2004
Year: 2004

We present the bounded delays, the absolute inertia and the relative inertia.
Parameter-less Optimization with the Extended Compact Genetic Algorithm and Iterated Local Search
Venue: arXiv cs.NE 2004
Year: 2004

This paper presents a parameter-less optimization framework that uses the extended compact genetic algorithm (ECGA) and iterated local search (ILS), but is not restricted to these algorithms. The presented optimization algorithm (ILS+ECGA) comes as an extension of the parameter-less genetic algorithm (GA), where the parameters of a selecto-recombinative GA are eliminated. The approach that we propose is tested on several well known problems. In the absence of domain knowledge, it is shown that ILS+ECGA is a robust and easy-to-use optimization method.
Digital Signal Transmission with Chaotic Encryption: Design and Evaluation of a FPGA Realization
Venue: arXiv cs.CR 2004
Year: 2004

A discrete-time discrete-value pseudo-chaotic encoder/decoder system is presented. The pseudo-chaotic module is a 3D discrete version of the well-known Lorenz dynamical system. Scaling and biasing transformations as well as natural number arithmetics are employed in order to simplify realizations on a small size Field Programmable Gate Array (FPGA. The encryption ability is improved by using only the least significant byte of one of the pseudo chaotic state variables as the key to encrypt the plain text. The key is periodically perturbed by another chaotic state variable. The statistical properties of the pseudo chaotic cipher are compared with those of other pseudo-random generators available in the literature. As an example of applicability of the technique, a full duplex communication system is designed and constructed using FPGA's as technological framework.