OpenRaiser/Intern-Atlas huggingface dataset:
Examples of Models of the Asynchronous Circuits
Venue: arXiv cs.LO 2004
Year: 2004

We define the delays of a circuit, as well as the properties of determinism, order, time invariance, constancy, symmetry and the serial connection.
Spam filter analysis
Venue: arXiv cs.CR 2004
Year: 2004

Unsolicited bulk email (aka. spam) is a major problem on the Internet. To counter spam, several techniques, ranging from spam filters to mail protocol extensions like hashcash, have been proposed. In this paper we investigate the effectiveness of several spam filtering techniques and technologies. Our analysis was performed by simulating email traffic under different conditions. We show that genetic algorithm based spam filters perform best at server level and naive Bayesian filters are the most appropriate for filtering at user level.
Nested Intervals Tree Encoding with Continued Fractions
Venue: arXiv cs.DB 2004
Year: 2004

We introduce a new variation of Tree Encoding with Nested Intervals, find connections with Materialized Path, and suggest a method for moving parts of the hierarchy.
Light types for polynomial time computation in lambda-calculus
Venue: arXiv cs.LO 2004
Year: 2004

We propose a new type system for lambda-calculus ensuring that well-typed programs can be executed in polynomial time: Dual light affine logic (DLAL). DLAL has a simple type language with a linear and an intuitionistic type arrow, and one modality. It corresponds to a fragment of Light affine logic (LAL). We show that contrarily to LAL, DLAL ensures good properties on lambda-terms: subject reduction is satisfied and a well-typed term admits a polynomial bound on the reduction by any strategy. We establish that as LAL, DLAL allows to represent all polytime functions. Finally we give a type inference procedure for propositional DLAL.
A Correlation-Based Distance
Venue: arXiv cs.IR 2004
Year: 2004

In this short technical report, we define on the sample space R^D a distance between data points which depends on their correlation. We also derive an expression for the center of mass of a set of points with respect to this distance.
Algebraic Curves in Parallel Coordinates - Avoiding the "Over-Plotting" Problem
Venue: arXiv cs.OH 2004
Year: 2004

${\cal U}$ntil now the representation (i.e. plotting) of curve in Parallel Coordinates is constructed from the point $\leftrightarrow$ line duality. The result is a ``line-curve'' which is seen as the envelope of it's tangents. Usually this gives an unclear image and is at the heart of the ``over-plotting'' problem; a barrier in the effective use of Parallel Coordinates. This problem is overcome by a transformation which provides directly the ``point-curve'' representation of a curve. Earlier this was applied to conics and their generalizations. Here the representation, also called dual, is extended to all planar algebraic curves. Specifically, it is shown that the dual of an algebraic curve of degree $n$ is an algebraic of degree at most $n(n - 1)$ in the absence of singular points. The result that conics map into conics follows as an easy special case. An algorithm, based on algebraic geometry using resultants and homogeneous polynomials, is obtained which constructs the dual image of the curve. This approach has potential generalizations to multi-dimensional algebraic surfaces and their approximation. The ``trade-off'' price then for obtaining {\em planar} representation of multidimensional algebraic curves and hyper-surfaces is the higher degree of the image's boundary which is also an algebraic curve in $\|$-coords.
Distribution of Mutual Information from Complete and Incomplete Data
Venue: arXiv cs.LG 2004
Year: 2004

Mutual information is widely used, in a descriptive way, to measure the stochastic dependence of categorical random variables. In order to address questions such as the reliability of the descriptive value, one must consider sample-to-population inferential approaches. This paper deals with the posterior distribution of mutual information, as obtained in a Bayesian framework by a second-order Dirichlet prior distribution. The exact analytical expression for the mean, and analytical approximations for the variance, skewness and kurtosis are derived. These approximations have a guaranteed accuracy level of the order O(1/n^3), where n is the sample size. Leading order approximations for the mean and the variance are derived in the case of incomplete samples. The derived analytical expressions allow the distribution of mutual information to be approximated reliably and quickly. In fact, the derived expressions can be computed with the same order of complexity needed for descriptive mutual information. This makes the distribution of mutual information become a concrete alternative to descriptive mutual information in many applications which would benefit from moving to the inductive side. Some of these prospective applications are discussed, and one of them, namely feature selection, is shown to perform significantly better when inductive mutual information is used.
Performance Evaluation of Packet-to-Cell Segmentation Schemes in Input Buffered Packet Switches
Venue: arXiv cs.NI 2004
Year: 2004

