OpenRaiser/Intern-Atlas huggingface dataset:
Acceptability with general orderings
Venue: arXiv cs.PL 2001
Year: 2001

We present a new approach to termination analysis of logic programs. The essence of the approach is that we make use of general orderings (instead of level mappings), like it is done in transformational approaches to logic program termination analysis, but we apply these orderings directly to the logic program and not to the term-rewrite system obtained through some transformation. We define some variants of acceptability, based on general orderings, and show how they are equivalent to LD-termination. We develop a demand driven, constraint-based approach to verify these acceptability-variants. The advantage of the approach over standard acceptability is that in some cases, where complex level mappings are needed, fairly simple orderings may be easily generated. The advantage over transformational approaches is that it avoids the transformation step all together. {\bf Keywords:} termination analysis, acceptability, orderings.
Enabling the Long-Term Archival of Signed Documents through Time Stamping
Venue: arXiv cs.DC 2001
Year: 2001

In this paper we describe how to build a trusted reliable distributed service across administrative domains in a peer-to-peer network. The application we use to motivate our work is a public key time stamping service called Prokopius. The service provides a secure, verifiable but distributable stable archive that maintains time stamped snapshots of public keys over time. This in turn allows clients to verify time stamped documents or certificates that rely on formerly trusted public keys that are no longer in service or where the signer no longer exists. We find that such a service can time stamp the snapshots of public keys in a network of 148 nodes at the granularity of a couple of days, even in the worst case where an adversary causes the maximal amount of damage allowable within our fault model.
Enhancing Constraint Propagation with Composition Operators
Venue: arXiv cs.AI 2001
Year: 2001

Constraint propagation is a general algorithmic approach for pruning the search space of a CSP. In a uniform way, K. R. Apt has defined a computation as an iteration of reduction functions over a domain. He has also demonstrated the need for integrating static properties of reduction functions (commutativity and semi-commutativity) to design specialized algorithms such as AC3 and DAC. We introduce here a set of operators for modeling compositions of reduction functions. Two of the major goals are to tackle parallel computations, and dynamic behaviours (such as slow convergence).
On Concurrent and Resettable Zero-Knowledge Proofs for NP
Venue: arXiv cs.CR 2001
Year: 2001

A proof is concurrent zero-knowledge if it remains zero-knowledge when many copies of the proof are run in an asynchronous environment, such as the Internet. It is known that zero-knowledge is not necessarily preserved in such an environment. Designing concurrent zero-knowledge proofs is a fundamental issue in the study of zero-knowledge since known zero-knowledge protocols cannot be run in a realistic modern computing environment. In this paper we present a concurrent zero-knowledge proof systems for all languages in NP. Currently, the proof system we present is the only known proof system that retains the zero-knowledge property when copies of the proof are allowed to run in an asynchronous environment. Our proof system has $\tilde{O}(\log^2 k)$ rounds (for a security parameter $k$), which is almost optimal, as it is shown by Canetti Kilian Petrank and Rosen that black-box concurrent zero-knowledge requires $\tildeΩ(\log k)$ rounds. Canetti, Goldreich, Goldwasser and Micali introduced the notion of {\em resettable} zero-knowledge, and modified an earlier version of our proof system to obtain the first resettable zero-knowledge proof system. This protocol requires $k^{θ(1)}$ rounds. We note that their technique also applies to our current proof system, yielding a resettable zero-knowledge proof for NP with $\tilde{O}(\log^2 k)$ rounds.
Introduction to the CoNLL-2001 Shared Task: Clause Identification
Venue: arXiv cs.CL 2001
Year: 2001

We describe the CoNLL-2001 shared task: dividing text into clauses. We give background information on the data sets, present a general overview of the systems that have taken part in the shared task and briefly discuss their performance.
Learning Computational Grammars
Venue: arXiv cs.CL 2001
Year: 2001

This paper reports on the "Learning Computational Grammars" (LCG) project, a postdoc network devoted to studying the application of machine learning techniques to grammars suitable for computational use. We were interested in a more systematic survey to understand the relevance of many factors to the success of learning, esp. the availability of annotated data, the kind of dependencies in the data, and the availability of knowledge bases (grammars). We focused on syntax, esp. noun phrase (NP) syntax.
Applying Natural Language Generation to Indicative Summarization
Venue: arXiv cs.CL 2001
Year: 2001

The task of creating indicative summaries that help a searcher decide whether to read a particular document is a difficult task. This paper examines the indicative summarization task from a generation perspective, by first analyzing its required content via published guidelines and corpus analysis. We show how these summaries can be factored into a set of document features, and how an implemented content planner uses the topicality document feature to create indicative multidocument query-based summaries.
Multidimensional Transformation-Based Learning
Venue: arXiv cs.CL 2001
Year: 2001

