OpenRaiser/Intern-Atlas huggingface dataset:
Complexity analysis for algorithmically simple strings
Venue: arXiv cs.LG 2002
Year: 2002

Given a reference computer, Kolmogorov complexity is a well defined function on all binary strings. In the standard approach, however, only the asymptotic properties of such functions are considered because they do not depend on the reference computer. We argue that this approach can be more useful if it is refined to include an important practical case of simple binary strings. Kolmogorov complexity calculus may be developed for this case if we restrict the class of available reference computers. The interesting problem is to define a class of computers which is restricted in a {\it natural} way modeling the real-life situation where only a limited class of computers is physically available to us. We give an example of what such a natural restriction might look like mathematically, and show that under such restrictions some error terms, even logarithmic in complexity, can disappear from the standard complexity calculus. Keywords: Kolmogorov complexity; Algorithmic information theory.
Convergent Approximate Solving of First-Order Constraints by Approximate Quantifiers
Venue: arXiv cs.LO 2002
Year: 2002

Exactly solving first-order constraints (i.e., first-order formulas over a certain predefined structure) can be a very hard, or even undecidable problem. In continuous structures like the real numbers it is promising to compute approximate solutions instead of exact ones. However, the quantifiers of the first-order predicate language are an obstacle to allowing approximations to arbitrary small error bounds. In this paper we solve the problem by modifying the first-order language and replacing the classical quantifiers with approximate quantifiers. These also have two additional advantages: First, they are tunable, in the sense that they allow the user to decide on the trade-off between precision and efficiency. Second, they introduce additional expressivity into the first-order language by allowing reasoning over the size of solution sets.
Automated Real-Time Testing (ARTT) for Embedded Control Systems (ECS)
Venue: arXiv cs.OH 2002
Year: 2002

Developing real-time automated test systems for embedded control systems has been a real problem. Some engineers and scientists have used customized software and hardware as a solution, which can be very expensive and time consuming to develop. We have discovered how to integrate a suite of commercially available off-the-shelf software tools and hardware to develop a scalable test platform that is capable of performing complete black-box testing for a dual-channel real-time Embedded-PLC-based control system (www.aps.anl.gov). We will discuss how the Vali/Test Pro testing methodology was implemented to structure testing for a personnel safety system with large quantities of requirements and test cases. This work was supported by the U.S. Department of Energy, Basic Energy Sciences, under Contract No. W-31-109-Eng-38.
Sharpening Occam's Razor
Venue: arXiv cs.LG 2002
Year: 2002

We provide a new representation-independent formulation of Occam's razor theorem, based on Kolmogorov complexity. This new formulation allows us to: (i) Obtain better sample complexity than both length-based and VC-based versions of Occam's razor theorem, in many applications. (ii) Achieve a sharper reverse of Occam's razor theorem than previous work. Specifically, we weaken the assumptions made in an earlier publication, and extend the reverse to superpolynomial running times.
Bundling Equilibrium in Combinatorial auctions
Venue: arXiv cs.GT 2002
Year: 2002

This paper analyzes individually-rational ex post equilibrium in the VC (Vickrey-Clarke) combinatorial auctions. If $Σ$ is a family of bundles of goods, the organizer may restrict the participants by requiring them to submit their bids only for bundles in $Σ$. The $Σ$-VC combinatorial auctions (multi-good auctions) obtained in this way are known to be individually-rational truth-telling mechanisms. In contrast, this paper deals with non-restricted VC auctions, in which the buyers restrict themselves to bids on bundles in $Σ$, because it is rational for them to do so. That is, it may be that when the buyers report their valuation of the bundles in $Σ$, they are in an equilibrium. We fully characterize those $Σ$ that induce individually rational equilibrium in every VC auction, and we refer to the associated equilibrium as a bundling equilibrium. The number of bundles in $Σ$ represents the communication complexity of the equilibrium. A special case of bundling equilibrium is partition-based equilibrium, in which $Σ$ is a field, that is, it is generated by a partition. We analyze the tradeoff between communication complexity and economic efficiency of bundling equilibrium, focusing in particular on partition-based equilibrium.
Structure from Motion: Theoretical Foundations of a Novel Approach Using Custom Built Invariants
Venue: arXiv cs.CV 2002
Year: 2002

We rephrase the problem of 3D reconstruction from images in terms of intersections of projections of orbits of custom built Lie groups actions. We then use an algorithmic method based on moving frames "a la Fels-Olver" to obtain a fundamental set of invariants of these groups actions. The invariants are used to define a set of equations to be solved by the points of the 3D object, providing a new technique for recovering 3D structure from motion.
Components of an NSDL Architecture: Technical Scope and Functional Model
Venue: arXiv cs.DL 2002
Year: 2002