Most input buffered packet switches internally segment variable-length packets into fixed-length cells. The last cell in a segmented packet will contain overhead bytes if the packet length is not evenly divisible by the cell length. Switch speed-up is used to compensate for this overhead. In this paper, we develop an analytical model of a single-server queue where an input stream of packets is segmented into cells for service. Analytical models are developed for M/M/1, M/H2/1, and M/E2/1 queues with a discretized (or quantized) service time. These models and simulation using real packet traces are used to evaluate the effect of speed-up on mean queue length. We propose and evaluate a new method of segmenting a packet trailer and subsequent packet header into a single cell. This cell merging method reduces the required speed-up. No changes to switch-matrix scheduling algorithms are needed. Simulation with a packet trace shows a reduction in the needed speed-up for an iSLIP scheduled input buffered switch.
Where Fail-Safe Default Logics Fail
Venue: arXiv cs.AI 2004
Year: 2004

Reiter's original definition of default logic allows for the application of a default that contradicts a previously applied one. We call failure this condition. The possibility of generating failures has been in the past considered as a semantical problem, and variants have been proposed to solve it. We show that it is instead a computational feature that is needed to encode some domains into default logic.
Stream cipher based on quasigroup string transformations in $Z_p^*$
Venue: arXiv cs.CR 2004
Year: 2004

In this paper we design a stream cipher that uses the algebraic structure of the multiplicative group $\bbbz_p^*$ (where p is a big prime number used in ElGamal algorithm), by defining a quasigroup of order $p-1$ and by doing quasigroup string transformations. The cryptographical strength of the proposed stream cipher is based on the fact that breaking it would be at least as hard as solving systems of multivariate polynomial equations modulo big prime number $p$ which is NP-hard problem and there are no known fast randomized or deterministic algorithms for solving it. Unlikely the speed of known ciphers that work in $\bbbz_p^*$ for big prime numbers $p$, the speed of this stream cipher both in encryption and decryption phase is comparable with the fastest symmetric-key stream ciphers.
Mathematical Analysis of Multi-Agent Systems
Venue: arXiv cs.RO 2004
Year: 2004

We review existing approaches to mathematical modeling and analysis of multi-agent systems in which complex collective behavior arises out of local interactions between many simple agents. Though the behavior of an individual agent can be considered to be stochastic and unpredictable, the collective behavior of such systems can have a simple probabilistic description. We show that a class of mathematical models that describe the dynamics of collective behavior of multi-agent systems can be written down from the details of the individual agent controller. The models are valid for Markov or memoryless agents, in which each agents future state depends only on its present state and not any of the past states. We illustrate the approach by analyzing in detail applications from the robotics domain: collaboration and foraging in groups of robots.
The Gridbus Toolkit for Service Oriented Grid and Utility Computing: An Overview and Status Report
Venue: arXiv cs.DC 2004
Year: 2004

Grids aim at exploiting synergies that result from cooperation of autonomous distributed entities. The synergies that result from grid cooperation include the sharing, exchange, selection, and aggregation of geographically distributed resources such as computers, data bases, software, and scientific instruments for solving large-scale problems in science, engineering, and commerce. For this cooperation to be sustainable, participants need to have economic incentive. Therefore, "incentive" mechanisms should be considered as one of key design parameters of Grid architectures. In this article, we present an overview and status of an open source Grid toolkit, called Gridbus, whose architecture is fundamentally driven by the requirements of Grid economy. Gridbus technologies provide services for both computational and data grids that power the emerging eScience and eBusiness applications.
The Random Buffer Tree : A Randomized Technique for I/O-efficient Algorithms
Venue: arXiv cs.DS 2004
Year: 2004