This paper presents a novel method that allows a machine learning algorithm following the transformation-based learning paradigm \cite{brill95:tagging} to be applied to multiple classification tasks by training jointly and simultaneously on all fields. The motivation for constructing such a system stems from the observation that many tasks in natural language processing are naturally composed of multiple subtasks which need to be resolved simultaneously; also tasks usually learned in isolation can possibly benefit from being learned in a joint framework, as the signals for the extra tasks usually constitute inductive bias. The proposed algorithm is evaluated in two experiments: in one, the system is used to jointly predict the part-of-speech and text chunks/baseNP chunks of an English corpus; and in the second it is used to learn the joint prediction of word segment boundaries and part-of-speech tagging for Chinese. The results show that the simultaneous learning of multiple tasks does achieve an improvement in each task upon training the same tasks sequentially. The part-of-speech tagging result of 96.63% is state-of-the-art for individual systems on the particular train/test split.
Semantic Web Content Accessibility Guidelines for Current Research Information Systems (CRIS)
Venue: arXiv cs.NI 2001
Year: 2001

The most exciting challenge for CRIS is to create a service for research information which should be wide-spread, distributed and actual like Google, but at the same time structured, trusted, with a complex search and navigation similar to today CRIS application. The core technology for such a "new" CRIS is the semantic web technology to integrate database contents with HTML and XML web pages for being provided to the research interested public. One (at the moment the best) possible way is to use RDF (Resource Description Framework) which is also recommended by the W3 consortium.
Bounded Concurrent Timestamp Systems Using Vector Clocks
Venue: arXiv cs.DC 2001
Year: 2001

Shared registers are basic objects used as communication mediums in asynchronous concurrent computation. A concurrent timestamp system is a higher typed communication object, and has been shown to be a powerful tool to solve many concurrency control problems. It has turned out to be possible to construct such higher typed objects from primitive lower typed ones. The next step is to find efficient constructions. We propose a very efficient wait-free construction of bounded concurrent timestamp systems from 1-writer multireader registers. This finalizes, corrects, and extends, a preliminary bounded multiwriter construction proposed by the second author in 1986. That work partially initiated the current interest in wait-free concurrent objects, and introduced a notion of discrete vector clocks in distributed algorithms.
Spiders and Crawlers and Bots, Oh My: The Economic Efficiency and Public Policy of Contracts that Restrict Data Collection
Venue: arXiv cs.CY 2001
Year: 2001

Recent trends reveal the search by companies for a legal hook to prevent the undesired and unauthorized copying of information posted on websites. In the center of this controversy are metasites, websites that display prices for a variety of vendors. Metasites function by implementing shopbots, which extract pricing data from other vendors' websites. Technological mechanisms have proved unsuccessful in blocking shopbots, and in response, websites have asserted a variety of legal claims. Two recent cases, which rely on the troublesome trespass to chattels doctrine, suggest that contract law may provide a less demanding legal method of preventing the search of websites by data robots. If blocking collection of pricing data is as simple as posting an online contract, the question arises whether this end result is desirable and legally viable.
Verifying Sequential Consistency on Shared-Memory Multiprocessors by Model Checking
Venue: arXiv cs.DC 2001
Year: 2001

The memory model of a shared-memory multiprocessor is a contract between the designer and programmer of the multiprocessor. The sequential consistency memory model specifies a total order among the memory (read and write) events performed at each processor. A trace of a memory system satisfies sequential consistency if there exists a total order of all memory events in the trace that is both consistent with the total order at each processor and has the property that every read event to a location returns the value of the last write to that location. Descriptions of shared-memory systems are typically parameterized by the number of processors, the number of memory locations, and the number of data values. It has been shown that even for finite parameter values, verifying sequential consistency on general shared-memory systems is undecidable. We observe that, in practice, shared-memory systems satisfy the properties of causality and data independence. Causality is the property that values of read events flow from values of write events. Data independence is the property that all traces can be generated by renaming data values from traces where the written values are distinct from each other. If a causal and data independent system also has the property that the logical order of write events to each location is identical to their temporal order, then sequential consistency can be verified algorithmically. Specifically, we present a model checking algorithm to verify sequential consistency on such systems for a finite number of processors and memory locations and an arbitrary number of data values.
Security Considerations for Remote Electronic Voting over the Internet
Venue: arXiv cs.CR 2001
Year: 2001

This paper discusses the security considerations for remote electronic voting in public elections. In particular, we examine the feasibility of running national federal elections over the Internet. The focus of this paper is on the limitations of the current deployed infrastructure in terms of the security of the hosts and the Internet itself. We conclude that at present, our infrastructure is inadequate for remote Internet voting.
Is There a There There: Towards Greater Certainty for Internet Jurisdiction
Venue: arXiv cs.CY 2001
Year: 2001

