OpenRaiser/Intern-Atlas huggingface dataset:
Modeling State in Software Debugging of VHDL-RTL Designs -- A Model-Based Diagnosis Approach
Venue: arXiv cs.AI 2003
Year: 2003

In this paper we outline an approach of applying model-based diagnosis to the field of automatic software debugging of hardware designs. We present our value-level model for debugging VHDL-RTL designs and show how to localize the erroneous component responsible for an observed misbehavior. Furthermore, we discuss an extension of our model that supports the debugging of sequential circuits, not only at a given point in time, but also allows for considering the temporal behavior of VHDL-RTL designs. The introduced model is capable of handling state inherently present in every sequential circuit. The principal applicability of the new model is outlined briefly and we use industrial-sized real world examples from the ISCAS'85 benchmark suite to discuss the scalability of our approach.
Parametric Connectives in Disjunctive Logic Programming
Venue: arXiv cs.AI 2003
Year: 2003

Disjunctive Logic Programming (\DLP) is an advanced formalism for Knowledge Representation and Reasoning (KRR). \DLP is very expressive in a precise mathematical sense: it allows to express every property of finite structures that is decidable in the complexity class $\SigmaP{2}$ ($\NP^{\NP}$). Importantly, the \DLP encodings are often simple and natural. In this paper, we single out some limitations of \DLP for KRR, which cannot naturally express problems where the size of the disjunction is not known ``a priori'' (like N-Coloring), but it is part of the input. To overcome these limitations, we further enhance the knowledge modelling abilities of \DLP, by extending this language by {\em Parametric Connectives (OR and AND)}. These connectives allow us to represent compactly the disjunction/conjunction of a set of atoms having a given property. We formally define the semantics of the new language, named $DLP^{\bigvee,\bigwedge}$ and we show the usefulness of the new constructs on relevant knowledge-based problems. We address implementation issues and discuss related works.
Generic and Efficient Program Monitoring by trace analysis
Venue: arXiv cs.PL 2003
Year: 2003

Program execution monitoring consists of checking whole executions for given properties in order to collect global run-time information. Monitoring is very useful to maintain programs. However, application developers face the following dilemma: either they use existing tools which never exactly fit their needs, or they invest a lot of effort to implement monitoring code. In this article we argue that, when an event-oriented tracer exists, the compiler developers can enable the application developers to easily code their own, relevant, monitors which will run efficiently. We propose a high-level operator, called foldt, which operates on execution traces. One of the key advantages of our approach is that it allows a clean separation of concerns; the definition of monitors is neither intertwined in the user source code nor in the language compiler. We give a number of applications of the foldt operator to compute monitors for Mercury program executions: execution profiles, graphical abstract views, and two test coverage measurements. Each example is implemented by a few simple lines of Mercury. Detailed measurements show acceptable performance of the basic mechanism of foldt for executions of several millions of execution events.
Fine-Grained Authorization for Job Execution in the Grid: Design and Implementation
Venue: arXiv cs.CR 2003
Year: 2003

In this paper we describe our work on enabling fine-grained authorization for resource usage and management. We address the need of virtual organizations to enforce their own polices in addition to those of the resource owners, in regard to both resource consumption and job management. To implement this design, we propose changes and extensions to the Globus Toolkit's version 2 resource management mechanism. We describe the prototype and the policy language that we designed to express fine-grained policies, and we present an analysis of our solution.
Staging Transformations for Multimodal Web Interaction Management
Venue: arXiv cs.IR 2003
Year: 2003

Multimodal interfaces are becoming increasingly ubiquitous with the advent of mobile devices, accessibility considerations, and novel software technologies that combine diverse interaction media. In addition to improving access and delivery capabilities, such interfaces enable flexible and personalized dialogs with websites, much like a conversation between humans. In this paper, we present a software framework for multimodal web interaction management that supports mixed-initiative dialogs between users and websites. A mixed-initiative dialog is one where the user and the website take turns changing the flow of interaction. The framework supports the functional specification and realization of such dialogs using staging transformations -- a theory for representing and reasoning about dialogs based on partial input. It supports multiple interaction interfaces, and offers sessioning, caching, and co-ordination functions through the use of an interaction manager. Two case studies are presented to illustrate the promise of this approach.
Towards an Intelligent Database System Founded on the SP Theory of Computing and Cognition
Venue: arXiv cs.DB 2003
Year: 2003

The SP theory of computing and cognition, described in previous publications, is an attractive model for intelligent databases because it provides a simple but versatile format for different kinds of knowledge, it has capabilities in artificial intelligence, and it can also function like established database models when that is required. This paper describes how the SP model can emulate other models used in database applications and compares the SP model with those other models. The artificial intelligence capabilities of the SP model are reviewed and its relationship with other artificial intelligence systems is described. Also considered are ways in which current prototypes may be translated into an 'industrial strength' working system.
The Rank-Frequency Analysis for the Functional Style Corpora in the Ukrainian Language
Venue: arXiv cs.CL 2003
Year: 2003