In this paper, we present a probabilistic self-balancing dictionary data structure for massive data sets, and prove expected amortized I/O-optimal bounds on the dictionary operations. We show how to use the structure as an I/O-optimal priority queue. The data structure, which we call as the random buffer tree, abstracts the properties of the random treap and the buffer tree and has the same expected I/O-bounds as the buffer tree.
Algorithms for Estimating Information Distance with Application to Bioinformatics and Linguistics
Venue: arXiv cs.CC 2004
Year: 2004

After reviewing unnormalized and normalized information distances based on incomputable notions of Kolmogorov complexity, we discuss how Kolmogorov complexity can be approximated by data compression algorithms. We argue that optimal algorithms for data compression with side information can be successfully used to approximate the normalized distance. Next, we discuss an alternative information distance, which is based on relative entropy rate (also known as Kullback-Leibler divergence), and compression-based algorithms for its estimation. Based on available biological and linguistic data, we arrive to unexpected conclusion that in Bioinformatics and Computational Linguistics this alternative distance is more relevant and important than the ones based on Kolmogorov complexity.
Speculation on graph computation architectures and computing via synchronization
Venue: arXiv cs.NE 2004
Year: 2004

A speculative overview of a future topic of research. The paper is a collection of ideas concerning two related areas: 1) Graph computation machines ("computing with graphs"). This is the class of models of computation in which the state of the computation is represented as a graph or network. 2) Arc-based neural networks, which store information not as activation in the nodes, but rather by adding and deleting arcs. Sometimes the arcs may be interpreted as synchronization. Warnings to readers: this is not the sort of thing that one might submit to a journal or conference. No proofs are presented. The presentation is informal, and written at an introductory level. You'll probably want to wait for a more concise presentation.
Visualising the structure of architectural open spaces based on shape analysis
Venue: arXiv cs.CV 2004
Year: 2004

This paper proposes the application of some well known two-dimensional geometrical shape descriptors for the visualisation of the structure of architectural open spaces. The paper demonstrates the use of visibility measures such as distance to obstacles and amount of visible space to calculate shape descriptors such as convexity and skeleton of the open space. The aim of the paper is to indicate a simple, objective and quantifiable approach to understand the structure of open spaces otherwise impossible due to the complex construction of built structures.
Intrusion Detection Systems Using Adaptive Regression Splines
Venue: arXiv cs.AI 2004
Year: 2004

Past few years have witnessed a growing recognition of intelligent techniques for the construction of efficient and reliable intrusion detection systems. Due to increasing incidents of cyber attacks, building effective intrusion detection systems (IDS) are essential for protecting information systems security, and yet it remains an elusive goal and a great challenge. In this paper, we report a performance analysis between Multivariate Adaptive Regression Splines (MARS), neural networks and support vector machines. The MARS procedure builds flexible regression models by fitting separate splines to distinct intervals of the predictor variables. A brief comparison of different neural network learning algorithms is also given.
Modeling Chaotic Behavior of Stock Indices Using Intelligent Paradigms
Venue: arXiv cs.AI 2004
Year: 2004

The use of intelligent systems for stock market predictions has been widely established. In this paper, we investigate how the seemingly chaotic behavior of stock markets could be well represented using several connectionist paradigms and soft computing techniques. To demonstrate the different techniques, we considered Nasdaq-100 index of Nasdaq Stock MarketS and the S&P CNX NIFTY stock index. We analyzed 7 year's Nasdaq 100 main index values and 4 year's NIFTY index values. This paper investigates the development of a reliable and efficient technique to model the seemingly chaotic behavior of stock markets. We considered an artificial neural network trained using Levenberg-Marquardt algorithm, Support Vector Machine (SVM), Takagi-Sugeno neuro-fuzzy model and a Difference Boosting Neural Network (DBNN). This paper briefly explains how the different connectionist paradigms could be formulated using different learning methods and then investigates whether they can provide the required level of performance, which are sufficiently good and robust so as to provide a reliable forecast model for stock market indices. Experiment results reveal that all the connectionist paradigms considered could represent the stock indices behavior very accurately.
A proof of Alon's second eigenvalue conjecture and related problems
Venue: arXiv cs.DM 2004
Year: 2004

