OpenRaiser/Intern-Atlas huggingface dataset:
Clifford Algebra of the Vector Space of Conics for decision boundary Hyperplanes in m-Euclidean Space
Venue: arXiv cs.NE 2007
Year: 2007

In this paper we embed $m$-dimensional Euclidean space in the geometric algebra $Cl_m $ to extend the operators of incidence in ${R^m}$ to operators of incidence in the geometric algebra to generalize the notion of separator to a decision boundary hyperconic in the Clifford algebra of hyperconic sections denoted as ${Cl}({Co}_{2})$. This allows us to extend the concept of a linear perceptron or the spherical perceptron in conformal geometry and introduce the more general conic perceptron, namely the {elliptical perceptron}. Using Clifford duality a vector orthogonal to the decision boundary hyperplane is determined. Experimental results are shown in 2-dimensional Euclidean space where we separate data that are naturally separated by some typical plane conic separators by this procedure. This procedure is more general in the sense that it is independent of the dimension of the input data and hence we can speak of the hyperconic elliptic perceptron.
A Leaf Recognition Algorithm for Plant Classification Using Probabilistic Neural Network
Venue: arXiv cs.AI 2007
Year: 2007

In this paper, we employ Probabilistic Neural Network (PNN) with image and data processing techniques to implement a general purpose automated leaf recognition algorithm. 12 leaf features are extracted and orthogonalized into 5 principal variables which consist the input vector of the PNN. The PNN is trained by 1800 leaves to classify 32 kinds of plants with an accuracy greater than 90%. Compared with other approaches, our algorithm is an accurate artificial intelligence approach which is fast in execution and easy in implementation.
Spatial Aggregation: Data Model and Implementation
Venue: arXiv cs.DB 2007
Year: 2007

Data aggregation in Geographic Information Systems (GIS) is only marginally present in commercial systems nowadays, mostly through ad-hoc solutions. In this paper, we first present a formal model for representing spatial data. This model integrates geographic data and information contained in data warehouses external to the GIS. We define the notion of geometric aggregation, a general framework for aggregate queries in a GIS setting. We also identify the class of summable queries, which can be efficiently evaluated by precomputing the overlay of two or more of the thematic layers involved in the query. We also sketch a language, denoted GISOLAP-QL, for expressing queries that involve GIS and OLAP features. In addition, we introduce Piet, an implementation of our proposal, that makes use of overlay precomputation for answering spatial queries (aggregate or not). Our experimental evaluation showed that for a certain class of geometric queries with or without aggregation, overlay precomputation outperforms R-tree-based techniques. Finally, as a particular application of our proposal, we study topological queries.
A Note on Shortest Developments
Venue: arXiv cs.LO 2007
Year: 2007

De Vrijer has presented a proof of the finite developments theorem which, in addition to showing that all developments are finite, gives an effective reduction strategy computing longest developments as well as a simple formula computing their length. We show that by applying a rather simple and intuitive principle of duality to de Vrijer's approach one arrives at a proof that some developments are finite which in addition yields an effective reduction strategy computing shortest developments as well as a simple formula computing their length. The duality fails for general beta-reduction. Our results simplify previous work by Khasidashvili.
Capacity Region of the Finite-State Multiple Access Channel with and without Feedback
Venue: arXiv cs.IT 2007
Year: 2007

