OpenRaiser/Intern-Atlas huggingface dataset:
On the graph coloring check-digit scheme with applications to verifiable secret sharing
Venue: arXiv cs.CR 2002
Year: 2002

In the paper we apply graph vertex coloring for verification of secret shares. We start from showing how to convert any graph into the number and vice versa. Next, theoretical result concerning properties of n-colorable graphs is stated and proven. From this result we derive graph coloring check-digit scheme. Feasibility of proposed scheme increases with the size of the number, which digits are checked and overall probability of errors. The check-digit scheme is used to build shares verification method that does not require cooperation of the third party. It allows implementing verification structure different from the access structure. It does not depend on particular secret sharing method. It can be used as long as the secret shares can be represented by numbers or graphs.
Knowledge Representation
Venue: arXiv cs.AI 2002
Year: 2002

This work analyses main features that should be present in knowledge representation. It suggests a model for representation and a way to implement this model in software. Representation takes care of both low-level sensor information and high-level concepts.
A direct time-domain FEM modeling of broadband frequency-dependent absorption with the presence of matrix fractional power: Model I
Venue: arXiv cs.CE 2002
Year: 2002

The frequency-dependent attenuation of broadband acoustics is often confronted in many different areas. However, the related time domain simulation is rarely found in literature due to enormous technical difficulty. The currently popular relaxation models with the presence of convolution operation require some material parameters which are not readily available. In this study, three reports are contributed to address broadband ultrasound frequency-dependent absorptions using the readily available empirical parameters. This report is the first in series concerned with developing a direct time domain FEM formulation. The next two reports are about the frequency decomposition model and the fractional derivative model.
First-order Logic as a Constraint Programming Language
Venue: arXiv cs.LO 2002
Year: 2002

We provide a denotational semantics for first-order logic that captures the two-level view of the computation process typical for constraint programming. At one level we have the usual program execution. At the other level an automatic maintenance of the constraint store takes place. We prove that the resulting semantics is sound with respect to the truth definition. By instantiating it by specific forms of constraint management policies we obtain several sound evaluation policies of first-order formulas. This semantics can also be used a basis for sound implementation of constraint maintenance in presence of block declarations and conditionals.
Complete Axiomatizations for Reasoning About Knowledge and Time
Venue: arXiv cs.LO 2002
Year: 2002

Sound and complete axiomatizations are provided for a number of different logics involving modalities for knowledge and time. These logics arise from different choices for various parameters. All the logics considered involve the discrete time linear temporal logic operators `next' and `until' and an operator for the knowledge of each of a number of agents. Both the single agent and multiple agent cases are studied: in some instances of the latter there is also an operator for the common knowledge of the group of all agents. Four different semantic properties of agents are considered: whether they have a unique initial state, whether they operate synchronously, whether they have perfect recall, and whether they learn. The property of no learning is essentially dual to perfect recall. Not all settings of these parameters lead to recursively axiomatizable logics, but sound and complete axiomatizations are presented for all the ones that do.
Reference Resolution Beyond Coreference: a Conceptual Frame and its Application
Venue: arXiv cs.CL 2002
Year: 2002

A model for reference use in communication is proposed, from a representationist point of view. Both the sender and the receiver of a message handle representations of their common environment, including mental representations of objects. Reference resolution by a computer is viewed as the construction of object representations using referring expressions from the discourse, whereas often only coreference links between such expressions are looked for. Differences between these two approaches are discussed. The model has been implemented with elementary rules, and tested on complex narrative texts (hundreds to thousands of referring expressions). The results support the mental representations paradigm.
A Virtual Library of Technical Publications
Venue: arXiv cs.DL 2002
Year: 2002

Through a collaborative effort, the Fermilab Information Resources Department and Computing Division have created a "virtual library" of technical publications that provides public access to electronic full-text documents. This paper will discuss the vision, planning and milestones of the project, as well as the hardware, software and interdepartmental cooperation components.
Perfectly Secure Message Transmission Revisited
Venue: arXiv cs.CR 2002
Year: 2002

Achieving secure communications in networks has been one of the most important problems in information technology. Dolev, Dwork, Waarts, and Yung have studied secure message transmission in one-way or two-way channels. They only consider the case when all channels are two-way or all channels are one-way. Goldreich, Goldwasser, and Linial, Franklin and Yung, Franklin and Wright, and Wang and Desmedt have studied secure communication and secure computation in multi-recipient (multicast) models. In a ``multicast channel'' (such as Ethernet), one processor can send the same message--simultaneously and privately--to a fixed subset of processors. In this paper, we shall study necessary and sufficient conditions for achieving secure communications against active adversaries in mixed one-way and two-way channels. We also discuss multicast channels and neighbor network channels.
Gales Suffice for Constructive Dimension
Venue: arXiv cs.CC 2002
Year: 2002