In this paper we show the following conjecture of Noga Alon. Fix a positive integer d>2 and real epsilon > 0; consider the probability that a random d-regular graph on n vertices has the second eigenvalue of its adjacency matrix greater than 2 sqrt(d-1) + epsilon; then this probability goes to zero as n tends to infinity. We prove the conjecture for a number of notions of random d-regular graph, including models for d odd. We also estimate the aforementioned probability more precisely, showing in many cases and models (but not all) that it decays like a polynomial in 1/n.
Computational Geometry Column 45
Venue: arXiv cs.CG 2004
Year: 2004

The algorithm of Edelsbrunner for surface reconstruction by ``wrapping'' a set of points in R^3 is described.
Supervisory Control of Fuzzy Discrete Event Systems
Venue: arXiv cs.DM 2004
Year: 2004

In order to cope with situations in which a plant's dynamics are not precisely known, we consider the problem of supervisory control for a class of discrete event systems modelled by fuzzy automata. The behavior of such discrete event systems is described by fuzzy languages; the supervisors are event feedback and can disable only controllable events with any degree. The concept of discrete event system controllability is thus extended by incorporating fuzziness. In this new sense, we present a necessary and sufficient condition for a fuzzy language to be controllable. We also study the supremal controllable fuzzy sublanguage and the infimal controllable fuzzy superlanguage when a given pre-specified desired fuzzy language is uncontrollable. Our framework generalizes that of Ramadge-Wonham and reduces to Ramadge-Wonham framework when membership grades in all fuzzy languages must be either 0 or 1. The theoretical development is accompanied by illustrative numerical examples.
Modular technology of developing of the problem-oriented extensions of a CAD system of reconstruction of the plant
Venue: arXiv cs.CE 2004
Year: 2004

The modular technology of creation of the problem-oriented extensions of a CAD system is described, which was realised in a system TechnoCAD GlassX for designing of reconstruction of the plants. The modularity of the technology is expressed in storage of all parameters of the design in one element of the drawing - modulus, with automatic generation of a geometrical part of the modulus from these parameters. The common principles of the system organization of extensions developing are described: separation of the part of the design to automize in this extension, architecture of parameters in the form of the lists of objects with their properties and links to another objects, separation of common and special operations, stages of the developing, boundaries of applicability of technology.
Export Behaviour Modeling Using EvoNF Approach
Venue: arXiv cs.AI 2004
Year: 2004

The academic literature suggests that the extent of exporting by multinational corporation subsidiaries (MCS) depends on their product manufactured, resources, tax protection, customers and markets, involvement strategy, financial independence and suppliers' relationship with a multinational corporation (MNC). The aim of this paper is to model the complex export pattern behaviour using a Takagi-Sugeno fuzzy inference system in order to determine the actual volume of MCS export output (sales exported). The proposed fuzzy inference system is optimised by using neural network learning and evolutionary computation. Empirical results clearly show that the proposed approach could model the export behaviour reasonable well compared to a direct neural network approach.
Short Term Load Forecasting Models in Czech Republic Using Soft Computing Paradigms
Venue: arXiv cs.AI 2004
Year: 2004

This paper presents a comparative study of six soft computing models namely multilayer perceptron networks, Elman recurrent neural network, radial basis function network, Hopfield model, fuzzy inference system and hybrid fuzzy neural network for the hourly electricity demand forecast of Czech Republic. The soft computing models were trained and tested using the actual hourly load data for seven years. A comparison of the proposed techniques is presented for predicting 2 day ahead demands for electricity. Simulation results indicate that hybrid fuzzy neural network and radial basis function networks are the best candidates for the analysis and forecasting of electricity demand.
Modular technology of developing of the extensions of a CAD system. The axonometric piping diagrams. Common and special operations
Venue: arXiv cs.CE 2004
Year: 2004

