OpenRaiser/Intern-Atlas huggingface dataset:
Perpetual Adaptation of Software to Hardware: An Extensible Architecture for Providing Code Optimization as a Central System Service
Venue: arXiv cs.OS 1999
Year: 1999

We present an open architecture for just-in-time code generation and dynamic code optimization that is flexible, customizable, and extensible. While previous research has primarily investigated functional aspects of such a system, architectural aspects have so far remained unexplored. In this paper, we argue that these properties are important to generate optimal code for a variety of hardware architectures and different processor generations within processor families. These properties are also important to make system-level code generation useful in practice.
Mixing Metaphors
Venue: arXiv cs.CL 1999
Year: 1999

Mixed metaphors have been neglected in recent metaphor research. This paper suggests that such neglect is short-sighted. Though mixing is a more complex phenomenon than straight metaphors, the same kinds of reasoning and knowledge structures are required. This paper provides an analysis of both parallel and serial mixed metaphors within the framework of an AI system which is already capable of reasoning about straight metaphorical manifestations and argues that the processes underlying mixing are central to metaphorical meaning. Therefore, any theory of metaphors must be able to account for mixing.
WebScript -- A Scripting Language for the Web
Venue: arXiv cs.NI 1999
Year: 1999

WebScript is a scripting language for processing Web documents. Designed as an extension to Jacl, the Java implementation of Tcl, WebScript allows programmers to manipulate HTML in the same way as Tcl manipulates text strings and GUI elements. This leads to a completely new way of writing the next generation of Web applications. This paper presents the motivation behind the design and implementation of WebScript, an overview of its major features, as well as some demonstrations of its power.
Active Virtual Network Management Protocol
Venue: arXiv cs.NI 1999
Year: 1999

This paper introduces a novel algorithm, the Active Virtual Network Management Protocol (AVNMP), for predictive network management. It explains how the AVNMP facilitates the management of an active network by allowing future predicted state information within an active network to be available to network management algorithms. This is accomplished by coupling ideas from optimistic discrete event simulation with active networking. The optimistic discrete event simulation method used is a form of self-adjusting Time Warp. It is self-adjusting because the system adjusts for predictions which are inaccurate beyond a given tolerance. The concept of a streptichron and autoanaplasis are introduced as mechanisms which take advantage of the enhanced flexibility and intelligence of active packets. Finally, it is demonstrated that the AVNMP is a feasible concept.
Network Management of Predictive Mobile Networks
Venue: arXiv cs.NI 1999
Year: 1999

There is a trend toward the use of predictive systems in communications networks. At the systems and network management level predictive capabilities are focused on anticipating network faults and performance degradation. Simultaneously, mobile communication networks are being developed with predictive location and tracking mechanisms. The interactions and synergies between these systems present a new set of problems. A new predictive network management framework is developed and examined. The interaction between a predictive mobile network and the proposed network management system is discussed. The Rapidly Deployable Radio Network is used as a specific example to illustrate these interactions.
Mobile ATM Buffer Capacity Analysis
Venue: arXiv cs.NI 1999
Year: 1999

This paper extends a stochastic theory for buffer fill distribution for multiple ``on'' and ``off'' sources to a mobile environment. Queue fill distribution is described by a set of differential equations assuming sources alternate asynchronously between exponentially distributed periods in ``on'' and ``off'' states. This paper includes the probabilities that mobile sources have links to a given queue. The sources represent mobile user nodes, and the queue represents the capacity of a switch. This paper presents a method of analysis which uses mobile parameters such as speed, call rates per unit area, cell area, and call duration and determines queue fill distribution at the ATM cell level. The analytic results are compared with simulation results.
A Computational Memory and Processing Model for Processing for Prosody
Venue: arXiv cs.CL 1999
Year: 1999