We describe work leading toward specification of a technical architecture for the National Science, Mathematics, Engineering, and Technology Education Digital Library (NSDL). This includes a technical scope and a functional model, with some elaboration on the particularly rich set of library services that NSDL is expected eventually to encompass.
The Witness Properties and the Semantics of the Prolog Cut
Venue: arXiv cs.PL 2002
Year: 2002

The semantics of the Prolog ``cut'' construct is explored in the context of some desirable properties of logic programming systems, referred to as the witness properties. The witness properties concern the operational consistency of responses to queries. A generalization of Prolog with negation as failure and cut is described, and shown not to have the witness properties. A restriction of the system is then described, which preserves the choice and first-solution behaviour of cut but allows the system to have the witness properties. The notion of cut in the restricted system is more restricted than the Prolog hard cut, but retains the useful first-solution behaviour of hard cut, not retained by other proposed cuts such as the ``soft cut''. It is argued that the restricted system achieves a good compromise between the power and utility of the Prolog cut and the need for internal consistency in logic programming systems. The restricted system is given an abstract semantics, which depends on the witness properties; this semantics suggests that the restricted system has a deeper connection to logic than simply permitting some computations which are logical. Parts of this paper appeared previously in a different form in the Proceedings of the 1995 International Logic Programming Symposium.
Classes of service under perfect competition and technological change: a model for the dynamics of the Internet?
Venue: arXiv cs.GT 2002
Year: 2002

Certain services may be provided in a continuous, one-dimensional, ordered range of different qualities and a customer requiring a service of quality q can only be offered a quality superior or equal to q. Only a discrete set of different qualities will be offered, and a service provider will provide the same service (of fixed quality b) to all customers requesting qualities of service inferior or equal to b. Assuming all services (of quality b) are priced identically, a monopolist will choose the qualities of service and the prices that maximize profit but, under perfect competition, a service provider will choose the (inferior) quality of service that can be priced at the lowest price. Assuming significant economies of scale, two fundamentally different regimes are possible: either a number of different classes of service are offered (DC regime), or a unique class of service offers an unbounded quality of service (UC regime). The DC regime appears in one of two sub-regimes: one, BDC, in which a finite number of classes is offered, the qualities of service offered are bounded and requests for high-quality services are not met, or UDC in which an infinite number of classes of service are offered and every request is met. The types of the demand curve and of the economies of scale, not the pace of technological change, determine the regime and the class boundaries. The price structure in the DC regime obeys very general laws.
Nonmonotonic inference operations
Venue: arXiv cs.AI 2002
Year: 2002

A. Tarski proposed the study of infinitary consequence operations as the central topic of mathematical logic. He considered monotonicity to be a property of all such operations. In this paper, we weaken the monotonicity requirement and consider more general operations, inference operations. These operations describe the nonmonotonic logics both humans and machines seem to be using when infering defeasible information from incomplete knowledge. We single out a number of interesting families of inference operations. This study of infinitary inference operations is inspired by the results of Kraus, Lehmann and Magidor on finitary nonmonotonic operations, but this paper is self-contained.
The efficient generation of unstructured control volumes in 2D and 3D
Venue: arXiv cs.CG 2002
Year: 2002

Many problems in engineering, chemistry and physics require the representation of solutions in complex geometries. In the paper we deal with a problem of unstructured mesh generation for the control volume method. We propose an algorithm which bases on the spheres generation in central points of the control volumes.
Generalized Cores
Venue: arXiv cs.DS 2002
Year: 2002

Cores are, besides connectivity components, one among few concepts that provides us with efficient decompositions of large graphs and networks. In the paper a generalization of the notion of core of a graph based on vertex property function is presented. It is shown that for the local monotone vertex property functions the corresponding cores can be determined in $O(m \max (Δ, \log n))$ time.
Capturing Knowledge of User Preferences: ontologies on recommender systems
Venue: arXiv cs.LG 2002
Year: 2002

Tools for filtering the World Wide Web exist, but they are hampered by the difficulty of capturing user preferences in such a dynamic environment. We explore the acquisition of user profiles by unobtrusive monitoring of browsing behaviour and application of supervised machine-learning techniques coupled with an ontological representation to extract user preferences. A multi-class approach to paper classification is used, allowing the paper topic taxonomy to be utilised during profile construction. The Quickstep recommender system is presented and two empirical studies evaluate it in a real work setting, measuring the effectiveness of using a hierarchical topic ontology compared with an extendable flat list.
Towards Experimental Nanosound Using Almost Disjoint Set Theory
Venue: arXiv cs.SD 2002
Year: 2002

