OpenRaiser/Intern-Atlas huggingface dataset:
On Orthogonality of Latin Squares
Venue: arXiv cs.DM 2006
Year: 2006

An arrangement of s elements in s rows and s columns, such that no element repeats more than once in each row and each column is called a Latin square of order s. If two Latin squares of the same order superimposed one on the other and in the resultant array if each ordered pair occurs once and only once then they are called othogonal Latin Squares. A frequency square is an nxn matrix, such that each element from the list of n elements, occurs t times in each row and in each column. These two concepts lead to a new third concept called as t orthogonal latin squares, where from a set of m orthogonal Latin squares, if t orthogonal Latin squares are superimposed and each ordered t tuple in the resultant array occurs once and only once then it is t othogonal Latin square. In this paper it is proposed to construct such t othogonal latin squares
On Hadamard Conjecture
Venue: arXiv cs.DM 2006
Year: 2006

In this note, while giving an overview of the state of art of the well known Hadamard conjecture, which is more than a century old and now it has been established by using the methods given in the two papers by Mohan et al [6,7].
A New Fault-Tolerant M-network and its Analysis
Venue: arXiv cs.IT 2006
Year: 2006

This paper introduces a new class of efficient inter connection networks called as M-graphs for large multi-processor systems.The concept of M-matrix and M-graph is an extension of Mn-matrices and Mn-graphs.We analyze these M-graphs regarding their suitability for large multi-processor systems. An(p,N) M-graph consists of N nodes, where p is the degree of each node.The topology is found to be having many attractive features prominent among them is the capability of maximal fault-tolerance, high density and constant diameter.It is found that these combinatorial structures exibit some properties like symmetry,and an inter-relation with the nodes, and degree of the concerned graph, which can be utilized for the purposes of inter connected networks.But many of the properties of these mathematical and graphical structures still remained unexplored and the present aim of the paper is to study and analyze some of the properties of these M-graphs and explore their application in networks and multi-processor systems.
Biologically Inspired Hierarchical Model for Feature Extraction and Localization
Venue: arXiv cs.CV 2006
Year: 2006

Feature extraction and matching are among central problems of computer vision. It is inefficent to search features over all locations and scales. Neurophysiological evidence shows that to locate objects in a digital image the human visual system employs visual attention to a specific object while ignoring others. The brain also has a mechanism to search from coarse to fine. In this paper, we present a feature extractor and an associated hierarchical searching model to simulate such processes. With the hierarchical representation of the object, coarse scanning is done through the matching of the larger scale and precise localization is conducted through the matching of the smaller scale. Experimental results justify the proposed model in its effectiveness and efficiency to localize features.
Distributed Metadata with the AMGA Metadata Catalog
Venue: arXiv cs.DC 2006
Year: 2006

Catalog Services play a vital role on Data Grids by allowing users and applications to discover and locate the data needed. On large Data Grids, with hundreds of geographically distributed sites, centralized Catalog Services do not provide the required scalability, performance or fault-tolerance. In this article, we start by presenting and discussing the general requirements on Grid Catalogs of applications being developed by the EGEE user community. This provides the motivation for the second part of the article, where we present the replication and distribution mechanisms we have designed and implemented into the AMGA Metadata Catalog, which is part of the gLite software stack being developed for the EGEE project. Implementing these mechanisms in the catalog itself has the advantages of not requiring any special support from the relational database back-end, of being database independent, and of allowing tailoring the mechanisms to the specific requirements and characteristics of Metadata Catalogs.
Complexity and Philosophy
Venue: arXiv cs.CC 2006
Year: 2006

