OpenRaiser/Intern-Atlas huggingface dataset:
An effective Procedure for Speeding up Algorithms
Venue: arXiv cs.CC 2001
Year: 2001

The provably asymptotically fastest algorithm within a factor of 5 for formally described problems will be constructed. The main idea is to enumerate all programs provably equivalent to the original problem by enumerating all proofs. The algorithm could be interpreted as a generalization and improvement of Levin search, which is, within a multiplicative constant, the fastest algorithm for inverting functions. Blum's speed-up theorem is avoided by taking into account only programs for which a correctness proof exists. Furthermore, it is shown that the fastest program that computes a certain function is also one of the shortest programs provably computing this function. To quantify this statement, the definition of Kolmogorov complexity is extended, and two new natural measures for the complexity of a function are defined.
Multi-Syllable Phonotactic Modelling
Venue: arXiv cs.CL 2001
Year: 2001

This paper describes a novel approach to constructing phonotactic models. The underlying theoretical approach to phonological description is the multisyllable approach in which multiple syllable classes are defined that reflect phonotactically idiosyncratic syllable subcategories. A new finite-state formalism, OFS Modelling, is used as a tool for encoding, automatically constructing and generalising phonotactic descriptions. Language-independent prototype models are constructed which are instantiated on the basis of data sets of phonological strings, and generalised with a clustering algorithm. The resulting approach enables the automatic construction of phonotactic models that encode arbitrarily close approximations of a language's set of attested phonological forms. The approach is applied to the construction of multi-syllable word-level phonotactic models for German, English and Dutch.
A Machine-Learning Approach to Estimating the Referential Properties of Japanese Noun Phrases
Venue: arXiv cs.CL 2001
Year: 2001

The referential properties of noun phrases in the Japanese language, which has no articles, are useful for article generation in Japanese-English machine translation and for anaphora resolution in Japanese noun phrases. They are generally classified as generic noun phrases, definite noun phrases, and indefinite noun phrases. In the previous work, referential properties were estimated by developing rules that used clue words. If two or more rules were in conflict with each other, the category having the maximum total score given by the rules was selected as the desired category. The score given by each rule was established by hand, so the manpower cost was high. In this work, we automatically adjusted these scores by using a machine-learning method and succeeded in reducing the amount of manpower needed to adjust these scores.
Search in Power-Law Networks
Venue: arXiv cs.NI 2001
Year: 2001

Many communication and social networks have power-law link distributions, containing a few nodes which have a very high degree and many with low degree. The high connectivity nodes play the important role of hubs in communication and networking, a fact which can be exploited when designing efficient search algorithms. We introduce a number of local search strategies which utilize high degree nodes in power-law graphs and which have costs which scale sub-linearly with the size of the graph. We also demonstrate the utility of these strategies on the Gnutella peer-to-peer network.
Nice point sets can have nasty Delaunay triangulations
Venue: arXiv cs.CG 2001
Year: 2001

We consider the complexity of Delaunay triangulations of sets of points in R^3 under certain practical geometric constraints. The spread of a set of points is the ratio between the longest and shortest pairwise distances. We show that in the worst case, the Delaunay triangulation of n points in R^3 with spread D has complexity Omega(min{D^3, nD, n^2}) and O(min{D^4, n^2}). For the case D = Theta(sqrt{n}), our lower bound construction consists of a uniform sample of a smooth convex surface with bounded curvature. We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity.
The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete
Venue: arXiv cs.DS 2001
Year: 2001

It is known that the existential theory of equations in free groups is decidable. This is a famous result of Makanin. On the other hand it has been shown that the scheme of his algorithm is not primitive recursive. In this paper we present an algorithm that works in polynomial space, even in the more general setting where each variable has a rational constraint, that is, the solution has to respect a specification given by a regular word language. Our main result states that the existential theory of equations in free groups with rational constraints is PSPACE-complete. We obtain this result as a corollary of the corresponding statement about free monoids with involution.
Quantum Clock Synchronization with one qubit
Venue: arXiv cs.CC 2001
Year: 2001

The clock synchronization problem is to determine the time difference T between two spatially separated parties. We improve on I. Chuang's quantum clock synchronization algorithm and show that it is possible to obtain T to n bits of accuracy while communicating only one qubit in one direction and using an O(2^n) frequency range. We also prove a quantum lower bound of Ω(2^n) for the product of the transmitted qubits and the range of frequencies, thus showing that our algorithm is optimal.
The Anatomy of the Grid - Enabling Scalable Virtual Organizations
Venue: arXiv cs.AR 2001
Year: 2001