We use the rank-frequency analysis for the estimation of Kernel Vocabulary size within specific corpora of Ukrainian. The extrapolation of high-rank behaviour is utilized for estimation of the total vocabulary size.
Weak Bezout inequality for D-modules
Venue: arXiv cs.SC 2003
Year: 2003

Let $\{w_{i,j}\}_{1\leq i\leq n, 1\leq j\leq s} \subset L_m=F(X_1,...,X_m)[{\partial \over \partial X_1},..., {\partial \over \partial X_m}]$ be linear partial differential operators of orders with respect to ${\partial \over \partial X_1},..., {\partial \over \partial X_m}$ at most $d$. We prove an upper bound n(4m^2d\min\{n,s\})^{4^{m-t-1}(2(m-t))} on the leading coefficient of the Hilbert-Kolchin polynomial of the left $L_m$-module $<\{w_{1,j}, ..., w_{n,j}\}_{1\leq j \leq s} > \subset L_m^n$ having the differential type $t$ (also being equal to the degree of the Hilbert-Kolchin polynomial). The main technical tool is the complexity bound on solving systems of linear equations over {\it algebras of fractions} of the form $$L_m(F[X_1,..., X_m, {\partial \over \partial X_1},..., {\partial \over \partial X_k}])^{-1}.$$
Embedding Web-based Statistical Translation Models in Cross-Language Information Retrieval
Venue: arXiv cs.CL 2003
Year: 2003

Although more and more language pairs are covered by machine translation services, there are still many pairs that lack translation resources. Cross-language information retrieval (CLIR) is an application which needs translation functionality of a relatively low level of sophistication since current models for information retrieval (IR) are still based on a bag-of-words. The Web provides a vast resource for the automatic construction of parallel corpora which can be used to train statistical translation models automatically. The resulting translation models can be embedded in several ways in a retrieval model. In this paper, we will investigate the problem of automatically mining parallel texts from the Web and different ways of integrating the translation models within the retrieval process. Our experiments on standard test collections for CLIR show that the Web-based translation models can surpass commercial MT systems in CLIR tasks. These results open the perspective of constructing a fully automatic query translation device for CLIR at a very low cost.
Failure-Free Genetic Algorithm Optimization of a System Controller Using SAFE/LEARNING Controllers in Tandem
Venue: arXiv cs.NE 2003
Year: 2003

The paper presents a method for failure free genetic algorithm optimization of a system controller. Genetic algorithms present a powerful tool that facilitates producing near-optimal system controllers. Applied to such methods of computational intelligence as neural networks or fuzzy logic, these methods are capable of combining the non-linear mapping capabilities of the latter with learning the system behavior directly, that is, without a prior model. At the same time, genetic algorithms routinely produce solutions that lead to the failure of the controlled system. Such solutions are generally unacceptable for applications where safe operation must be guaranteed. We present here a method of design, which allows failure-free application of genetic algorithms through utilization of SAFE and LEARNING controllers in tandem, where the SAFE controller recovers the system from dangerous states while the LEARNING controller learns its behavior. The method has been validated by applying it to an inherently unstable system of inverted pendulum.
Designing of a Community-based Translation Center
Venue: arXiv cs.HC 2003
Year: 2003

Interfaces that support multi-lingual content can reach a broader community. We wish to extend the reach of CITIDEL, a digital library for computing education materials, to support multiple languages. By doing so, we hope that it will increase the number of users, and in turn the number of resources. This paper discusses three approaches to translation (automated translation, developer-based, and community-based), and a brief evaluation of these approaches. It proposes a design for an online community translation center where volunteers help translate interface components and educational materials available in CITIDEL.
Inferring Termination Conditions for Logic Programs using Backwards Analysis
Venue: arXiv cs.PL 2003
Year: 2003

This paper focuses on the inference of modes for which a logic program is guaranteed to terminate. This generalises traditional termination analysis where an analyser tries to verify termination for a specified mode. Our contribution is a methodology in which components of traditional termination analysis are combined with backwards analysis to obtain an analyser for termination inference. We identify a condition on the components of the analyser which guarantees that termination inference will infer all modes which can be checked to terminate. The application of this methodology to enhance a traditional termination analyser to perform also termination inference is demonstrated.
Evolution: Google vs. DRIS
Venue: arXiv cs.DL 2003
Year: 2003