The science of complexity is based on a new way of thinking that stands in sharp contrast to the philosophy underlying Newtonian science, which is based on reductionism, determinism, and objective knowledge. This paper reviews the historical development of this new world view, focusing on its philosophical foundations. Determinism was challenged by quantum mechanics and chaos theory. Systems theory replaced reductionism by a scientifically based holism. Cybernetics and postmodern social science showed that knowledge is intrinsically subjective. These developments are being integrated under the header of "complexity science". Its central paradigm is the multi-agent system. Agents are intrinsically subjective and uncertain about their environment and future, but out of their local interactions, a global organization emerges. Although different philosophers, and in particular the postmodernists, have voiced similar ideas, the paradigm of complexity still needs to be fully assimilated by philosophy. This will throw a new light on old philosophical issues such as relativism, ethics and the role of the subject.
The emergence of knowledge exchange: an agent-based model of a software market
Venue: arXiv cs.MA 2006
Year: 2006

We investigate knowledge exchange among commercial organisations, the rationale behind it and its effects on the market. Knowledge exchange is known to be beneficial for industry, but in order to explain it, authors have used high level concepts like network effects, reputation and trust. We attempt to formalise a plausible and elegant explanation of how and why companies adopt information exchange and why it benefits the market as a whole when this happens. This explanation is based on a multi-agent model that simulates a market of software providers. Even though the model does not include any high-level concepts, information exchange naturally emerges during simulations as a successful profitable behaviour. The conclusions reached by this agent-based analysis are twofold: (1) A straightforward set of assumptions is enough to give rise to exchange in a software market. (2) Knowledge exchange is shown to increase the efficiency of the market.
Optimum Asymptotic Multiuser Efficiency of Pseudo-Orthogonal Randomly Spread CDMA
Venue: arXiv cs.IT 2006
Year: 2006

A $K$-user pseudo-orthogonal (PO) randomly spread CDMA system, equivalent to transmission over a subset of $K'\leq K$ single-user Gaussian channels, is introduced. The high signal-to-noise ratio performance of the PO-CDMA is analyzed by rigorously deriving its asymptotic multiuser efficiency (AME) in the large system limit. Interestingly, the $K'$-optimized PO-CDMA transceiver scheme yields an AME which is practically equal to 1 for system loads smaller than 0.1 and lower bounded by 1/4 for increasing loads. As opposed to the vanishing efficiency of linear multiuser detectors, the derived efficiency is comparable to the ultimate CDMA efficiency achieved for the intractable optimal multiuser detector.
Optimal and Suboptimal Finger Selection Algorithms for MMSE Rake Receivers in Impulse Radio UWB Systems
Venue: arXiv cs.IT 2006
Year: 2006

The problem of choosing the optimal multipath components to be employed at a minimum mean square error (MMSE) selective Rake receiver is considered for an impulse radio ultra-wideband system. First, the optimal finger selection problem is formulated as an integer programming problem with a non-convex objective function. Then, the objective function is approximated by a convex function and the integer programming problem is solved by means of constraint relaxation techniques. The proposed algorithms are suboptimal due to the approximate objective function and the constraint relaxation steps. However, they perform better than the conventional finger selection algorithm, which is suboptimal since it ignores the correlation between multipath components, and they can get quite close to the optimal scheme that cannot be implemented in practice due to its complexity. In addition to the convex relaxation techniques, a genetic algorithm (GA) based approach is proposed, which does not need any approximations or integer relaxations. This iterative algorithm is based on the direct evaluation of the objective function, and can achieve near-optimal performance with a reasonable number of iterations. Simulation results are presented to compare the performance of the proposed finger selection algorithms with that of the conventional and the optimal schemes.
Myopic Coding in Wireless Networks
Venue: arXiv cs.IT 2006
Year: 2006

We investigate the achievable rate of data transmission from sources to sinks through a multiple-relay network. We study achievable rates for omniscient coding, in which all nodes are considered in the coding design at each node. We find that, when maximizing the achievable rate, not all nodes need to ``cooperate'' with all other nodes in terms of coding and decoding. This leads us to suggest a constrained network, whereby each node only considers a few neighboring nodes during encoding and decoding. We term this myopic coding and calculate achievable rates for myopic coding. We show by examples that, when nodes transmit at low SNR, these rates are close to that achievable by omniscient coding, when the network is unconstrained . This suggests that a myopic view of the network might be as good as a global view. In addition, myopic coding has the practical advantage of being more robust to topology changes. It also mitigates the high computational complexity and large buffer/memory requirements of omniscient coding schemes.
Fast computation of power series solutions of systems of differential equations
Venue: arXiv cs.SC 2006
Year: 2006