Music composition using digital audio sequence editors is increasingly performed in a visual workspace where sound complexes are built from discrete sound objects, called gestures that are arranged in time and space to generate a continuous composition. The visual workspace, common to most industry standard audio loop sequencing software, is premised on the arrangement of gestures defined with geometric shape properties. Here, one aspect of fractal set theory was validated using audio-frequency sets to evaluate self-affine scaling behavior when new sound complexes are built through union and intersection operations on discrete musical gestures. Results showed that intersection of two sets revealed lower complexity compared with the union operator, meaning that the intersection of two sound gestures is an almost disjoint set, and in accord with formal logic. These results are also discussed with reference to fuzzy sets, cellular automata, nanotechnology and self-organization to further explore the link between sequenced notation and complexity.
Improving Table Compression with Combinatorial Optimization
Venue: arXiv cs.DS 2002
Year: 2002

We study the problem of compressing massive tables within the partition-training paradigm introduced by Buchsbaum et al. [SODA'00], in which a table is partitioned by an off-line training procedure into disjoint intervals of columns, each of which is compressed separately by a standard, on-line compressor like gzip. We provide a new theory that unifies previous experimental observations on partitioning and heuristic observations on column permutation, all of which are used to improve compression rates. Based on the theory, we devise the first on-line training algorithms for table compression, which can be applied to individual files, not just continuously operating sources; and also a new, off-line training algorithm, based on a link to the asymmetric traveling salesman problem, which improves on prior work by rearranging columns prior to partitioning. We demonstrate these results experimentally. On various test files, the on-line algorithms provide 35-55% improvement over gzip with negligible slowdown; the off-line reordering provides up to 20% further improvement over partitioning alone. We also show that a variation of the table compression problem is MAX-SNP hard.
A steady state model for graph power laws
Venue: arXiv cs.DM 2002
Year: 2002

Power law distribution seems to be an important characteristic of web graphs. Several existing web graph models generate power law graphs by adding new vertices and non-uniform edge connectivities to existing graphs. Researchers have conjectured that preferential connectivity and incremental growth are both required for the power law distribution. In this paper, we propose a different web graph model with power law distribution that does not require incremental growth. We also provide a comparison of our model with several others in their ability to predict web graph clustering behavior.
On the Computational Complexity of Consistent Query Answers
Venue: arXiv cs.DB 2002
Year: 2002

We consider here the problem of obtaining reliable, consistent information from inconsistent databases -- databases that do not have to satisfy given integrity constraints. We use the notion of consistent query answer -- a query answer which is true in every (minimal) repair of the database. We provide a complete classification of the computational complexity of consistent answers to first-order queries w.r.t. functional dependencies and denial constraints. We show how the complexity depends on the {\em type} of the constraints considered, their {\em number}, and the {\em size} of the query. We obtain several new PTIME cases, using new algorithms.
The Sketch of a Polymorphic Symphony
Venue: arXiv cs.PL 2002
Year: 2002

In previous work, we have introduced functional strategies, that is, first-class generic functions that can traverse into terms of any type while mixing uniform and type-specific behaviour. In the present paper, we give a detailed description of one particular Haskell-based model of functional strategies. This model is characterised as follows. Firstly, we employ first-class polymorphism as a form of second-order polymorphism as for the mere types of functional strategies. Secondly, we use an encoding scheme of run-time type case for mixing uniform and type-specific behaviour. Thirdly, we base all traversal on a fundamental combinator for folding over constructor applications. Using this model, we capture common strategic traversal schemes in a highly parameterised style. We study two original forms of parameterisation. Firstly, we design parameters for the specific control-flow, data-flow and traversal characteristics of more concrete traversal schemes. Secondly, we use overloading to postpone commitment to a specific type scheme of traversal. The resulting portfolio of traversal schemes can be regarded as a challenging benchmark for setups for typed generic programming. The way we develop the model and the suite of traversal schemes, it becomes clear that parameterised + typed strategic programming is best viewed as a potent combination of certain bits of parametric, intensional, polytypic, and ad-hoc polymorphism.
Design Patterns for Functional Strategic Programming
Venue: arXiv cs.PL 2002
Year: 2002

In previous work, we introduced the fundamentals and a supporting combinator library for \emph{strategic programming}. This an idiom for generic programming based on the notion of a \emph{functional strategy}: a first-class generic function that cannot only be applied to terms of any type, but which also allows generic traversal into subterms and can be customized with type-specific behaviour. This paper seeks to provide practicing functional programmers with pragmatic guidance in crafting their own strategic programs. We present the fundamentals and the support from a user's perspective, and we initiate a catalogue of \emph{strategy design patterns}. These design patterns aim at consolidating strategic programming expertise in accessible form.
Navigating the Small World Web by Textual Cues
Venue: arXiv cs.IR 2002
Year: 2002

Can a Web crawler efficiently locate an unknown relevant page? While this question is receiving much empirical attention due to its considerable commercial value in the search engine community [Cho98,Chakrabarti99,Menczer00,Menczer01], theoretical efforts to bound the performance of focused navigation have only exploited the link structure of the Web graph, neglecting other features [Kleinberg01,Adamic01,Kim02]. Here I investigate the connection between linkage and a content-induced topology of Web pages, suggesting that efficient paths can be discovered by decentralized navigation algorithms based on textual cues.
A Calculus for End-to-end Statistical Service Guarantees
Venue: arXiv cs.NI 2002
Year: 2002

The deterministic network calculus offers an elegant framework for determining delays and backlog in a network with deterministic service guarantees to individual traffic flows. This paper addresses the problem of extending the network calculus to a probabilistic framework with statistical service guarantees. Here, the key difficulty relates to expressing, in a statistical setting, an end-to-end (network) service curve as a concatenation of per-node service curves. The notion of an effective service curve is developed as a probabilistic bound on the service received by an individual flow. It is shown that per-node effective service curves can be concatenated to yield a network effective service curve.
Ellogon: A New Text Engineering Platform
Venue: arXiv cs.CL 2002
Year: 2002

This paper presents Ellogon, a multi-lingual, cross-platform, general-purpose text engineering environment. Ellogon was designed in order to aid both researchers in natural language processing, as well as companies that produce language engineering systems for the end-user. Ellogon provides a powerful TIPSTER-based infrastructure for managing, storing and exchanging textual data, embedding and managing text processing components as well as visualising textual data and their associated linguistic information. Among its key features are full Unicode support, an extensive multi-lingual graphical user interface, its modular architecture and the reduced hardware requirements.
Distance function wavelets - Part I: Helmholtz and convection-diffusion transforms and series
Venue: arXiv cs.CE 2002
Year: 2002

This report aims to present my research updates on distance function wavelets (DFW) based on the fundamental solutions and the general solutions of the Helmholtz, modified Helmholtz, and convection-diffusion equations, which include the isotropic Helmholtz-Fourier (HF) transform and series, the Helmholtz-Laplace (HL) transform, and the anisotropic convection-diffusion wavelets and ridgelets. The latter is set to handle discontinuous and track data problems. The edge effect of the HF series is addressed. Alternative existence conditions for the DFW transforms are proposed and discussed. To simplify and streamline the expression of the HF and HL transforms, a new dimension-dependent function notation is introduced. The HF series is also used to evaluate the analytical solutions of linear diffusion problems of arbitrary dimensionality and geometry. The weakness of this report is lacking of rigorous mathematical analysis due to the author's limited mathematical knowledge.
A variable-free dynamic semantics
Venue: arXiv cs.CL 2002
Year: 2002

I propose a variable-free treatment of dynamic semantics. By "dynamic semantics" I mean analyses of donkey sentences ("Every farmer who owns a donkey beats it") and other binding and anaphora phenomena in natural language where meanings of constituents are updates to information states, for instance as proposed by Groenendijk and Stokhof. By "variable-free" I mean denotational semantics in which functional combinators replace variable indices and assignment functions, for instance as advocated by Jacobson. The new theory presented here achieves a compositional treatment of dynamic anaphora that does not involve assignment functions, and separates the combinatorics of variable-free semantics from the particular linguistic phenomena it treats. Integrating variable-free semantics and dynamic semantics gives rise to interactions that make new empirical predictions, for example "donkey weak crossover" effects.
On-Line File Caching
Venue: arXiv cs.DS 2002
Year: 2002

In the on-line file-caching problem problem, the input is a sequence of requests for files, given on-line (one at a time). Each file has a non-negative size and a non-negative retrieval cost. The problem is to decide which files to keep in a fixed-size cache so as to minimize the sum of the retrieval costs for files that are not in the cache when requested. The problem arises in web caching by browsers and by proxies. This paper describes a natural generalization of LRU called Landlord and gives an analysis showing that it has an optimal performance guarantee (among deterministic on-line algorithms). The paper also gives an analysis of the algorithm in a so-called ``loosely'' competitive model, showing that on a ``typical'' cache size, either the performance guarantee is O(1) or the total retrieval cost is insignificant.
Prefix Codes: Equiprobable Words, Unequal Letter Costs
Venue: arXiv cs.DS 2002
Year: 2002

Describes a near-linear-time algorithm for a variant of Huffman coding, in which the letters may have non-uniform lengths (as in Morse code), but with the restriction that each word to be encoded has equal probability. [See also ``Huffman Coding with Unequal Letter Costs'' (2002).]
Eavesdropping on Electronic Guidebooks: Observing Learning Resources in Shared Listening Environments
Venue: arXiv cs.HC 2002
Year: 2002

We describe an electronic guidebook, Sotto Voce, that enables visitors to share audio information by eavesdropping on each other's guidebook activity. We have conducted three studies of visitors using electronic guidebooks in a historic house: one study with open air audio played through speakers and two studies with eavesdropped audio. An analysis of visitor interaction in these studies suggests that eavesdropped audio provides more social and interactive learning resources than open air audio played through speakers.