"Grid" computing has emerged as an important new field, distinguished from conventional distributed computing by its focus on large-scale resource sharing, innovative applications, and, in some cases, high-performance orientation. In this article, we define this new field. First, we review the "Grid problem," which we define as flexible, secure, coordinated resource sharing among dynamic collections of individuals, institutions, and resources-what we refer to as virtual organizations. In such settings, we encounter unique authentication, authorization, resource access, resource discovery, and other challenges. It is this class of problem that is addressed by Grid technologies. Next, we present an extensible and open Grid architecture, in which protocols, services, application programming interfaces, and software development kits are categorized according to their roles in enabling resource sharing. We describe requirements that we believe any such mechanisms must satisfy, and we discuss the central role played by the intergrid protocols that enable interoperability among different Grid systems. Finally, we discuss how Grid technologies relate to other contemporary technologies, including enterprise integration, application service provider, storage service provider, and peer-to-peer computing. We maintain that Grid concepts and technologies complement and have much to contribute to these other approaches.
Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure
Venue: arXiv cs.DS 2001
Year: 2001

In this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular, we devise a deterministic algorithm for general directed graphs that achieves $O(n^2)$ amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. Our matrix-based approach yields an algorithm for directed acyclic graphs that breaks through the $O(n^2)$ barrier on the single-operation complexity of fully dynamic transitive closure. We can answer queries in $O(n^ε)$ time and perform updates in $O(n^{ω(1,ε,1)-ε}+n^{1+ε})$ time, for any $ε\in[0,1]$, where $ω(1,ε,1)$ is the exponent of the multiplication of an $n\times n^ε$ matrix by an $n^ε\times n$ matrix. The current best bounds on $ω(1,ε,1)$ imply an $O(n^{0.58})$ query time and an $O(n^{1.58})$ update time. Our subquadratic algorithm is randomized, and has one-side error.
ABL: Alignment-Based Learning
Venue: arXiv cs.LG 2001
Year: 2001

This paper introduces a new type of grammar learning algorithm, inspired by string edit distance (Wagner and Fischer, 1974). The algorithm takes a corpus of flat sentences as input and returns a corpus of labelled, bracketed sentences. The method works on pairs of unstructured sentences that have one or more words in common. When two sentences are divided into parts that are the same in both sentences and parts that are different, this information is used to find parts that are interchangeable. These parts are taken as possible constituents of the same type. After this alignment learning step, the selection learning step selects the most probable constituents from all possible constituents. This method was used to bootstrap structure on the ATIS corpus (Marcus et al., 1993) and on the OVIS (Openbaar Vervoer Informatie Systeem (OVIS) stands for Public Transport Information System.) corpus (Bonnema et al., 1997). While the results are encouraging (we obtained up to 89.25 % non-crossing brackets precision), this paper will point out some of the shortcomings of our approach and will suggest possible solutions.
HTTP Cookies: Standards, Privacy, and Politics
Venue: arXiv cs.SE 2001
Year: 2001

How did we get from a world where cookies were something you ate and where "non-techies" were unaware of "Netscape cookies" to a world where cookies are a hot-button privacy issue for many computer users? This paper will describe how HTTP "cookies" work, and how Netscape's original specification evolved into an IETF Proposed Standard. I will also offer a personal perspective on how what began as a straightforward technical specification turned into a political flashpoint when it tried to address non-technical issues such as privacy.
Robust Probabilistic Predictive Syntactic Processing
Venue: arXiv cs.CL 2001
Year: 2001

This thesis presents a broad-coverage probabilistic top-down parser, and its application to the problem of language modeling for speech recognition. The parser builds fully connected derivations incrementally, in a single pass from left-to-right across the string. We argue that the parsing approach that we have adopted is well-motivated from a psycholinguistic perspective, as a model that captures probabilistic dependencies between lexical items, as part of the process of building connected syntactic structures. The basic parser and conditional probability models are presented, and empirical results are provided for its parsing accuracy on both newspaper text and spontaneous telephone conversations. Modifications to the probability model are presented that lead to improved performance. A new language model which uses the output of the parser is then defined. Perplexity and word error rate reduction are demonstrated over trigram models, even when the trigram is trained on significantly more data. Interpolation on a word-by-word basis with a trigram model yields additional improvements.
Toward Natural Gesture/Speech Control of a Large Display
Venue: arXiv cs.CV 2001
Year: 2001