We propose new algorithms for the computation of the first N terms of a vector (resp. a basis) of power series solutions of a linear system of differential equations at an ordinary point, using a number of arithmetic operations which is quasi-linear with respect to N. Similar results are also given in the non-linear case. This extends previous results obtained by Brent and Kung for scalar differential equations of order one and two.
HCI and Educational Metrics as Tools for VLE Evaluation
Venue: arXiv cs.HC 2006
Year: 2006

The general set of HCI and Educational principles are considered and a classification system constructed. A frequency analysis of principles is used to obtain the most significant set. Metrics are devised to provide objective measures of these principles and a consistent testing regime devised. These principles are used to analyse Blackboard and Moodle.
On the Shannon Covers of Certain Irreducible Constrained Systems of Finite Type
Venue: arXiv cs.IT 2006
Year: 2006

A construction of Crochemore, Mignosi and Restivo in the automata theory literature gives a presentation of a finite-type constrained system (FTCS) that is deterministic and has a relatively small number of states. This construction is thus a good starting point for determining the minimal deterministic presentation, known as the Shannon cover, of an FTCS. We analyze in detail the Crochemore-Mignosi-Restivo (CMR) construction in the case when the list of forbidden words defining the FTCS is of size at most two. We show that if the FTCS is irreducible, then an irreducible presentation for the system can be easily obtained by deleting a prescribed few states from the CMR presentation. By studying the follower sets of the states in this irreducible presentation, we are able to explicitly determine the Shannon cover in some cases. In particular, our results show that the CMR construction directly yields the Shannon cover in the case of an irreducible FTCS with exactly one forbidden word, but this is not in general the case for FTCS's with two forbidden words.
Analysis of Dynamic Task Allocation in Multi-Robot Systems
Venue: arXiv cs.RO 2006
Year: 2006

Dynamic task allocation is an essential requirement for multi-robot systems operating in unknown dynamic environments. It allows robots to change their behavior in response to environmental changes or actions of other robots in order to improve overall system performance. Emergent coordination algorithms for task allocation that use only local sensing and no direct communication between robots are attractive because they are robust and scalable. However, a lack of formal analysis tools makes emergent coordination algorithms difficult to design. In this paper we present a mathematical model of a general dynamic task allocation mechanism. Robots using this mechanism have to choose between two types of task, and the goal is to achieve a desired task division in the absence of explicit communication and global knowledge. Robots estimate the state of the environment from repeated local observations and decide which task to choose based on these observations. We model the robots and observations as stochastic processes and study the dynamics of the collective behavior. Specifically, we analyze the effect that the number of observations and the choice of the decision function have on the performance of the system. The mathematical models are validated in a multi-robot multi-foraging scenario. The model's predictions agree very closely with experimental results from sensor-based simulations.
A Hybrid Quantum Encoding Algorithm of Vector Quantization for Image Compression
Venue: arXiv cs.MM 2006
Year: 2006

Many classical encoding algorithms of Vector Quantization (VQ) of image compression that can obtain global optimal solution have computational complexity O(N). A pure quantum VQ encoding algorithm with probability of success near 100% has been proposed, that performs operations 45sqrt(N) times approximately. In this paper, a hybrid quantum VQ encoding algorithm between classical method and quantum algorithm is presented. The number of its operations is less than sqrt(N) for most images, and it is more efficient than the pure quantum algorithm. Key Words: Vector Quantization, Grover's Algorithm, Image Compression, Quantum Algorithm
Cooperative Relay Broadcast Channels
Venue: arXiv cs.IT 2006
Year: 2006