This paper links prosody to the information in a text and how it is processed by the speaker. It describes the operation and output of LOQ, a text-to-speech implementation that includes a model of limited attention and working memory. Attentional limitations are key. Varying the attentional parameter in the simulations varies in turn what counts as given and new in a text, and therefore, the intonational contours with which it is uttered. Currently, the system produces prosody in three different styles: child-like, adult expressive, and knowledgeable. This prosody also exhibits differences within each style -- no two simulations are alike. The limited resource approach captures some of the stylistic and individual variety found in natural prosody.
Hadamard product nonlinear formulation of Galerkin and finite element methods
Venue: arXiv cs.CE 1999
Year: 1999

A novel nonlinear formulation of the finite element and Galerkin methods is presented here, which leads to the Hadamard product expression of the resultant nonlinear algebraic analogue. The presented formulation attains the advantages of weak formulation in the standard finite element and Galerkin schemes and avoids the costly repeated numerical integration of the Jacobian matrix via the recently developed SJT product approach. This also provides possibility of the nonlinear decoupling computations.
Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition
Venue: arXiv cs.LG 1999
Year: 1999

This paper presents the MAXQ approach to hierarchical reinforcement learning based on decomposing the target Markov decision process (MDP) into a hierarchy of smaller MDPs and decomposing the value function of the target MDP into an additive combination of the value functions of the smaller MDPs. The paper defines the MAXQ hierarchy, proves formal results on its representational power, and establishes five conditions for the safe use of state abstractions. The paper presents an online model-free learning algorithm, MAXQ-Q, and proves that it converges wih probability 1 to a kind of locally-optimal policy known as a recursively optimal policy, even in the presence of the five kinds of state abstraction. The paper evaluates the MAXQ representation and MAXQ-Q through a series of experiments in three domains and shows experimentally that MAXQ-Q (with state abstractions) converges to a recursively optimal policy much faster than flat Q learning. The fact that MAXQ learns a representation of the value function has an important benefit: it makes it possible to compute and execute an improved, non-hierarchical policy via a procedure similar to the policy improvement step of policy iteration. The paper demonstrates the effectiveness of this non-hierarchical execution experimentally. Finally, the paper concludes with a comparison to related work and a discussion of the design tradeoffs in hierarchical reinforcement learning.
MSO definable string transductions and two-way finite state transducers
Venue: arXiv cs.LO 1999
Year: 1999

String transductions that are definable in monadic second-order (mso) logic (without the use of parameters) are exactly those realized by deterministic two-way finite state transducers. Nondeterministic mso definable string transductions (i.e., those definable with the use of parameters) correspond to compositions of two nondeterministic two-way finite state transducers that have the finite visit property. Both families of mso definable string transductions are characterized in terms of Hennie machines, i.e., two-way finite state transducers with the finite visit property that are allowed to rewrite their input tape.
Cascaded Markov Models
Venue: arXiv cs.CL 1999
Year: 1999

This paper presents a new approach to partial parsing of context-free structures. The approach is based on Markov Models. Each layer of the resulting structure is represented by its own Markov Model, and output of a lower layer is passed as input to the next higher layer. An empirical evaluation of the method yields very good results for NP/PP chunking of German newspaper texts.
The application of special matrix product to differential quadrature solution of geometrically nonlinear bending of orthotropic rectangular plates
Venue: arXiv cs.CE 1999
Year: 1999

The Hadamard and SJT product of matrices are two types of special matrix product. The latter was first defined by Chen. In this study, they are applied to the differential quadrature (DQ) solution of geometrically nonlinear bending of isotropic and orthotropic rectangular plates. By using the Hadamard product, the nonlinear formulations are greatly simplified, while the SJT product approach minimizes the effort to evaluate the Jacobian derivative matrix in the Newton-Raphson method for solving the resultant nonlinear formulations. In addition, the coupled nonlinear formulations for the present problems can easily be decoupled by means of the Hadamard and SJT product. Therefore, the size of the simultaneous nonlinear algebraic equations is reduced by two-thirds and the computing effort and storage requirements are alleviated greatly. Two recent approaches applying the multiple boundary conditions are employed in the present DQ nonlinear computations. The solution accuracies are improved obviously in comparison to the previously given by Bert et al. The numerical results and detailed solution procedures are provided to demonstrate the superb efficiency, accuracy and simplicity of the new approaches in applying DQ method for nonlinear computations.
A Unified Example-Based and Lexicalist Approach to Machine Translation
Venue: arXiv cs.CL 1999
Year: 1999

