OpenRaiser/Intern-Atlas huggingface dataset:
A decision procedure for well-formed linear quantum cellular automata
Venue: arXiv cs.DS 2000
Year: 2000

In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since it enables us to define the probability of a configuration in an observation as the squared magnitude of its amplitude. We give an efficient algorithm which decides if a linear quantum cellular automaton is well-formed. The complexity of the algorithm is $O(n^2)$ in the algebraic model of computation if the input automaton has continuous neighborhood.
Processor Verification Using Efficient Reductions of the Logic of Uninterpreted Functions to Propositional Logic
Venue: arXiv cs.LO 2000
Year: 2000

The logic of equality with uninterpreted functions (EUF) provides a means of abstracting the manipulation of data by a processor when verifying the correctness of its control logic. By reducing formulas in this logic to propositional formulas, we can apply Boolean methods such as Ordered Binary Decision Diagrams (BDDs) and Boolean satisfiability checkers to perform the verification. We can exploit characteristics of the formulas describing the verification conditions to greatly simplify the propositional formulas generated. In particular, we exploit the property that many equations appear only in positive form. We can therefore reduce the set of interpretations of the function symbols that must be considered to prove that a formula is universally valid to those that are ``maximally diverse.'' We present experimental results demonstrating the efficiency of this approach when verifying pipelined processors using the method proposed by Burch and Dill.
PIPE: Personalizing Recommendations via Partial Evaluation
Venue: arXiv cs.IR 2000
Year: 2000

It is shown that personalization of web content can be advantageously viewed as a form of partial evaluation --- a technique well known in the programming languages community. The basic idea is to model a recommendation space as a program, then partially evaluate this program with respect to user preferences (and features) to obtain specialized content. This technique supports both content-based and collaborative approaches, and is applicable to a range of applications that require automatic information integration from multiple web sources. The effectiveness of this methodology is illustrated by two example applications --- (i) personalizing content for visitors to the Blacksburg Electronic Village (http://www.bev.net), and (ii) locating and selecting scientific software on the Internet. The scalability of this technique is demonstrated by its ability to interface with online web ontologies that index thousands of web pages.
A syntactical analysis of non-size-increasing polynomial time computation
Venue: arXiv cs.LO 2001
Year: 2001

A syntactical proof is given that all functions definable in a certain affine linear typed lambda-calculus with iteration in all types are polynomial time computable. The proof provides explicit polynomial bounds that can easily be calculated.
Automated Debugging In Java Using OCL And JDI
Venue: arXiv cs.SE 2001
Year: 2001

Correctness constraints provide a foundation for automated debugging within object-oriented systems. This paper discusses a new approach to incorporating correctness constraints into Java development environments. Our approach uses the Object Constraint Language ("OCL") as a specification language and the Java Debug Interface ("JDI") as a verification API. OCL provides a standard language for expressing object-oriented constraints that can integrate with Unified Modeling Language ("UML") software models. JDI provides a standard Java API capable of supporting type-safe and side effect free runtime constraint evaluation. The resulting correctness constraint mechanism: (1) entails no programming language modifications; (2) requires neither access nor changes to existing source code; and (3) works with standard off-the-shelf Java virtual machines ("VMs"). A prototype correctness constraint auditor is presented to demonstrate the utility of this mechanism for purposes of automated debugging.
Multiple-Size Divide-and-Conquer Recurrences
Venue: arXiv cs.GL 2001
Year: 2001

This short note reports a master theorem on tight asymptotic solutions to divide-and-conquer recurrences with more than one recursive term: for example, T(n) = 1/4 T(n/16) + 1/3 T(3n/5) + 4 T(n/100) + 10 T(n/300) + n^2.
Combinatorial Toolbox for Protein Sequence Design and Landscape Analysis in the Grand Canonical Model
Venue: arXiv cs.CE 2001
Year: 2001

In modern biology, one of the most important research problems is to understand how protein sequences fold into their native 3D structures. To investigate this problem at a high level, one wishes to analyze the protein landscapes, i.e., the structures of the space of all protein sequences and their native 3D structures. Perhaps the most basic computational problem at this level is to take a target 3D structure as input and design a fittest protein sequence with respect to one or more fitness functions of the target 3D structure. We develop a toolbox of combinatorial techniques for protein landscape analysis in the Grand Canonical model of Sun, Brem, Chan, and Dill. The toolbox is based on linear programming, network flow, and a linear-size representation of all minimum cuts of a network. It not only substantially expands the network flow technique for protein sequence design in Kleinberg's seminal work but also is applicable to a considerably broader collection of computational problems than those considered by Kleinberg. We have used this toolbox to obtain a number of efficient algorithms and hardness results. We have further used the algorithms to analyze 3D structures drawn from the Protein Data Bank and have discovered some novel relationships between such native 3D structures and the Grand Canonical model.
A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
Venue: arXiv cs.DS 2001
Year: 2001

We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property pi is called a pi-graph. If pi satisfies certain properties, then an n-node m-edge pi-graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most beta(n)+o(beta(n)) bits for any continuous super-additive function beta(n) so that there are at most 2^{beta(n)+o(beta(n))} distinct n-node pi-graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such pi include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) G is directed or undirected; (3) G is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from {1, ..., ell_1} for ell_1 <= n; (5) the edges of G are labeled with labels from {1, ..., ell_2} for ell_2 <= m; and (6) each node (respectively, edge) of G has at most ell_3 = O(1) self-loops (respectively, ell_4 = O(1) multiple edges). Moreover, ell_3 and ell_4 are not required to be O(1) for the cases of pi being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes.
Deterministic computations whose history is independent of the order of asynchronous updating
Venue: arXiv cs.DC 2001
Year: 2001