Supergales, generalizations of supermartingales, have been used by Lutz (2002) to define the constructive dimensions of individual binary sequences. Here it is shown that gales, the corresponding generalizations of martingales, can be equivalently used to define constructive dimension.
The partition semantics of questions, syntactically
Venue: arXiv cs.CL 2002
Year: 2002

Groenendijk and Stokhof (1984, 1996; Groenendijk 1999) provide a logically attractive theory of the semantics of natural language questions, commonly referred to as the partition theory. Two central notions in this theory are entailment between questions and answerhood. For example, the question "Who is going to the party?" entails the question "Is John going to the party?", and "John is going to the party" counts as an answer to both. Groenendijk and Stokhof define these two notions in terms of partitions of a set of possible worlds. We provide a syntactic characterization of entailment between questions and answerhood . We show that answers are, in some sense, exactly those formulas that are built up from instances of the question. This result lets us compare the partition theory with other approaches to interrogation -- both linguistic analyses, such as Hamblin's and Karttunen's semantics, and computational systems, such as Prolog. Our comparison separates a notion of answerhood into three aspects: equivalence (when two questions or answers are interchangeable), atomic answers (what instances of a question count as answers), and compound answers (how answers compose).
Gossip Based Ad-Hoc Routing
Venue: arXiv cs.NI 2002
Year: 2002

Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based approach, where each node forwards a message with some probability, to reduce the overhead of the routing protocols. Gossiping exhibits bimodal behavior in sufficiently large networks: in some executions, the gossip dies out quickly and hardly any node gets the message; in the remaining executions, a substantial fraction of the nodes gets the message. The fraction of executions in which most nodes get the message depends on the gossiping probability and the topology of the network. In the networks we have considered, using gossiping probability between 0.6 and 0.8 suffices to ensure that almost every node gets the message in almost every execution. For large networks, this simple gossiping protocol uses up to 35% fewer messages than flooding, with improved performance. Gossiping can also be combined with various optimizations of flooding to yield further benefits. Simulations show that adding gossiping to AODV results in significant performance improvement, even in networks as small as 150 nodes. We expect that the improvement should be even more significant in larger networks.
Randomized protocols for asynchronous consensus
Venue: arXiv cs.DS 2002
Year: 2002

The famous Fischer, Lynch, and Paterson impossibility proof shows that it is impossible to solve the consensus problem in a natural model of an asynchronous distributed system if even a single process can fail. Since its publication, two decades of work on fault-tolerant asynchronous consensus algorithms have evaded this impossibility result by using extended models that provide (a) randomization, (b) additional timing assumptions, (c) failure detectors, or (d) stronger synchronization mechanisms than are available in the basic model. Concentrating on the first of these approaches, we illustrate the history and structure of randomized asynchronous consensus protocols by giving detailed descriptions of several such protocols.
Evolution and Gravitation: a Computer Simulation of a Non-Walrasian Equilibrium Model
Venue: arXiv cs.CY 2002
Year: 2002

The paper contains a computer simulation concerning a basic non-Walrasian equilibrium system, following the Edmond Malinvaud "short side" approach, as far as the price adjustment is concerned, and the sequential Hicksian "weeks" structure with regard of the temporal characterization.
A generalization of Amdahl's law and relative conditions of parallelism
Venue: arXiv cs.DC 2002
Year: 2002

In this work I present a generalization of Amdahl's law on the limits of a parallel implementation with many processors. In particular I establish some mathematical relations involving the number of processors and the dimension of the treated problem, and with these conditions I define, on the ground of the reachable speedup, some classes of parallelism for the implementations. I also derive a condition for obtaining superlinear speedup. The used mathematical technics are those of differential calculus. I describe some examples from classical problems offered by the specialized literature on the subject.
Positive time fractional derivative
Venue: arXiv cs.CE 2002
Year: 2002

In mathematical modeling of the non-squared frequency-dependent diffusions, also known as the anomalous diffusions, it is desirable to have a positive real Fourier transform for the time derivative of arbitrary fractional or odd integer order. The Fourier transform of the fractional time derivative in the Riemann-Liouville and Caputo senses, however, involves a complex power function of the fractional order. In this study, a positive time derivative of fractional or odd integer order is introduced to respect the positivity in modeling the anomalous diffusions.
Integration and interoperability accessing electronic information resources in science and technology: the proposal of Brazilian Digital Library
Venue: arXiv cs.DL 2002
Year: 2002