We present an approach to Machine Translation that combines the ideas and methodologies of the Example-Based and Lexicalist theoretical frameworks. The approach has been implemented in a multilingual Machine Translation system.
Setting Parameters by Example
Venue: arXiv cs.DS 1999
Year: 1999

We introduce a class of "inverse parametric optimization" problems, in which one is given both a parametric optimization problem and a desired optimal solution; the task is to determine parameter values that lead to the given solution. We describe algorithms for solving such problems for minimum spanning trees, shortest paths, and other "optimal subgraph" problems, and discuss applications in multicast routing, vehicle path planning, resource allocation, and board game programming.
The Distribution of Cycle Lengths in Graphical Models for Iterative Decoding
Venue: arXiv cs.DM 1999
Year: 1999

This paper analyzes the distribution of cycle lengths in turbo decoding and low-density parity check (LDPC) graphs. The properties of such cycles are of significant interest in the context of iterative decoding algorithms which are based on belief propagation or message passing. We estimate the probability that there exist no simple cycles of length less than or equal to k at a randomly chosen node in a turbo decoding graph using a combination of counting arguments and independence assumptions. For large block lengths n, this probability is approximately e^{-{2^{k-1}-4}/n}, k>=4. Simulation results validate the accuracy of the various approximations. For example, for turbo codes with a block length of 64000, a randomly chosen node has a less than 1% chance of being on a cycle of length less than or equal to 10, but has a greater than 99.9% chance of being on a cycle of length less than or equal to 20. The effect of the "S-random" permutation is also analyzed and it is shown that while it eliminates short cycles of length k<8, it does not significantly affect the overall distribution of cycle lengths. Similar analyses and simulations are also presented for graphs for LDPC codes. The paper concludes by commenting briefly on how these results may provide insight into the practical success of iterative decoding methods.
A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem
Venue: arXiv cs.CC 1999
Year: 1999

Rice's Theorem states that every nontrivial language property of the recursively enumerable sets is undecidable. Borchert and Stephan initiated the search for complexity-theoretic analogs of Rice's Theorem. In particular, they proved that every nontrivial counting property of circuits is UP-hard, and that a number of closely related problems are SPP-hard. The present paper studies whether their UP-hardness result itself can be improved to SPP-hardness. We show that their UP-hardness result cannot be strengthened to SPP-hardness unless unlikely complexity class containments hold. Nonetheless, we prove that every P-constructibly bi-infinite counting property of circuits is SPP-hard. We also raise their general lower bound from unambiguous nondeterminism to constant-ambiguity nondeterminism.
Raising NP Lower Bounds to Parallel NP Lower Bounds
Venue: arXiv cs.CC 1999
Year: 1999

A decade ago, a beautiful paper by Wagner developed a ``toolkit'' that in certain cases allows one to prove problems hard for parallel access to NP. However, the problems his toolkit applies to most directly are not overly natural. During the past year, problems that previously were known only to be NP-hard or coNP-hard have been shown to be hard even for the class of sets solvable via parallel access to NP. Many of these problems are longstanding and extremely natural, such as the Minimum Equivalent Expression problem (which was the original motivation for creating the polynomial hierarchy), the problem of determining the winner in the election system introduced by Lewis Carroll in 1876, and the problem of determining on which inputs heuristic algorithms perform well. In the present article, we survey this recent progress in raising lower bounds.
Construction of regular languages and recognizability of polynomials
Venue: arXiv cs.CC 1999
Year: 1999