The capacity regions are investigated for two relay broadcast channels (RBCs), where relay links are incorporated into standard two-user broadcast channels to support user cooperation. In the first channel, the Partially Cooperative Relay Broadcast Channel, only one user in the system can act as a relay and transmit to the other user through a relay link. An achievable rate region is derived based on the relay using the decode-and-forward scheme. An outer bound on the capacity region is derived and is shown to be tighter than the cut-set bound. For the special case where the Partially Cooperative RBC is degraded, the achievable rate region is shown to be tight and provides the capacity region. Gaussian Partially Cooperative RBCs and Partially Cooperative RBCs with feedback are further studied. In the second channel model being studied in the paper, the Fully Cooperative Relay Broadcast Channel, both users can act as relay nodes and transmit to each other through relay links. This is a more general model than the Partially Cooperative RBC. All the results for Partially Cooperative RBCs are correspondingly generalized to the Fully Cooperative RBCs. It is further shown that the AWGN Fully Cooperative RBC has a larger achievable rate region than the AWGN Partially Cooperative RBC. The results illustrate that relaying and user cooperation are powerful techniques in improving the capacity of broadcast channels.
Applied MVC Patterns. A pattern language
Venue: arXiv cs.SE 2006
Year: 2006

How to get advantages of MVC model without making applications unnecessarily complex? The full-featured MVC implementation is on the top end of ladder of complexity. The other end is meant for simple cases that do not call for such complex designs, however still in need of the advantages of MVC patterns, such as ability to change the look-and-feel. This paper presents patterns of MVC implementation that help to benefit from the paradigm and keep the right balance between flexibility and implementation complexity.
The Gaussian Multiple Access Wire-Tap Channel with Collective Secrecy Constraints
Venue: arXiv cs.IT 2006
Year: 2006

We consider the Gaussian Multiple Access Wire-Tap Channel (GMAC-WT). In this scenario, multiple users communicate with an intended receiver in the presence of an intelligent and informed wire-tapper who receives a degraded version of the signal at the receiver. We define a suitable security measure for this multi-access environment. We derive an outer bound for the rate region such that secrecy to some pre-determined degree can be maintained. We also find, using Gaussian codebooks, an achievable such secrecy region. Gaussian codewords are shown to achieve the sum capacity outer bound, and the achievable region concides with the outer bound for Gaussian codewords, giving the capacity region when inputs are constrained to be Gaussian. We present numerical results showing the new rate region and compare it with that of the Gaussian Multiple-Access Channel (GMAC) with no secrecy constraints.
Strongly Almost Periodic Sequences under Finite Automata Mappings
Venue: arXiv cs.DM 2006
Year: 2006

The notion of almost periodicity nontrivially generalizes the notion of periodicity. Strongly almost periodic sequences (=uniformly recurrent infinite words) first appeared in the field of symbolic dynamics, but then turned out to be interesting in connection with computer science. The paper studies the class of eventually strongly almost periodic sequences (i. e., becoming strongly almost periodic after deleting some prefix). We prove that the property of eventual strong almost periodicity is preserved under the mappings done by finite automata and finite transducers. The class of almost periodic sequences includes the class of eventually strongly almost periodic sequences. We prove this inclusion to be strict.
On the Design of Agent-Based Systems using UML and Extensions
Venue: arXiv cs.AI 2006
Year: 2006

The Unified Software Development Process (USDP) and UML have been now generally accepted as the standard methodology and modeling language for developing Object-Oriented Systems. Although Agent-based Systems introduces new issues, we consider that USDP and UML can be used in an extended manner for modeling Agent-based Systems. The paper presents a methodology for designing agent-based systems and the specific models expressed in an UML-based notation corresponding to each phase of the software development process. UML was extended using the provided mechanism: stereotypes. Therefore, this approach can be managed with any CASE tool supporting UML. A Case Study, the development of a specific agent-based Student Evaluation System (SAS), is presented.
Mobile Agent Based Solutions for Knowledge Assessment in elearning Environments
Venue: arXiv cs.MA 2006
Year: 2006