The unique challenge presented by the Internet is that compliance with local laws is rarely sufficient to assure a business that it has limited its exposure to legal risk. The paper identifies why the challenge of adequately accounting for the legal risk arising from Internet jurisdiction has been aggravated in recent years by the adoption of the Zippo legal framework, commonly referred to as the passive versus active test. The test provides parties with only limited guidance and often results in detrimental judicial decisions from a policy perspective. Given the inadequacies of the Zippo passive versus active test, the paper argues that it is now fitting to identify a more effective standard for determining when it is appropriate to assert jurisdiction in cases involving predominantly Internet-based contacts. The solution submitted in the paper is to move toward a targeting-based analysis. Unlike the Zippo approach, a targeting analysis would seek to identify the intentions of the parties and to assess the steps taken to either enter or avoid a particular jurisdiction. Targeting would also lessen the reliance on effects-based analysis, the source of considerable uncertainty since Internet-based activity can ordinarily be said to create some effects in most jurisdictions. To identify the appropriate criteria for a targeting test, the paper recommends returning to the core jurisdictional principle -- foreseeability. Foreseeability in the targeting context depends on three factors -- contracts, technology, and actual or implied knowledge.
Boosting Trees for Anti-Spam Email Filtering
Venue: arXiv cs.CL 2001
Year: 2001

This paper describes a set of comparative experiments for the problem of automatically filtering unwanted electronic mail messages. Several variants of the AdaBoost algorithm with confidence-rated predictions [Schapire & Singer, 99] have been applied, which differ in the complexity of the base learners considered. Two main conclusions can be drawn from our experiments: a) The boosting-based methods clearly outperform the baseline learning algorithms (Naive Bayes and Induction of Decision Trees) on the PU1 corpus, achieving very high levels of the F1 measure; b) Increasing the complexity of the base learners allows to obtain better ``high-precision'' classifiers, which is a very important issue when misclassification costs are considered.
Learning from the Success of MPI
Venue: arXiv cs.DC 2001
Year: 2001

The Message Passing Interface (MPI) has been extremely successful as a portable way to program high-performance parallel computers. This success has occurred in spite of the view of many that message passing is difficult and that other approaches, including automatic parallelization and directive-based parallelism, are easier to use. This paper argues that MPI has succeeded because it addresses all of the important issues in providing a parallel programming model.
Interactive Timetabling
Venue: arXiv cs.PL 2001
Year: 2001

Timetabling is a typical application of constraint programming whose task is to allocate activities to slots in available resources respecting various constraints like precedence and capacity. In this paper we present a basic concept, a constraint model, and the solving algorithms for interactive timetabling. Interactive timetabling combines automated timetabling (the machine allocates the activities) with user interaction (the user can interfere with the process of timetabling). Because the user can see how the timetabling proceeds and can intervene this process, we believe that such approach is more convenient than full automated timetabling which behaves like a black-box. The contribution of this paper is twofold: we present a generic model to describe timetabling (and scheduling in general) problems and we propose an interactive algorithm for solving such problems.
Verification of Timed Automata Using Rewrite Rules and Strategies
Venue: arXiv cs.PL 2001
Year: 2001

ELAN is a powerful language and environment for specifying and prototyping deduction systems in a language based on rewrite rules controlled by strategies. Timed automata is a class of continuous real-time models of reactive systems for which efficient model-checking algorithms have been devised. In this paper, we show that these algorithms can very easily be prototyped in the ELAN system. This paper argues through this example that rewriting based systems relying on rules and strategies are a good framework to prototype, study and test rather efficiently symbolic model-checking algorithms, i.e. algorithms which involve combination of graph exploration rules, deduction rules, constraint solving techniques and decision procedures.
Dynamic Global Constraints: A First View
Venue: arXiv cs.PL 2001
Year: 2001

Global constraints proved themselves to be an efficient tool for modelling and solving large-scale real-life combinatorial problems. They encapsulate a set of binary constraints and using global reasoning about this set they filter the domains of involved variables better than arc consistency among the set of binary constraints. Moreover, global constraints exploit semantic information to achieve more efficient filtering than generalised consistency algorithms for n-ary constraints. Continued expansion of constraint programming (CP) to various application areas brings new challenges for design of global constraints. In particular, application of CP to advanced planning and scheduling (APS) requires dynamic additions of new variables and constraints during the process of constraint satisfaction and, thus, it would be helpful if the global constraints could adopt new variables. In the paper, we give a motivation for such dynamic global constraints and we describe a dynamic version of the well-known alldifferent constraint.
Random Walks in Routing Landscapes
Venue: arXiv cs.NI 2001
Year: 2001