The capacity region of the Finite-State Multiple Access Channel (FS-MAC) with feedback that may be an arbitrary time-invariant function of the channel output samples is considered. We characterize both an inner and an outer bound for this region, using Masseys's directed information. These bounds are shown to coincide, and hence yield the capacity region, of FS-MACs where the state process is stationary and ergodic and not affected by the inputs. Though `multi-letter' in general, our results yield explicit conclusions when applied to specific scenarios of interest. E.g., our results allow us to: - Identify a large class of FS-MACs, that includes the additive mod-2 noise MAC where the noise may have memory, for which feedback does not enlarge the capacity region. - Deduce that, for a general FS-MAC with states that are not affected by the input, if the capacity (region) without feedback is zero, then so is the capacity (region) with feedback. - Deduce that the capacity region of a MAC that can be decomposed into a `multiplexer' concatenated by a point-to-point channel (with, without, or with partial feedback), the capacity region is given by $\sum_{m} R_m \leq C$, where C is the capacity of the point to point channel and m indexes the encoders. Moreover, we show that for this family of channels source-channel coding separation holds.
A preliminary analysis on metaheuristics methods applied to the Haplotype Inference Problem
Venue: arXiv cs.AI 2007
Year: 2007

Haplotype Inference is a challenging problem in bioinformatics that consists in inferring the basic genetic constitution of diploid organisms on the basis of their genotype. This information allows researchers to perform association studies for the genetic variants involved in diseases and the individual responses to therapeutic agents. A notable approach to the problem is to encode it as a combinatorial problem (under certain hypotheses, such as the pure parsimony criterion) and to solve it using off-the-shelf combinatorial optimization techniques. The main methods applied to Haplotype Inference are either simple greedy heuristic or exact methods (Integer Linear Programming, Semidefinite Programming, SAT encoding) that, at present, are adequate only for moderate size instances. We believe that metaheuristic and hybrid approaches could provide a better scalability. Moreover, metaheuristics can be very easily combined with problem specific heuristics and they can also be integrated with tree-based search techniques, thus providing a promising framework for hybrid systems in which a good trade-off between effectiveness and efficiency can be reached. In this paper we illustrate a feasibility study of the approach and discuss some relevant design issues, such as modeling and design of approximate solvers that combine constructive heuristics, local search-based improvement strategies and learning mechanisms. Besides the relevance of the Haplotype Inference problem itself, this preliminary analysis is also an interesting case study because the formulation of the problem poses some challenges in modeling and hybrid metaheuristic solver design that can be generalized to other problems.
Open and Free Cluster for Public
Venue: arXiv cs.DC 2007
Year: 2007

We introduce the LIPI Public Cluster, the first parallel machine facility fully open for public and for free in Indonesia and surrounding countries. In this paper, we focus on explaining our globally new concept on open cluster, and how to realize and manage it to meet the users needs. We show that after 2 years trial running and several upgradings, the Public Cluster performs well and is able to fulfil all requirements as expected.
A Formulation of the Channel Capacity of Multiple-Access Channel
Venue: arXiv cs.IT 2007
Year: 2007

The necessary and sufficient condition of the channel capacity is rigorously formulated for the N-user discrete memoryless multiple-access channel (MAC). The essence of the formulation is to invoke an {\em elementary} MAC where sizes of input alphabets are not greater than the size of output alphabet. The main objective is to demonstrate that the channel capacity of an MAC is achieved by an elementary MAC included in the original MAC. The proof is quite straightforward by the very definition of the elementary MAC. Moreover it is proved that the Kuhn-Tucker conditions of the elementary MAC are strictly sufficient and obviously necessary for the channel capacity. The latter proof requires some steps such that for the elementary MAC every solution of the Kuhn-Tucker conditions reveals itself as local maximum on the domain of all possible input probability distributions and then it achieves the channel capacity. As a result, in respect of the channel capacity, the MAC in general can be regarded as an aggregate of a finite number of elementary MAC's.
Diversity-Multiplexing Tradeoff of Asynchronous Cooperative Diversity in Wireless Networks
Venue: arXiv cs.IT 2007
Year: 2007

Synchronization of relay nodes is an important and critical issue in exploiting cooperative diversity in wireless networks. In this paper, two asynchronous cooperative diversity schemes are proposed, namely, distributed delay diversity and asynchronous space-time coded cooperative diversity schemes. In terms of the overall diversity-multiplexing (DM) tradeoff function, we show that the proposed independent coding based distributed delay diversity and asynchronous space-time coded cooperative diversity schemes achieve the same performance as the synchronous space-time coded approach which requires an accurate symbol-level timing synchronization to ensure signals arriving at the destination from different relay nodes are perfectly synchronized. This demonstrates diversity order is maintained even at the presence of asynchronism between relay node. Moreover, when all relay nodes succeed in decoding the source information, the asynchronous space-time coded approach is capable of achieving better DM-tradeoff than synchronous schemes and performs equivalently to transmitting information through a parallel fading channel as far as the DM-tradeoff is concerned. Our results suggest the benefits of fully exploiting the space-time degrees of freedom in multiple antenna systems by employing asynchronous space-time codes even in a frequency flat fading channel. In addition, it is shown asynchronous space-time coded systems are able to achieve higher mutual information than synchronous space-time coded systems for any finite signal-to-noise-ratio (SNR) when properly selected baseband waveforms are employed.
Defensive forecasting for optimal prediction with expert advice
Venue: arXiv cs.LG 2007
Year: 2007

The method of defensive forecasting is applied to the problem of prediction with expert advice for binary outcomes. It turns out that defensive forecasting is not only competitive with the Aggregating Algorithm but also handles the case of "second-guessing" experts, whose advice depends on the learner's prediction; this paper assumes that the dependence on the learner's prediction is continuous.
Designing a Collaborative Research Environment for Students and their Supervisors (CRESS)
Venue: arXiv cs.HC 2007
Year: 2007

In a previous paper the CSCR domain was defined. Here this is taken to the next stage where the design of a particular Collaborative Research Environment to support Students and Supervisors (CRESS) is considered. Following the CSCR structure this paper deals with an analysis of 13 collaborative working environments to determine a preliminary design for CRESS in order to discover the most appropriate set of tools for its implementation.
A Language for Generic Programming in the Large
Venue: arXiv cs.PL 2007
Year: 2007

Generic programming is an effective methodology for developing reusable software libraries. Many programming languages provide generics and have features for describing interfaces, but none completely support the idioms used in generic programming. To address this need we developed the language G. The central feature of G is the concept, a mechanism for organizing constraints on generics that is inspired by the needs of modern C++ libraries. G provides modular type checking and separate compilation (even of generics). These characteristics support modular software development, especially the smooth integration of independently developed components. In this article we present the rationale for the design of G and demonstrate the expressiveness of G with two case studies: porting the Standard Template Library and the Boost Graph Library from C++ to G. The design of G shares much in common with the concept extension proposed for the next C++ Standard (the authors participated in its design) but there are important differences described in this article.
Minimum Cost Homomorphisms to Reflexive Digraphs
Venue: arXiv cs.DM 2007
Year: 2007

For digraphs $G$ and $H$, a homomorphism of $G$ to $H$ is a mapping $f:\ V(G)\dom V(H)$ such that $uv\in A(G)$ implies $f(u)f(v)\in A(H)$. If moreover each vertex $u \in V(G)$ is associated with costs $c_i(u), i \in V(H)$, then the cost of a homomorphism $f$ is $\sum_{u\in V(G)}c_{f(u)}(u)$. For each fixed digraph $H$, the {\em minimum cost homomorphism problem} for $H$, denoted MinHOM($H$), is the following problem. Given an input digraph $G$, together with costs $c_i(u)$, $u\in V(G)$, $i\in V(H)$, and an integer $k$, decide if $G$ admits a homomorphism to $H$ of cost not exceeding $k$. We focus on the minimum cost homomorphism problem for {\em reflexive} digraphs $H$ (every vertex of $H$ has a loop). It is known that the problem MinHOM($H$) is polynomial time solvable if the digraph $H$ has a {\em Min-Max ordering}, i.e., if its vertices can be linearly ordered by $<$ so that $i<j, s<r$ and $ir, js \in A(H)$ imply that $is \in A(H)$ and $jr \in A(H)$. We give a forbidden induced subgraph characterization of reflexive digraphs with a Min-Max ordering; our characterization implies a polynomial time test for the existence of a Min-Max ordering. Using this characterization, we show that for a reflexive digraph $H$ which does not admit a Min-Max ordering, the minimum cost homomorphism problem is NP-complete. Thus we obtain a full dichotomy classification of the complexity of minimum cost homomorphism problems for reflexive digraphs.
On the Security of the Cha-Ko-Lee-Han-Cheon Braid Group Public Key Cryptosystem
Venue: arXiv cs.CR 2007
Year: 2007

We show that a number of cryptographic protocols using non-commutative semigroups including the Cha-Ko-Lee-Han-Cheon braid group public-key cryptosystem and related public-key cryptosystems such as the Shpilrain-Ushakov public-key cryptosystems are based on the MSCSP.
Priority Queue Based on Multilevel Prefix Tree
Venue: arXiv cs.DS 2007
Year: 2007

Tree structures are very often used data structures. Among ordered types of trees there are many variants whose basic operations such as insert, delete, search, delete-min are characterized by logarithmic time complexity. In the article I am going to present the structure whose time complexity for each of the above operations is $O(\frac{M}{K} + K)$, where M is the size of data type and K is constant properly matching the size of data type. Properly matched K will make the structure function as a very effective Priority Queue. The structure size linearly depends on the number and size of elements. PTrie is a clever combination of the idea of prefix tree -- Trie, structure of logarithmic time complexity for insert and remove operations, doubly linked list and queues.
Network Coding Capacity of Random Wireless Networks under a Signal-to-Interference-and-Noise Model
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we study network coding capacity for random wireless networks. Previous work on network coding capacity for wired and wireless networks have focused on the case where the capacities of links in the network are independent. In this paper, we consider a more realistic model, where wireless networks are modeled by random geometric graphs with interference and noise. In this model, the capacities of links are not independent. We consider two scenarios, single source multiple destinations and multiple sources multiple destinations. In the first scenario, employing coupling and martingale methods, we show that the network coding capacity for random wireless networks still exhibits a concentration behavior around the mean value of the minimum cut under some mild conditions. Furthermore, we establish upper and lower bounds on the network coding capacity for dependent and independent nodes. In the second one, we also show that the network coding capacity still follows a concentration behavior. Our simulation results confirm our theoretical predictions.
Linear Time Algorithms Based on Multilevel Prefix Tree for Finding Shortest Path with Positive Weights and Minimum Spanning Tree in a Networks
Venue: arXiv cs.DS 2007
Year: 2007

In this paper I present general outlook on questions relevant to the basic graph algorithms; Finding the Shortest Path with Positive Weights and Minimum Spanning Tree. I will show so far known solution set of basic graph problems and present my own. My solutions to graph problems are characterized by their linear worst-case time complexity. It should be noticed that the algorithms which compute the Shortest Path and Minimum Spanning Tree problems not only analyze the weight of arcs (which is the main and often the only criterion of solution hitherto known algorithms) but also in case of identical path weights they select this path which walks through as few vertices as possible. I have presented algorithms which use priority queue based on multilevel prefix tree -- PTrie. PTrie is a clever combination of the idea of prefix tree -- Trie, the structure of logarithmic time complexity for insert and remove operations, doubly linked list and queues. In C++ I will implement linear worst-case time algorithm computing the Single-Destination Shortest-Paths problem and I will explain its usage.
A Polynomial-time Algorithm for Computing the Permanent in GF(3^q)
Venue: arXiv cs.CC 2007
Year: 2007

A polynomial-time algorithm for computing the permanent in any field of characteristic 3 is presented in this article. The principal objects utilized for that purpose are the Cauchy and Vandermonde matrices, the discriminant function and their generalizations of various types. Classical theorems on the permanent such as the Binet-Minc identity and Borchadt's formula are widely applied, while a special new technique involving the notion of limit re-defined for fields of finite characteristics and corresponding computational methods was developed in order to deal with a number of polynomial-time reductions. All the constructions preserve a strictly algebraic nature ignoring the structure of the basic field, while applying its infinite extensions for calculating limits. A natural corollary of the polynomial-time computability of the permanent in a field of a characteristic different from 2 is the non-uniform equality between the complexity classes P and NP what is equivalent to RP=NP (Ref. [1]).
Ambient Multimodality: an Asset for Developing Universal Access to the Information Society
Venue: arXiv cs.HC 2007
Year: 2007

The paper tries to point out the benefits that can be derived from research advances in the implementation of concepts such as ambient intelligence (AmI) and ubiquitous or pervasive computing for promoting Universal Access (UA) to the Information Society, that is, for contributing to enable everybody, especially Physically Disabled (PD) people, to have easy access to all computing resources and information services that the coming worldwide Information Society will soon make available to the general public. Following definitions of basic concepts relating to multimodal interaction, the significant contribution of multimodality to developing UA is briefly argued. Then, a short state of the art in AmI research is presented. In the last section we bring out the potential contribution of advances in AmI research and technology to the improvement of computer access for PD people. This claim is supported by the following observations: (i) most projects aiming at implementing AmI focus on the design of new interaction modalities and flexible multimodal user interfaces which may facilitate PD users' computer access ; (ii) targeted applications will support users in a wide range of daily activities which will be performed simultaneously with supporting computing tasks; therefore, users will be placed in contexts where they will be confronted with similar difficulties to those encountered by PD users; (iii) AmI applications being intended for the general public, a wide range of new interaction devices and flexible processing software will be available, making it possible to provide PD users with human-computer facilities tailored to their specific needs at reasonable expense..
Interfaces adaptatives Adaptation dynamique à l'utilisateur courant
Venue: arXiv cs.HC 2007
Year: 2007

We present a survey of recent research studies of the implementation of adaptive user models in human-computer interaction. A classification of research directions on adaptive user interfaces is first proposed; it takes account of the user characteristics that are modelled, the distribution of initiative and control of the system evolution between user and system, and the role of dynamic adaptation. Then, a few representative research studies are briefly presented to illustrate this classification. In the conclusion, some major issues regarding the utility and usability of adaptive user interfaces and the design of an appropriate methodology for assessing the ergonomic quality of this new form of interaction are mentioned.
A Non Parametric Model for the Forecasting of the Venezuelan Oil Prices
Venue: arXiv cs.CE 2007
Year: 2007

A neural net model for forecasting the prices of Venezuelan crude oil is proposed. The inputs of the neural net are selected by reference to a dynamic system model of oil prices by Mashayekhi (1995, 2001) and its performance is evaluated using two criteria: the Excess Profitability test by Anatoliev and Gerko (2005) and the characteristics of the equity curve generated by a trading strategy based on the neural net predictions. ----- Se introduce aqui un modelo no parametrico para pronosticar los precios del petroleo Venezolano cuyos insumos son seleccionados en base a un sistema dinamico que explica los precios en terminos de dichos insumos. Se describe el proceso de recoleccion y pre-procesamiento de datos y la corrida de la red y se evaluan sus pronosticos a traves de un test estadistico de predictibilidad y de las caracteristicas del Equity Curve inducido por la estrategia de compraventa bursatil generada por dichos pronosticos.
The Isoconditioning Loci of Planar Three-DOF Parallel Manipulators
Venue: arXiv cs.RO 2007
Year: 2007

The subject of this paper is a special class of three-degree-of-freedom parallel manipulators. The singular configurations of the two Jacobian matrices are first studied. The isotropic configurations are then found based on the characteristic length of this manipulator. The isoconditioning loci for the Jacobian matrices are plotted to define a global performance index allowing the comparison of the different working modes. The index thus resulting is compared with the Cartesian workspace surface and the average of the condition number.
Kinematic analysis of the 3-RPR parallel manipulator
Venue: arXiv cs.RO 2007
Year: 2007

The aim of this paper is the kinematic study of a 3-RPR planar parallel manipulator where the three fixed revolute joints are actuated. The direct and inverse kinematic problem as well as the singular configuration is characterized. On parallel singular configurations, the motion produce by the mobile platform can be compared to the Reuleaux straight-line mechanism.