A generalization of numeration system in which the set N of the natural numbers is recognizable by finite automata can be obtained by describing a lexicographically ordered infinite regular language. Here we show that if P belonging to Q[x] is a polynomial such that P(N) is a subset of N then we can construct a numeration system in which the set of representations of P(N) is regular. The main issue in this construction is to setup a regular language with a density function equals to P(n+1)-P(n) for n large enough.
Emerging Challenges in Computational Topology
Venue: arXiv cs.CG 1999
Year: 1999

Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both computation and topology.
Semantic robust parsing for noun extraction from natural language queries
Venue: arXiv cs.CL 1999
Year: 1999

This paper describes how robust parsing techniques can be fruitful applied for building a query generation module which is part of a pipelined NLP architecture aimed at process natural language queries in a restricted domain. We want to show that semantic robustness represents a key issue in those NLP systems where it is more likely to have partial and ill-formed utterances due to various factors (e.g. noisy environments, low quality of speech recognition modules, etc...) and where it is necessary to succeed, even if partially, in extracting some meaningful information.
Circular Separability of Polygons
Venue: arXiv cs.CG 1999
Year: 1999

Two planar sets are circularly separable if there exists a circle enclosing one of the sets and whose open interior disk does not intersect the other set. This paper studies two problems related to circular separability. A linear-time algorithm is proposed to decide if two polygons are circularly separable. The algorithm outputs the smallest separating circle. The second problem asks for the largest circle included in a preprocessed, convex polygon, under some point and/or line constraints. The resulting circle must contain the query points and it must lie in the halfplanes delimited by the query lines.
Query Order and the Polynomial Hierarchy
Venue: arXiv cs.CC 1999
Year: 1999

Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] initiated the field of query order, which studies the ways in which computational power is affected by the order in which information sources are accessed. The present paper studies, for the first time, query order as it applies to the levels of the polynomial hierarchy. We prove that the levels of the polynomial hierarchy are order-oblivious. Yet, we also show that these ordered query classes form new levels in the polynomial hierarchy unless the polynomial hierarchy collapses. We prove that all leaf language classes - and thus essentially all standard complexity classes - inherit all order-obliviousness results that hold for P.
Self-Specifying Machines
Venue: arXiv cs.CC 1999
Year: 1999

We study the computational power of machines that specify their own acceptance types, and show that they accept exactly the languages that $\manyonesharp$-reduce to NP sets. A natural variant accepts exactly the languages that $\manyonesharp$-reduce to P sets. We show that these two classes coincide if and only if $\psone = \psnnoplusbigohone$, where the latter class denotes the sets acceptable via at most one question to $\sharpp$ followed by at most a constant number of questions to $\np$.
Translating Equality Downwards
Venue: arXiv cs.CC 1999
Year: 1999

Downward translation of equality refers to cases where a collapse of some pair of complexity classes would induce a collapse of some other pair of complexity classes that (a priori) one expects are smaller. Recently, the first downward translation of equality was obtained that applied to the polynomial hierarchy-in particular, to bounded access to its levels [cs.CC/9910007]. In this paper, we provide a much broader downward translation that extends not only that downward translation but also that translation's elegant enhancement by Buhrman and Fortnow. Our work also sheds light on previous research on the structure of refined polynomial hierarchies, and strengthens the connection between the collapse of bounded query hierarchies and the collapse of the polynomial hierarchy.
The Complexity of Temporal Logic over the Reals
Venue: arXiv cs.LO 1999
Year: 1999

It is shown that the decision problem for the temporal logic with until and since connectives over real-numbers time is PSPACE-complete.
Finite-resolution hidden surface removal
Venue: arXiv cs.CG 1999
Year: 1999