In this paper we present a combinatorial optimisation view on the routing problem for connectionless packet networks by using the metaphor of a landscape. We examine the main properties of the routing landscapes as we define them and how they can help us on the evaluation of the problem difficulty and the generation of effective algorithms. We also present the random walk statistical technique to evaluate the main properties of those landscapes and a number of examples to demonstrate the use of the method.
CLP versus LS on Log-based Reconciliation Problems
Venue: arXiv cs.PL 2001
Year: 2001

Nomadic applications create replicas of shared objects that evolve independently while they are disconnected. When reconnecting, the system has to reconcile the divergent replicas. In the log-based approach to reconciliation, such as in the IceCube system, the input is a common initial state and logs of actions that were performed on each replica. The output is a consistent global schedule that maximises the number of accepted actions. The reconciler merges the logs according to the schedule, and replays the operations in the merged log against the initial state, yielding to a reconciled common final state. In this paper, we show the NP-completeness of the log-based reconciliation problem and present two programs for solving it. Firstly, a constraint logic program (CLP) that uses integer constraints for expressing precedence constraints, boolean constraints for expressing dependencies between actions, and some heuristics for guiding the search. Secondly, a stochastic local search method with Tabu heuristic (LS), that computes solutions in an incremental fashion but does not prove optimality. One difficulty in the LS modeling lies in the handling of both boolean variables and integer variables, and in the handling of the objective function which differs from a max-CSP problem. Preliminary evaluation results indicate better performance for the CLP program which, on somewhat realistic benchmarks, finds nearly optimal solutions up to a thousands of actions and proves optimality up to a hundreds of actions.
Internet Radio: A New Engine for Content Diversity?
Venue: arXiv cs.CY 2001
Year: 2001

While traditional radio stations are subject to extensive government regulations, Internet radio stations remain largely unregulated. As Internet radio usage has increased certain stakeholders have begun to argue that these Internet radio broadcasters are providing significant and diverse programming to American audiences and that government regulation of spectrum-using radio station ownership may be further relaxed. One of the primary justifications for regulation of ownership has been to protect diversity in broadcasting. This study hypothesizes that Internet radio broadcasting does add diversity to the radio broadcasting industry and that it should be considered as relevant by regulators. This study evaluates the role of Internet radio broadcasters according to five criteria intended to gauge the level of diversity being delivered to listeners online. By measuring the levels of format, channel, ownership, location and language diversity among Internet radio stations, it is possible to draw benchmark lessons about the new medium's ability to provide Americans with diverse broadcasting options. The study finds that Internet radio broadcasters are in fact adding measurable diversity to the radio broadcasting industry. Internet broadcasters are providing audiences with access to an increasing number of stations, owners, formats, and language choices, and it is likely that technologies aiding in the mobility of access as well as broadband evolution will reinforce these findings.
Monopoly Power on the Web - A Preliminary Investigation of Search Engines
Venue: arXiv cs.CY 2001
Year: 2001

E-Commerce challenges traditional approaches to assessing monopolistic practices due to the rapid rate of growth, rapid change in technology, difficulty in assessing market share for information products like web sites, and high degree of interconnectivity and alliance formation among corporations. This paper has provided a fundamental framework that integrates a network and economic perspective to the search engine market. The findings indicate that (1) despite an increasing number of search engines, barriers to entry seem high, largely due to the exponential growth in the number of web sites and the non-scalability of the current search technology and collective switching costs; (2) older search engine sites tend typically to have more features to lock in users. Using standard economic indicators (CR4=58% and HHI=1163), the industry looks close to being plagued by anticompetitive practices. But based on a network adjusted HHI constructed in this paper, its value, 870, suggests that there is less cause for concern. Based on all indicators, it suggests that Yahoo would be a contender. Other possible contenders are MSN and Netscape. On the basis of results to date, some search engines keep increasing their audience reach while others don't. The trend shows that some search engines may dominate the search engine market. We suggest conducting research in the coverage performance of search engines and investigate "information search cost" as a performance indicator of search techniques. In addition, we suggest paying attention to any anticompetitive conduct (e.g. product bundling) that may lesson competition and reduce consumer welfare. The combination of network theory and economic theory to study the search engine market is a particularly powerful approach for E-Commerce.
Branching: the Essence of Constraint Solving
Venue: arXiv cs.PL 2001
Year: 2001

This paper focuses on the branching process for solving any constraint satisfaction problem (CSP). A parametrised schema is proposed that (with suitable instantiations of the parameters) can solve CSP's on both finite and infinite domains. The paper presents a formal specification of the schema and a statement of a number of interesting properties that, subject to certain conditions, are satisfied by any instances of the schema. It is also shown that the operational procedures of many constraint systems including cooperative systems) satisfy these conditions. Moreover, the schema is also used to solve the same CSP in different ways by means of different instantiations of its parameters.