E-learning is nowadays one of the most interesting of the "e- " domains available through the Internet. The main problem to create a Web-based, virtual environment is to model the traditional domain and to implement the model using the most suitable technologies. We analyzed the distance learning domain and investigated the possibility to implement some e-learning services using mobile agent technologies. This paper presents a model of the Student Assessment Service (SAS) and an agent-based framework developed to be used for implementing specific applications. A specific Student Assessment application that relies on the framework was developed.
Approximate Discrete Probability Distribution Representation using a Multi-Resolution Binary Tree
Venue: arXiv cs.AI 2006
Year: 2006

Computing and storing probabilities is a hard problem as soon as one has to deal with complex distributions over multiple random variables. The problem of efficient representation of probability distributions is central in term of computational efficiency in the field of probabilistic reasoning. The main problem arises when dealing with joint probability distributions over a set of random variables: they are always represented using huge probability arrays. In this paper, a new method based on binary-tree representation is introduced in order to store efficiently very large joint distributions. Our approach approximates any multidimensional joint distributions using an adaptive discretization of the space. We make the assumption that the lower is the probability mass of a particular region of feature space, the larger is the discretization step. This assumption leads to a very optimized representation in term of time and memory. The other advantages of our approach are the ability to refine dynamically the distribution every time it is needed leading to a more accurate representation of the probability distribution and to an anytime representation of the distribution.
A Chaotic Cipher Mmohocc and Its Randomness Evaluation
Venue: arXiv cs.CR 2006
Year: 2006

After a brief introduction to a new chaotic stream cipher Mmohocc which utilizes the fundamental chaos characteristics of mixing, unpredictability, and sensitivity to initial conditions, we conducted the randomness statistical tests against the keystreams generated by the cipher. Two batteries of most stringent randomness tests, namely the NIST Suite and the Diehard Suite, were performed. The results showed that the keystreams have successfully passed all the statistical tests. We conclude that Mmohocc can generate high-quality pseudorandom numbers from a statistical point of view.
The Complexity of Mean Flow Time Scheduling Problems with Release Times
Venue: arXiv cs.DS 2006
Year: 2006

We study the problem of preemptive scheduling n jobs with given release times on m identical parallel machines. The objective is to minimize the average flow time. We show that when all jobs have equal processing times then the problem can be solved in polynomial time using linear programming. Our algorithm can also be applied to the open-shop problem with release times and unit processing times. For the general case (when processing times are arbitrary), we show that the problem is unary NP-hard.
Caractéristiques arithmétiques des processeurs graphiques
Venue: arXiv cs.MS 2006
Year: 2006

Les unités graphiques (Graphic Processing Units- GPU) sont désormais des processeurs puissants et flexibles. Les dernières générations de GPU contiennent des unités programmables de traitement des sommets (vertex shader) et des pixels (pixel shader) supportant des opérations en virgule flottante sur 8, 16 ou 32 bits. La représentation flottante sur 32 bits correspond à la simple précision de la norme IEEE sur l'arithmétique en virgule flottante (IEEE-754). Les GPU sont bien adaptés aux applications avec un fort parallélisme de données. Cependant ils ne sont que peu utilisés en dehors des calculs graphiques (General Purpose computation on GPU -- GPGPU). Une des raisons de cet état de faits est la pauvreté des documentations techniques fournies par les fabricants (ATI et Nvidia), particulièrement en ce qui concerne l'implantation des différents opérateurs arithmétiques embarqués dans les différentes unités de traitement. Or ces informations sont essentielles pour estimer et contrôler les erreurs d'arrondi ou pour mettre en oeuvre des techniques de réduction ou de compensation afin de travailler en précision double, quadruple ou arbitrairement étendue. Nous proposons dans cet article un ensemble de programmes qui permettent de découvrir les caractéristiques principales des GPU en ce qui concerne l'arithmétique à virgule flottante. Nous donnons les résultats obtenus sur deux cartes graphiques récentes: la Nvidia 7800GTX et l'ATI RX1800XL.