Consider a network of processors (sites) in which each site x has a finite set N(x) of neighbors. There is a transition function f that for each site x computes the next state ξ(x) from the states in N(x). But these transitions (updates) are applied in arbitrary order, one or many at a time. If the state of site x at time t is η(x,t) then let us define the sequence ζ(x,0), ζ(x,1), ... by taking the sequence η(x,0), η(x,1), ..., and deleting repetitions. The function f is said to have invariant histories if the sequence ζ(x,i), (while it lasts, in case it is finite) depends only on the initial configuration, not on the order of updates. This paper shows that though the invariant history property is typically undecidable, there is a useful simple sufficient condition, called commutativity: For any configuration, for any pair x,y of neighbors, if the updating would change both ξ(x) and ξ(y) then the result of updating first x and then y is the same as the result of doing this in the reverse order.
Open Archives Initiative protocol development and implementation at arXiv
Venue: arXiv cs.DL 2001
Year: 2001

I outline the involvement of the Los Alamos e-print archive (arXiv) within the Open Archives Initiative (OAI) and describe the implementation of the data provider side of the OAI protocol v1.0. I highlight the ways in which we map the existing structure of arXiv onto elements of the protocol.
On the predictability of Rainfall in Kerala- An application of ABF Neural Network
Venue: arXiv cs.NE 2001
Year: 2001