In recent years because of the advances in computer vision research, free hand gestures have been explored as means of human-computer interaction (HCI). Together with improved speech processing technology it is an important step toward natural multimodal HCI. However, inclusion of non-predefined continuous gestures into a multimodal framework is a challenging problem. In this paper, we propose a structured approach for studying patterns of multimodal language in the context of a 2D-display control. We consider systematic analysis of gestures from observable kinematical primitives to their semantics as pertinent to a linguistic structure. Proposed semantic classification of co-verbal gestures distinguishes six categories based on their spatio-temporal deixis. We discuss evolution of a computational framework for gesture and speech integration which was used to develop an interactive testbed (iMAP). The testbed enabled elicitation of adequate, non-sequential, multimodal patterns in a narrative mode of HCI. Conducted user studies illustrate significance of accounting for the temporal alignment of gesture and speech parts in semantic mapping. Furthermore, co-occurrence analysis of gesture/speech production suggests syntactic organization of gestures at the lexical level.
State Analysis and Aggregation Study for Multicast-based Micro Mobility
Venue: arXiv cs.NI 2001
Year: 2001

IP mobility addresses the problem of changing the network point-of-attachment transparently during movement. Mobile IP is the proposed standard by IETF. Several studies, however, have shown that Mobile IP has several drawbacks, such as triangle routing and poor handoff performance. Multicast-based mobility has been proposed as a promising solution to the above problems, incurring less end-to-end delays and fast smooth handoff. Nonetheless, such architecture suffers from multicast state scalability problems with the growth in number of mobile nodes. This architecture also requires ubiquitous multicast deployment and more complex security measures. To alleviate these problems, we propose an intra-domain multicast-based mobility solution. A mobility proxy allocates a multicast address for each mobile that moves to its domain. The mobile uses this multicast address within a domain for micro mobility. Also, aggregation is considered to reduce the multicast state. We conduct multicast state analysis to study the efficiency of several aggregation techniques. We use extensive simulation to evaluate our protocol's performance over a variety of real and generated topologies. We take aggregation gain as metric for our evaluation. Our simulation results show that in general leaky aggregation obtains better gains than perfect aggregation. Also, we notice that aggregation gain increases with the increase in number of visiting mobile nodes and with the decrease in number of mobility proxies within a domain.
Learning to Cooperate via Policy Search
Venue: arXiv cs.LG 2001
Year: 2001

Cooperative games are those in which both agents share the same payoff structure. Value-based reinforcement-learning algorithms, such as variants of Q-learning, have been applied to learning cooperative games, but they only apply when the game state is completely observable to both agents. Policy search methods are a reasonable alternative to value-based methods for partially observable environments. In this paper, we provide a gradient-based distributed policy-search method for cooperative games and compare the notion of local optimum to that of Nash equilibrium. We demonstrate the effectiveness of this method experimentally in a small, partially observable simulated soccer domain.
Integrating Prosodic and Lexical Cues for Automatic Topic Segmentation
Venue: arXiv cs.CL 2001
Year: 2001

We present a probabilistic model that uses both prosodic and lexical cues for the automatic segmentation of speech into topically coherent units. We propose two methods for combining lexical and prosodic information using hidden Markov models and decision trees. Lexical information is obtained from a speech recognizer, and prosodic features are extracted automatically from speech waveforms. We evaluate our approach on the Broadcast News corpus, using the DARPA-TDT evaluation metrics. Results show that the prosodic model alone is competitive with word-based segmentation methods. Furthermore, we achieve a significant reduction in error by combining the prosodic and word-based knowledge sources.
Approximating the satisfiability threshold for random k-XOR-formulas
Venue: arXiv cs.DM 2001
Year: 2001

In this paper we study random linear systems with $k$ variables per equation over the finite field GF(2), or equivalently $k$-XOR-CNF formulas. In a previous paper Creignou and Daudé proved that the phase transition for the consistency (satisfiability) of such systems (formulas) exhibits a sharp threshold. Here we prove that the phase transition occurs as the number of equations (clauses) is proportional to the number of variables. For any $k\ge 3$ we establish first estimates for the critical ratio. For $k=3$ we get 0.93 as an upper bound, 0.89 as a lower bound, whereas experiments suggest that the critical ratio is approximately 0.92.
Modelling Contractual Arguments
Venue: arXiv cs.AI 2001
Year: 2001

One influential approach to assessing the "goodness" of arguments is offered by the Pragma-Dialectical school (p-d) (Eemeren & Grootendorst 1992). This can be compared with Rhetorical Structure Theory (RST) (Mann & Thompson 1988), an approach that originates in discourse analysis. In p-d terms an argument is good if it avoids committing a fallacy, whereas in RST terms an argument is good if it is coherent. RST has been criticised (Snoeck Henkemans 1997) for providing only a partially functional account of argument, and similar criticisms have been raised in the Natural Language Generation (NLG) community-particularly by Moore & Pollack (1992)- with regards to its account of intentionality in text in general. Mann and Thompson themselves note that although RST can be successfully applied to a wide range of texts from diverse domains, it fails to characterise some types of text, most notably legal contracts. There is ongoing research in the Artificial Intelligence and Law community exploring the potential for providing electronic support to contract negotiators, focusing on long-term, complex engineering agreements (see for example Daskalopulu & Sergot 1997). This paper provides a brief introduction to RST and illustrates its shortcomings with respect to contractual text. An alternative approach for modelling argument structure is presented which not only caters for contractual text, but also overcomes the aforementioned limitations of RST.
Computational Properties of Metaquerying Problems
Venue: arXiv cs.DB 2001
Year: 2001