We propose a hybrid image-space/object-space solution to the classical hidden surface removal problem: Given n disjoint triangles in Real^3 and p sample points (``pixels'') in the xy-plane, determine the first triangle directly behind each pixel. Our algorithm constructs the sampled visibility map of the triangles with respect to the pixels, which is the subset of the trapezoids in a trapezoidal decomposition of the analytic visibility map that contain at least one pixel. The sampled visibility map adapts to local changes in image complexity, and its complexity is bounded both by the number of pixels and by the complexity of the analytic visibility map. Our algorithm runs in time O(n^{1+e} + n^{2/3+e}t^{2/3} + p), where t is the output size and e is any positive constant. This is nearly optimal in the worst case and compares favorably with the best output-sensitive algorithms for both ray casting and analytic hidden surface removal. In the special case where the pixels form a regular grid, a sweepline variant of our algorithm runs in time O(n^{1+e} + n^{2/3+e}t^{2/3} + t log p), which is usually sublinear in the number of pixels.
Graph Ramsey games
Venue: arXiv cs.CC 1999
Year: 1999

We consider combinatorial avoidance and achievement games based on graph Ramsey theory: The players take turns in coloring still uncolored edges of a graph G, each player being assigned a distinct color, choosing one edge per move. In avoidance games, completing a monochromatic subgraph isomorphic to another graph A leads to immediate defeat or is forbidden and the first player that cannot move loses. In the avoidance+ variants, both players are free to choose more than one edge per move. In achievement games, the first player that completes a monochromatic subgraph isomorphic to A wins. Erdos & Selfridge (1973) were the first to identify some tractable subcases of these games, followed by a large number of further studies. We complete these investigations by settling the complexity of all unrestricted cases: We prove that general graph Ramsey avoidance, avoidance+, and achievement games and several variants thereof are PSPACE-complete. We ultra-strongly solve some nontrivial instances of graph Ramsey avoidance games that are based on symmetric binary Ramsey numbers and provide strong evidence that all other cases based on symmetric binary Ramsey numbers are effectively intractable. Keywords: combinatorial games, graph Ramsey theory, Ramsey game, PSPACE-completeness, complexity, edge coloring, winning strategy, achievement game, avoidance game, the game of Sim, Polya's enumeration formula, probabilistic counting, machine learning, heuristics, Java applet
Resolution of Indirect Anaphora in Japanese Sentences Using Examples 'X no Y (Y of X)'
Venue: arXiv cs.CL 1999
Year: 1999

A noun phrase can indirectly refer to an entity that has already been mentioned. For example, ``I went into an old house last night. The roof was leaking badly and ...'' indicates that ``the roof'' is associated with `` an old house}'', which was mentioned in the previous sentence. This kind of reference (indirect anaphora) has not been studied well in natural language processing, but is important for coherence resolution, language understanding, and machine translation. In order to analyze indirect anaphora, we need a case frame dictionary for nouns that contains knowledge of the relationships between two nouns but no such dictionary presently exists. Therefore, we are forced to use examples of ``X no Y'' (Y of X) and a verb case frame dictionary instead. We tried estimating indirect anaphora using this information and obtained a recall rate of 63% and a precision rate of 68% on test sentences. This indicates that the information of ``X no Y'' is useful to a certain extent when we cannot make use of a noun case frame dictionary. We estimated the results that would be given by a noun case frame dictionary, and obtained recall and precision rates of 71% and 82% respectively. Finally, we proposed a way to construct a noun case frame dictionary by using examples of ``X no Y.''
An Estimate of Referent of Noun Phrases in Japanese Sentences
Venue: arXiv cs.CL 1999
Year: 1999

In machine translation and man-machine dialogue, it is important to clarify referents of noun phrases. We present a method for determining the referents of noun phrases in Japanese sentences by using the referential properties, modifiers, and possessors of noun phrases. Since the Japanese language has no articles, it is difficult to decide whether a noun phrase has an antecedent or not. We had previously estimated the referential properties of noun phrases that correspond to articles by using clue words in the sentences. By using these referential properties, our system determined the referents of noun phrases in Japanese sentences. Furthermore we used the modifiers and possessors of noun phrases in determining the referents of noun phrases. As a result, on training sentences we obtained a precision rate of 82% and a recall rate of 85% in the determination of the referents of noun phrases that have antecedents. On test sentences, we obtained a precision rate of 79% and a recall rate of 77%.