This paper describes technological and methodological options to achieve interoperability in accessing electronic information resources, available in Internet, in the scope of Brazilian Digital Library in Science and Technology Project - BDL, developed by Brazilian Institute for Scientific and Technical Information - IBICT. It stresses the impact of the Web in the publishing and communication processes in science and technology and also in the information systems and libraries. The work points out the two major objectives of the BDL Project: facilitates electronic publishing of different full text materials such as theses, journal articles, conference papers,grey literature - by Brazilian scientific community, so amplifying their nationally and internationally visibility; and achieving, through a unified gateway, thus avoiding a user to navigate and query across different information resources individually. The work explains technological options and standards that will assure interoperability in this context.
Algorithmic scalability in globally constrained conservative parallel discrete event simulations of asynchronous systems
Venue: arXiv cs.DC 2002
Year: 2002

We consider parallel simulations for asynchronous systems employing L processing elements that are arranged on a ring. Processors communicate only among the nearest neighbors and advance their local simulated time only if it is guaranteed that this does not violate causality. In simulations with no constraints, in the infinite L-limit the utilization scales (Korniss et al, PRL 84, 2000); but, the width of the virtual time horizon diverges (i.e., the measurement phase of the algorithm does not scale). In this work, we introduce a moving window global constraint, which modifies the algorithm so that the measurement phase scales as well. We present results of systematic studies in which the system size (i.e., L and the volume load per processor) as well as the constraint are varied. The constraint eliminates the extreme fluctuations in the virtual time horizon, provides a bound on its width, and controls the average progress rate. The width of the window constraint can serve as a tuning parameter that, for a given volume load per processor, could be adjusted to optimize the utilization so as to maximize the efficiency. This result may find numerous applications in modeling the evolution of general spatially extended short-range interacting systems with asynchronous dynamics, including dynamic Monte Carlo studies.
XCB, the Last of the Shortest Single Axioms for the Classical Equivalential Calculus
Venue: arXiv cs.LO 2002
Year: 2002

It has long been an open question whether the formula XCB = EpEEEpqErqr is, with the rules of substitution and detachment, a single axiom for the classical equivalential calculus. This paper answers that question affirmatively, thus completing a search for all such eleven-symbol single axioms that began seventy years ago.
SkyQuery: A WebService Approach to Federate Databases
Venue: arXiv cs.DB 2002
Year: 2002

Traditional science searched for new objects and phenomena that led to discoveries. Tomorrow's science will combine together the large pool of information in scientific archives and make discoveries. Scienthists are currently keen to federate together the existing scientific databases. The major challenge in building a federation of these autonomous and heterogeneous databases is system integration. Ineffective integration will result in defunct federations and under utilized scientific data. Astronomy, in particular, has many autonomous archives spread over the Internet. It is now seeking to federate these, with minimal effort, into a Virtual Observatory that will solve complex distributed computing tasks such as answering federated spatial join queries. In this paper, we present SkyQuery, a successful prototype of an evolving federation of astronomy archives. It interoperates using the emerging Web services standard. We describe the SkyQuery architecture and show how it efficiently evaluates a probabilistic federated spatial join query.
Annotations for HTML to VoiceXML Transcoding: Producing Voice WebPages with Usability in Mind
Venue: arXiv cs.HC 2002
Year: 2002

Web pages contain a large variety of information, but are largely designed for use by graphical web browsers. Mobile access to web-based information often requires presenting HTML web pages using channels that are limited in their graphical capabilities such as small-screens or audio-only interfaces. Content transcoding and annotations have been explored as methods for intelligently presenting HTML documents. Much of this work has focused on transcoding for small-screen devices such as are found on PDAs and cell phones. Here, we focus on the use of annotations and transcoding for presenting HTML content through a voice user interface instantiated in VoiceXML. This transcoded voice interface is designed with an assumption that it will not be used for extended web browsing by voice, but rather to quickly gain directed access to information on web pages. We have found repeated structures that are common in the presentation of data on web pages that are well suited for voice presentation and navigation. In this paper, we describe these structures and their use in an annotation system we have implemented that produces a VoiceXML interface to information originally embedded in HTML documents. We describe the transcoding process used to translate HTML into VoiceXML, including transcoding features we have designed to lead to highly usable VoiceXML code.
A Model for Combination of External and Internal Stimuli in the Action Selection of an Autonomous Agent
Venue: arXiv cs.AI 2002
Year: 2002