Metaquerying is a datamining technology by which hidden dependencies among several database relations can be discovered. This tool has already been successfully applied to several real-world applications. Recent papers provide only preliminary results about the complexity of metaquerying. In this paper we define several variants of metaquerying that encompass, as far as we know, all variants defined in the literature. We study both the combined complexity and the data complexity of these variants. We show that, under the combined complexity measure, metaquerying is generally intractable (unless P=NP), lying sometimes quite high in the complexity hierarchies (as high as NP^PP), depending on the characteristics of the plausibility index. However, we are able to single out some tractable and interesting metaquerying cases (whose combined complexity is LOGCFL-complete). As for the data complexity of metaquerying, we prove that, in general, this is in TC0, but lies within AC0 in some simpler cases. Finally, we discuss implementation of metaqueries, by providing algorithms to answer them.
File mapping Rule-based DBMS and Natural Language Processing
Venue: arXiv cs.CL 2001
Year: 2001

This paper describes the system of storage, extract and processing of information structured similarly to the natural language. For recursive inference the system uses the rules having the same representation, as the data. The environment of storage of information is provided with the File Mapping (SHM) mechanism of operating system. In the paper the main principles of construction of dynamic data structure and language for record of the inference rules are stated; the features of available implementation are considered and the description of the application realizing semantic information retrieval on the natural language is given.
Pricing Virtual Paths with Quality-of-Service Guarantees as Bundle Derivatives
Venue: arXiv cs.NI 2001
Year: 2001

We describe a model of a communication network that allows us to price complex network services as financial derivative contracts based on the spot price of the capacity in individual routers. We prove a theorem of a Girsanov transform that is useful for pricing linear derivatives on underlying assets, which can be used to price many complex network services, and it is used to price an option that gives access to one of several virtual channels between two network nodes, during a specified future time interval. We give the continuous time hedging strategy, for which the option price is independent of the service providers attitude towards risk. The option price contains the density function of a sum of lognormal variables, which has to be evaluated numerically.
Building Views with Description Logics in ADE: Application Development Environment
Venue: arXiv cs.LO 2001
Year: 2001

Any of views is formally defined within description logics that were established as a family of logics for modeling complex hereditary structures and have a suitable expressive power. This paper considers the Application Development Environment (ADE) over generalized variable concepts that are used to build database applications involving the supporting views. The front-end user interacts the database via separate ADE access mechanism intermediated by view support. The variety of applications may be generated that communicate with different and distinct desktop databases in a data warehouse. The advanced techniques allows to involve remote or stored procedures retrieval and call.
Complexity Results and Practical Algorithms for Logics in Knowledge Representation
Venue: arXiv cs.LO 2001
Year: 2001

Description Logics (DLs) are used in knowledge-based systems to represent and reason about terminological knowledge of the application domain in a semantically well-defined manner. In this thesis, we establish a number of novel complexity results and give practical algorithms for expressive DLs that provide different forms of counting quantifiers. We show that, in many cases, adding local counting in the form of qualifying number restrictions to DLs does not increase the complexity of the inference problems, even if binary coding of numbers in the input is assumed. On the other hand, we show that adding different forms of global counting restrictions to a logic may increase the complexity of the inference problems dramatically. We provide exact complexity results and a practical, tableau based algorithm for the DL SHIQ, which forms the basis of the highly optimized DL system iFaCT. Finally, we describe a tableau algorithm for the clique guarded fragment (CGF), which we hope will serve as the basis for an efficient implementation of a CGF reasoner.
Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences
Venue: arXiv cs.LG 2001
Year: 2001

Solomonoff's uncomputable universal prediction scheme $ξ$ allows to predict the next symbol $x_k$ of a sequence $x_1...x_{k-1}$ for any Turing computable, but otherwise unknown, probabilistic environment $μ$. This scheme will be generalized to arbitrary environmental classes, which, among others, allows the construction of computable universal prediction schemes $ξ$. Convergence of $ξ$ to $μ$ in a conditional mean squared sense and with $μ$ probability 1 is proven. It is shown that the average number of prediction errors made by the universal $ξ$ scheme rapidly converges to those made by the best possible informed $μ$ scheme. The schemes, theorems and proofs are given for general finite alphabet, which results in additional complications as compared to the binary case. Several extensions of the presented theory and results are outlined. They include general loss functions and bounds, games of chance, infinite alphabet, partial and delayed prediction, classification, and more active systems.