This paper gives an absolute new search system that builds the information retrieval infrastructure for Internet. Now most search engine companies are mainly concerned with how to make profit from company users by advertisement and ranking prominence, but never consider what its real customers will feel. Few web search engines can sell billions dollars just at the cost of inconvenience of most Internet users, but not its high quality of search service. When we have to bear the bothersome advertisements in the awful results and have no choices, Internet as the kind of public good will surely be undermined. If current Internet can't fully ensure our right to know, it may need some sound improvements or a revolution.
Speedup of Logic Programs by Binarization and Partial Deduction
Venue: arXiv cs.PL 2003
Year: 2003

Binary logic programs can be obtained from ordinary logic programs by a binarizing transformation. In most cases, binary programs obtained this way are less efficient than the original programs. (Demoen, 1992) showed an interesting example of a logic program whose computational behaviour was improved when it was transformed to a binary program and then specialized by partial deduction. The class of B-stratifiable logic programs is defined. It is shown that for every B-stratifiable logic program, binarization and subsequent partial deduction produce a binary program which does not contain variables for continuations introduced by binarization. Such programs usually have a better computational behaviour than the original ones. Both binarization and partial deduction can be easily automated. A comparison with other related approaches to program transformation is given.
Learning in a Compiler for MINSAT Algorithms
Venue: arXiv cs.LO 2003
Year: 2003

This paper describes learning in a compiler for algorithms solving classes of the logic minimization problem MINSAT, where the underlying propositional formula is in conjunctive normal form (CNF) and where costs are associated with the True/False values of the variables. Each class consists of all instances that may be derived from a given propositional formula and costs for True/False values by fixing or deleting variables, and by deleting clauses. The learning step begins once the compiler has constructed a solution algorithm for a given class. The step applies that algorithm to comparatively few instances of the class, analyses the performance of the algorithm on these instances, and modifies the underlying propositional formula, with the goal that the algorithm will perform much better on all instances of the class.
Partitioning schemes for quicksort and quickselect
Venue: arXiv cs.DS 2003
Year: 2003

We introduce several modifications of the partitioning schemes used in Hoare's quicksort and quickselect algorithms, including ternary schemes which identify keys less or greater than the pivot. We give estimates for the numbers of swaps made by each scheme. Our computational experiments indicate that ternary schemes allow quickselect to identify all keys equal to the selected key at little additional cost.
Polyhierarchical Classifications Induced by Criteria Polyhierarchies, and Taxonomy Algebra
Venue: arXiv cs.AI 2003
Year: 2003

A new approach to the construction of general persistent polyhierarchical classifications is proposed. It is based on implicit description of category polyhierarchy by a generating polyhierarchy of classification criteria. Similarly to existing approaches, the classification categories are defined by logical functions encoded by attributive expressions. However, the generating hierarchy explicitly predefines domains of criteria applicability, and the semantics of relations between categories is invariant to changes in the universe composition, extending variety of criteria, and increasing their cardinalities. The generating polyhierarchy is an independent, compact, portable, and re-usable information structure serving as a template classification. It can be associated with one or more particular sets of objects, included in more general classifications as a standard component, or used as a prototype for more comprehensive classifications. The approach dramatically simplifies development and unplanned modifications of persistent hierarchical classifications compared with tree, DAG, and faceted schemes. It can be efficiently implemented in common DBMS, while considerably reducing amount of computer resources required for storage, maintenance, and use of complex polyhierarchies.
Benchmarking Optimization Software with Performance Profiles
Venue: arXiv cs.MS 2004
Year: 2004

We propose performance profiles-distribution functions for a performance metric-as a tool for benchmarking and comparing optimization software. We show that performance profiles combine the best features of other tools for performance evaluation.
Kolmogorov's Structure Functions and Model Selection
Venue: arXiv cs.CC 2004
Year: 2004

In 1974 Kolmogorov proposed a non-probabilistic approach to statistics and model selection. Let data be finite binary strings and models be finite sets of binary strings. Consider model classes consisting of models of given maximal (Kolmogorov) complexity. The ``structure function'' of the given data expresses the relation between the complexity level constraint on a model class and the least log-cardinality of a model in the class containing the data. We show that the structure function determines all stochastic properties of the data: for every constrained model class it determines the individual best-fitting model in the class irrespective of whether the ``true'' model is in the model class considered or not. In this setting, this happens {\em with certainty}, rather than with high probability as is in the classical case. We precisely quantify the goodness-of-fit of an individual model with respect to individual data. We show that--within the obvious constraints--every graph is realized by the structure function of some data. We determine the (un)computability properties of the various functions contemplated and of the ``algorithmic minimal sufficient statistic.''
PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation
Venue: arXiv cs.CC 2004
Year: 2004