This paper proposes a model for combination of external and internal stimuli for the action selection in an autonomous agent, based in an action selection mechanism previously proposed by the authors. This combination model includes additive and multiplicative elements, which allows to incorporate new properties, which enhance the action selection. A given parameter a, which is part of the proposed model, allows to regulate the degree of dependence of the observed external behaviour from the internal states of the entity.
Mining the Web for Lexical Knowledge to Improve Keyphrase Extraction: Learning from Labeled and Unlabeled Data
Venue: arXiv cs.LG 2002
Year: 2002

Keyphrases are useful for a variety of purposes, including summarizing, indexing, labeling, categorizing, clustering, highlighting, browsing, and searching. The task of automatic keyphrase extraction is to select keyphrases from within the text of a given document. Automatic keyphrase extraction makes it feasible to generate keyphrases for the huge number of documents that do not have manually assigned keyphrases. Good performance on this task has been obtained by approaching it as a supervised learning problem. An input document is treated as a set of candidate phrases that must be classified as either keyphrases or non-keyphrases. To classify a candidate phrase as a keyphrase, the most important features (attributes) appear to be the frequency and location of the candidate phrase in the document. Recent work has demonstrated that it is also useful to know the frequency of the candidate phrase as a manually assigned keyphrase for other documents in the same domain as the given document (e.g., the domain of computer science). Unfortunately, this keyphrase-frequency feature is domain-specific (the learning process must be repeated for each new domain) and training-intensive (good performance requires a relatively large number of training documents in the given domain, with manually assigned keyphrases). The aim of the work described here is to remove these limitations. In this paper, I introduce new features that are derived by mining lexical knowledge from a very large collection of unlabeled data, consisting of approximately 350 million Web pages without manually assigned keyphrases. I present experiments that show that the new features result in improved keyphrase extraction, although they are neither domain-specific nor training-intensive.
Classes of Spatiotemporal Objects and Their Closure Properties
Venue: arXiv cs.DB 2002
Year: 2002

We present a data model for spatio-temporal databases. In this model spatio-temporal data is represented as a finite union of objects described by means of a spatial reference object, a temporal object and a geometric transformation function that determines the change or movement of the reference object in time. We define a number of practically relevant classes of spatio-temporal objects, and give complete results concerning closure under Boolean set operators for these classes. Since only few classes are closed under all set operators, we suggest an extension of the model, which leads to better closure properties, and therefore increased practical applicability. We also discuss a normal form for this extended data model.
The Management of Context-Sensitive Features: A Review of Strategies
Venue: arXiv cs.LG 2002
Year: 2002

In this paper, we review five heuristic strategies for handling context-sensitive features in supervised machine learning from examples. We discuss two methods for recovering lost (implicit) contextual information. We mention some evidence that hybrid strategies can have a synergetic effect. We then show how the work of several machine learning researchers fits into this framework. While we do not claim that these strategies exhaust the possibilities, it appears that the framework includes all of the techniques that can be found in the published literature on contextsensitive learning.
Data Engineering for the Analysis of Semiconductor Manufacturing Data
Venue: arXiv cs.LG 2002
Year: 2002

We have analyzed manufacturing data from several different semiconductor manufacturing plants, using decision tree induction software called Q-YIELD. The software generates rules for predicting when a given product should be rejected. The rules are intended to help the process engineers improve the yield of the product, by helping them to discover the causes of rejection. Experience with Q-YIELD has taught us the importance of data engineering -- preprocessing the data to enable or facilitate decision tree induction. This paper discusses some of the data engineering problems we have encountered with semiconductor manufacturing data. The paper deals with two broad classes of problems: engineering the features in a feature vector representation and engineering the definition of the target concept (the classes). Manufacturing process data present special problems for feature engineering, since the data have multiple levels of granularity (detail, resolution). Engineering the target concept is important, due to our focus on understanding the past, as opposed to the more common focus in machine learning on predicting the future.
Computing Conformal Structure of Surfaces
Venue: arXiv cs.GR 2002
Year: 2002

This paper solves the problem of computing conformal structures of general 2-manifolds represented as triangle meshes. We compute conformal structures in the following way: first compute homology bases from simplicial complex structures, then construct dual cohomology bases and diffuse them to harmonic 1-forms. Next, we construct bases of holomorphic differentials. We then obtain period matrices by integrating holomorphic differentials along homology bases. We also study the global conformal mapping between genus zero surfaces and spheres, and between general meshes and planes. Our method of computing conformal structures can be applied to tackle fundamental problems in computer aid design and computer graphics, such as geometry classification and identification, and surface global parametrization.