Applying the modular technology of developing of the problem-oriented extensions of a CAD system to a problem of automation of creating of the axonometric piping diagrams on an example of the program system TechnoCAD GlassX is described. The features of realization of common operations, composition and realization of special operations of a designing of the schemas of the special technological pipe lines, systems of a water line and water drain, heating, heat supply, ventilating, air conditioning are reviewed.
Let's Get Ready to Rumble: Crossover Versus Mutation Head to Head
Venue: arXiv cs.NE 2004
Year: 2004

This paper analyzes the relative advantages between crossover and mutation on a class of deterministic and stochastic additively separable problems. This study assumes that the recombination and mutation operators have the knowledge of the building blocks (BBs) and effectively exchange or search among competing BBs. Facetwise models of convergence time and population sizing have been used to determine the scalability of each algorithm. The analysis shows that for additively separable deterministic problems, the BB-wise mutation is more efficient than crossover, while the crossover outperforms the mutation on additively separable problems perturbed with additive Gaussian noise. The results show that the speed-up of using BB-wise mutation on deterministic problems is O(k^{0.5}logm), where k is the BB size, and m is the number of BBs. Likewise, the speed-up of using crossover on stochastic problems with fixed noise variance is O(mk^{0.5}log m).
Generative Programming of Graphical User Interfaces
Venue: arXiv cs.HC 2004
Year: 2004

Generative Programming (GP) is a computing paradigm allowing automatic creation of entire software families utilizing the configuration of elementary and reusable components. GP can be projected on different technologies, e.g. C++-templates, Java-Beans, Aspect-Oriented Programming (AOP), or Frame technology. This paper focuses on Frame Technology, which aids the possible implementation and completion of software components. The purpose of this paper is to introduce the GP paradigm in the area of GUI application generation. It demonstrates how automatically customized executable applications with GUI parts can be generated from an abstract specification.
On the Expressive Power of First-Order Boolean Functions in PCF
Venue: arXiv cs.PL 2004
Year: 2004

Recent results of Bucciarelli show that the semilattice of degrees of parallelism of first-order boolean functions in PCF has both infinite chains and infinite antichains. By considering a simple subclass of Sieber's sequentiality relations, we identify levels in the semilattice and derive inexpressibility results concerning functions on different levels. This allows us to further explore the structure of the semilattice of degrees of parallelism: we identify semilattices characterized by simple level properties, and show the existence of new infinite hierarchies which are in a certain sense natural with respect to the levels.
Convex Hull of Planar H-Polyhedra
Venue: arXiv cs.CG 2004
Year: 2004

Suppose $<A_i, \vec{c}_i>$ are planar (convex) H-polyhedra, that is, $A_i \in \mathbb{R}^{n_i \times 2}$ and $\vec{c}_i \in \mathbb{R}^{n_i}$. Let $P_i = \{\vec{x} \in \mathbb{R}^2 \mid A_i\vec{x} \leq \vec{c}_i \}$ and $n = n_1 + n_2$. We present an $O(n \log n)$ algorithm for calculating an H-polyhedron $<A, \vec{c}>$ with the smallest $P = \{\vec{x} \in \mathbb{R}^2 \mid A\vec{x} \leq \vec{c} \}$ such that $P_1 \cup P_2 \subseteq P$.
Computerized Face Detection and Recognition
Venue: arXiv cs.CV 2004
Year: 2004

This publication presents methods for face detection, analysis and recognition: fast normalized cross-correlation (fast correlation coefficient) between multiple templates based face pre-detection method, method for detection of exact face contour based on snakes and Generalized Gradient Vector Flow field, method for combining recognition algorithms based on Cumulative Match Characteristics in order to increase recognition speed and accuracy, and face recognition method based on Principal Component Analysis of the Wavelet Packet Decomposition allowing to use PCA - based recognition method with large number of training images. For all the methods are presented experimental results and comparisons of speed and accuracy with large face databases.