Rainfall in Kerala State, the southern part of Indian Peninsula in particular is caused by the two monsoons and the two cyclones every year. In general, climate and rainfall are highly nonlinear phenomena in nature giving rise to what is known as the `butterfly effect'. We however attempt to train an ABF neural network on the time series rainfall data and show for the first time that in spite of the fluctuations resulting from the nonlinearity in the system, the trends in the rainfall pattern in this corner of the globe have remained unaffected over the past 87 years from 1893 to 1980. We also successfully filter out the chaotic part of the system and illustrate that its effects are marginal over long term predictions.
Communities of Practice: Going Virtual
Venue: arXiv cs.HC 2001
Year: 2001

With the current trends towards downsizing, outsourcing and globalisation, modern organisations are reducing the numbers of people they employ. In addition, organisations now have to cope with the increasing internationalisation of business forcing collaboration and knowledge sharing across time and distance simultaneously. There is a need for new ways of thinking about how knowledge is shared in distributed groups. In this paper we explore a relatively new approach to knowledge sharing using Lave and Wenger's (1991) theory of Communities of Practice (CoPs). We investigate whether CoPs might translate to a geographically distributed international environment through a case study that explores the functioning of a CoP across national boundaries.
Rapid Application Evolution and Integration Through Document Metamorphosis
Venue: arXiv cs.DB 2001
Year: 2001

The Harland document management system implements a data model in which document (object) structure can be altered by mixin-style multiple inheritance at any time. This kind of structural fluidity has long been supported by knowledge-base management systems, but its use has primarily been in support of reasoning and inference. In this paper, we report our experiences building and supporting several non-trivial applications on top of this data model. Based on these experiences, we argue that structural fluidity is convenient for data-intensive applications other than knowledge-base management. Specifically, we suggest that this flexible data model is a natural fit for the decoupled programming methodology that arises naturally when using enterprise component frameworks.
Secure, Efficient Data Transport and Replica Management for High-Performance Data-Intensive Computing
Venue: arXiv cs.DC 2001
Year: 2001

An emerging class of data-intensive applications involve the geographically dispersed extraction of complex scientific information from very large collections of measured or computed data. Such applications arise, for example, in experimental physics, where the data in question is generated by accelerators, and in simulation science, where the data is generated by supercomputers. So-called Data Grids provide essential infrastructure for such applications, much as the Internet provides essential services for applications such as e-mail and the Web. We describe here two services that we believe are fundamental to any Data Grid: reliable, high-speed transporet and replica management. Our high-speed transport service, GridFTP, extends the popular FTP protocol with new features required for Data Grid applciations, such as striping and partial file access. Our replica management service integrates a replica catalog with GridFTP transfers to provide for the creation, registration, location, and management of dataset replicas. We present the design of both services and also preliminary performance results. Our implementations exploit security and other services provided by the Globus Toolkit.
Local Search Techniques for Constrained Portfolio Selection Problems
Venue: arXiv cs.CE 2001
Year: 2001

We consider the problem of selecting a portfolio of assets that provides the investor a suitable balance of expected return and risk. With respect to the seminal mean-variance model of Markowitz, we consider additional constraints on the cardinality of the portfolio and on the quantity of individual shares. Such constraints better capture the real-world trading system, but make the problem more difficult to be solved with exact methods. We explore the use of local search techniques, mainly tabu search, for the portfolio selection problem. We compare and combine previous work on portfolio selection that makes use of the local search approach and we propose new algorithms that combine different neighborhood relations. In addition, we show how the use of randomization and of a simple form of adaptiveness simplifies the setting of a large number of critical parameters. Finally, we show how our techniques perform on public benchmarks.
Rule Writing or Annotation: Cost-efficient Resource Usage for Base Noun Phrase Chunking
Venue: arXiv cs.CL 2001
Year: 2001

This paper presents a comprehensive empirical comparison between two approaches for developing a base noun phrase chunker: human rule writing and active learning using interactive real-time human annotation. Several novel variations on active learning are investigated, and underlying cost models for cross-modal machine learning comparison are presented and explored. Results show that it is more efficient and more successful by several measures to train a system using active learning annotation rather than hand-crafted rule writing at a comparable level of human labor investment.
Parallel implementation of the TRANSIMS micro-simulation
Venue: arXiv cs.CE 2001
Year: 2001

This paper describes the parallel implementation of the TRANSIMS traffic micro-simulation. The parallelization method is domain decomposition, which means that each CPU of the parallel computer is responsible for a different geographical area of the simulated region. We describe how information between domains is exchanged, and how the transportation network graph is partitioned. An adaptive scheme is used to optimize load balancing. We then demonstrate how computing speeds of our parallel micro-simulations can be systematically predicted once the scenario and the computer architecture are known. This makes it possible, for example, to decide if a certain study is feasible with a certain computing budget, and how to invest that budget. The main ingredients of the prediction are knowledge about the parallel implementation of the micro-simulation, knowledge about the characteristics of the partitioning of the transportation network graph, and knowledge about the interaction of these quantities with the computer system. In particular, we investigate the differences between switched and non-switched topologies, and the effects of 10 Mbit, 100 Mbit, and Gbit Ethernet. keywords: Traffic simulation, parallel computing, transportation planning, TRANSIMS
A Complete WordNet1.5 to WordNet1.6 Mapping
Venue: arXiv cs.CL 2001
Year: 2001

We describe a robust approach for linking already existing lexical/semantic hierarchies. We use a constraint satisfaction algorithm (relaxation labelling) to select --among a set of candidates-- the node in a target taxonomy that bests matches each node in a source taxonomy. In this paper we present the complete mapping of the nominal, verbal, adjectival and adverbial parts of WordNet 1.5 onto WordNet 1.6.
Applying Slicing Technique to Software Architectures
Venue: arXiv cs.SE 2001
Year: 2001

Software architecture is receiving increasingly attention as a critical design level for software systems. As software architecture design resources (in the form of architectural specifications) are going to be accumulated, the development of techniques and tools to support architectural understanding, testing, reengineering, maintenance, and reuse will become an important issue. This paper introduces a new form of slicing, named architectural slicing, to aid architectural understanding and reuse. In contrast to traditional slicing, architectural slicing is designed to operate on the architectural specification of a software system, rather than the source code of a program. Architectural slicing provides knowledge about the high-level structure of a software system, rather than the low-level implementation details of a program. In order to compute an architectural slice, we present the architecture information flow graph which can be used to represent information flows in a software architecture. Based on the graph, we give a two-phase algorithm to compute an architectural slice.
The alldifferent Constraint: A Survey
Venue: arXiv cs.PL 2001
Year: 2001

The constraint of difference is known to the constraint programming community since Lauriere introduced Alice in 1978. Since then, several solving strategies have been designed for this constraint. In this paper we give both a practical overview and an abstract comparison of these different strategies.
Optimization Over Zonotopes and Training Support Vector Machines
Venue: arXiv cs.CG 2001
Year: 2001

We make a connection between classical polytopes called zonotopes and Support Vector Machine (SVM) classifiers. We combine this connection with the ellipsoid method to give some new theoretical results on training SVMs. We also describe some special properties of soft margin C-SVMs as parameter C goes to infinity.
Solving Composed First-Order Constraints from Discrete-Time Robust Control
Venue: arXiv cs.LO 2001
Year: 2001

This paper deals with a problem from discrete-time robust control which requires the solution of constraints over the reals that contain both universal and existential quantifiers. For solving this problem we formulate it as a program in a (fictitious) constraint logic programming language with explicit quantifier notation. This allows us to clarify the special structure of the problem, and to extend an algorithm for computing approximate solution sets of first-order constraints over the reals to exploit this structure. As a result we can deal with inputs that are clearly out of reach for current symbolic solvers.
An object evaluator to generate flexible applications
Venue: arXiv cs.LO 2001
Year: 2001

This paper contains a brief discussion of an object evaluator which is based on principles of evaluations in a category. The main tool system referred as the Application Development Environment (ADE) is used to build database applications involving the graphical user interface (GUI). The separation of a database access and the user interface is reached by distinguishing the potential and actual objects. The variety of applications may be generated that communicate with different and distinct desktop databases. The commutative diagrams' technique allows to involve retrieval and call of the delayed procedures.
Hinged Kite Mirror Dissection
Venue: arXiv cs.CG 2001
Year: 2001

Any two polygons of equal area can be partitioned into congruent sets of polygonal pieces, and in many cases one can connect the pieces by flexible hinges while still allowing the connected set to form both polygons. However it is open whether such a hinged dissection always exists. We solve a special case of this problem, by showing that any asymmetric polygon always has a hinged dissection to its mirror image. Our dissection forms a chain of kite-shaped pieces, found by a circle-packing algorithm for quadrilateral mesh generation. A hinged mirror dissection of a polygon with n sides can be formed with O(n) kites in O(n log n) time.
Using the No-Search Easy-Hard Technique for Downward Collapse
Venue: arXiv cs.CC 2001
Year: 2001

The top part of the preceding figure [figure appears in actual paper] shows some classes from the (truth-table) bounded-query and boolean hierarchies. It is well-known that if either of these hierarchies collapses at a given level, then all higher levels of that hierarchy collapse to that same level. This is a standard ``upward translation of equality'' that has been known for over a decade. The issue of whether these hierarchies can translate equality {\em downwards\/} has proven vastly more challenging. In particular, with regard to the figure above, consider the following claim: $$P_{m-tt}^{Σ_k^p} = P_{m+1-tt}^{Σ_k^p} \implies DIFF_m(Σ_k^p) coDIFF_m(Σ_k^p) = BH(Σ_k^p). (*) $$ This claim, if true, says that equality translates downwards between levels of the bounded-query hierarchy and the boolean hierarchy levels that (before the fact) are immediately below them. Until recently, it was not known whether (*) {\em ever\/} held, except for the degenerate cases $m=0$ and $k=0$. Then Hemaspaandra, Hemaspaandra, and Hempel \cite{hem-hem-hem:j:downward-translation} proved that (*) holds for all $m$, for $k > 2$. Buhrman and Fortnow~\cite{buh-for:j:two-queries} then showed that, when $k=2$, (*) holds for the case $m = 1$. In this paper, we prove that for the case $k=2$, (*) holds for all values of $m$. Since there is an oracle relative to which ``for $k=1$, (*) holds for all $m$'' fails \cite{buh-for:j:two-queries}, our achievement of the $k=2$ case cannot to be strengthened to $k=1$ by any relativizable proof technique. The new downward translation we obtain also tightens the collapse in the polynomial hierarchy implied by a collapse in the bounded-query hierarchy of the second level of the polynomial hierarchy.
Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones
Venue: arXiv cs.CC 2001
Year: 2001

We prove that computing a single pair of vertices that are mapped onto each other by an isomorphism $ϕ$ between two isomorphic graphs is as hard as computing $ϕ$ itself. This result optimally improves upon a result of Gál et al. We establish a similar, albeit slightly weaker, result about computing complete Hamiltonian cycles of a graph from partial Hamiltonian cycles.
MACE 2.0 Reference Manual and Guide
Venue: arXiv cs.LO 2001
Year: 2001

MACE is a program that searches for finite models of first-order statements. The statement to be modeled is first translated to clauses, then to relational clauses; finally for the given domain size, the ground instances are constructed. A Davis-Putnam-Loveland-Logeman procedure decides the propositional problem, and any models found are translated to first-order models. MACE is a useful complement to the theorem prover Otter, with Otter searching for proofs and MACE looking for countermodels.
Using the Distribution of Performance for Studying Statistical NLP Systems and Corpora
Venue: arXiv cs.CL 2001
Year: 2001

Statistical NLP systems are frequently evaluated and compared on the basis of their performances on a single split of training and test data. Results obtained using a single split are, however, subject to sampling noise. In this paper we argue in favour of reporting a distribution of performance figures, obtained by resampling the training data, rather than a single number. The additional information from distributions can be used to make statistically quantified statements about differences across parameter settings, systems, and corpora.