We present a nondeterministic model of computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph model can be manipulated in order to reverse the direction of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove this result in a variety of special cases including planar graphs and highly restricted vertex configurations, some of which correspond to a kind of passive constraint logic. Our framework is inspired by (and indeed a generalization of) the ``Generalized Rush Hour Logic'' developed by Flake and Baum. We illustrate the importance of our model of computation by giving simple reductions to show that several motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to be all dominoes (1x2 blocks) and the goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush Hour puzzles are PSPACE-complete, of which we also give a simpler proof. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete, by showing that it is PSPACE-complete even if no barriers are allowed.
Quasi-Optimal Arithmetic for Quaternion Polynomials
Venue: arXiv cs.SC 2004
Year: 2004

Fast algorithms for arithmetic on real or complex polynomials are well-known and have proven to be not only asymptotically efficient but also very practical. Based on Fast Fourier Transform (FFT), they for instance multiply two polynomials of degree up to N or multi-evaluate one at N points simultaneously within quasi-linear time O(N.polylog N). An extension to (and in fact the mere definition of) polynomials over the skew-field H of quaternions is promising but still missing. The present work proposes three such definitions which in the commutative case coincide but for H turn out to differ, each one satisfying some desirable properties while lacking others. For each notion we devise algorithms for according arithmetic; these are quasi-optimal in that their running times match lower complexity bounds up to polylogarithmic factors.
The one-round Voronoi game replayed
Venue: arXiv cs.CG 2004
Year: 2004

We consider the one-round Voronoi game, where player one (``White'', called ``Wilma'') places a set of n points in a rectangular area of aspect ratio r <=1, followed by the second player (``Black'', called ``Barney''), who places the same number of points. Each player wins the fraction of the board closest to one of his points, and the goal is to win more than half of the total area. This problem has been studied by Cheong et al., who showed that for large enough $n$ and r=1, Barney has a strategy that guarantees a fraction of 1/2+a, for some small fixed a. We resolve a number of open problems raised by that paper. In particular, we give a precise characterization of the outcome of the game for optimal play: We show that Barney has a winning strategy for n>2 and r>sqrt{2}/n, and for n=2 and r>sqrt{3}/2. Wilma wins in all remaining cases, i.e., for n>=3 and r<=sqrt{2}/n, for n=2 and r<=sqrt{3}/2, and for n=1. We also discuss complexity aspects of the game on more general boards, by proving that for a polygon with holes, it is NP-hard to maximize the area Barney can win against a given set of points by Wilma.
Deciding regular grammar logics with converse through first-order logic
Venue: arXiv cs.LO 2004
Year: 2004

We provide a simple translation of the satisfiability problem for regular grammar logics with converse into GF2, which is the intersection of the guarded fragment and the 2-variable fragment of first-order logic. This translation is theoretically interesting because it translates modal logics with certain frame conditions into first-order logic, without explicitly expressing the frame conditions. A consequence of the translation is that the general satisfiability problem for regular grammar logics with converse is in EXPTIME. This extends a previous result of the first author for grammar logics without converse. Using the same method, we show how some other modal logics can be naturally translated into GF2, including nominal tense logics and intuitionistic logic. In our view, the results in this paper show that the natural first-order fragment corresponding to regular grammar logics is simply GF2 without extra machinery such as fixed point-operators.
Optimal Adaptive Algorithms for Finding the Nearest and Farthest Point on a Parametric Black-Box Curve
Venue: arXiv cs.CG 2004
Year: 2004

We consider a general model for representing and manipulating parametric curves, in which a curve is specified by a black box mapping a parameter value between 0 and 1 to a point in Euclidean d-space. In this model, we consider the nearest-point-on-curve and farthest-point-on-curve problems: given a curve C and a point p, find a point on C nearest to p or farthest from p. In the general black-box model, no algorithm can solve these problems. Assuming a known bound on the speed of the curve (a Lipschitz condition), the answer can be estimated up to an additive error of epsilon using O(1/epsilon) samples, and this bound is tight in the worst case. However, many instances can be solved with substantially fewer samples, and we give algorithms that adapt to the inherent difficulty of the particular instance, up to a logarithmic factor. More precisely, if OPT(C,p,epsilon) is the minimum number of samples of C that every correct algorithm must perform to achieve tolerance epsilon, then our algorithm performs O(OPT(C,p,epsilon) log (epsilon^(-1)/OPT(C,p,epsilon))) samples. Furthermore, any algorithm requires Omega(k log (epsilon^(-1)/k)) samples for some instance C' with OPT(C',p,epsilon) = k; except that, for the nearest-point-on-curve problem when the distance between C and p is less than epsilon, OPT is 1 but the upper and lower bounds on the number of samples are both Theta(1/epsilon). When bounds on relative error are desired, we give algorithms that perform O(OPT log (2+(1+epsilon^(-1)) m^(-1)/OPT)) samples (where m is the exact minimum or maximum distance from p to C) and prove that Omega(OPT log (1/epsilon)) samples are necessary on some problem instances.