OpenRaiser/Intern-Atlas huggingface dataset:
A First Step Towards Automatically Building Network Representations
Venue: arXiv cs.DC 2007
Year: 2007

To fully harness Grids, users or middlewares must have some knowledge on the topology of the platform interconnection network. As such knowledge is usually not available, one must uses tools which automatically build a topological network model through some measurements. In this article, we define a methodology to assess the quality of these network model building tools, and we apply this methodology to representatives of the main classes of model builders and to two new algorithms. We show that none of the main existing techniques build models that enable to accurately predict the running time of simple application kernels for actual platforms. However some of the new algorithms we propose give excellent results in a wide range of situations.
Random Sentences from a Generalized Phrase-Structure Grammar Interpreter
Venue: arXiv cs.CL 2007
Year: 2007

In numerous domains in cognitive science it is often useful to have a source for randomly generated corpora. These corpora may serve as a foundation for artificial stimuli in a learning experiment (e.g., Ellefson & Christiansen, 2000), or as input into computational models (e.g., Christiansen & Dale, 2001). The following compact and general C program interprets a phrase-structure grammar specified in a text file. It follows parameters set at a Unix or Unix-based command-line and generates a corpus of random sentences from that grammar.
Observable Graphs
Venue: arXiv cs.MA 2007
Year: 2007

An edge-colored directed graph is \emph{observable} if an agent that moves along its edges is able to determine his position in the graph after a sufficiently long observation of the edge colors. When the agent is able to determine his position only from time to time, the graph is said to be \emph{partly observable}. Observability in graphs is desirable in situations where autonomous agents are moving on a network and one wants to localize them (or the agent wants to localize himself) with limited information. In this paper, we completely characterize observable and partly observable graphs and show how these concepts relate to observable discrete event systems and to local automata. Based on these characterizations, we provide polynomial time algorithms to decide observability, to decide partial observability, and to compute the minimal number of observations necessary for finding the position of an agent. In particular we prove that in the worst case this minimal number of observations increases quadratically with the number of nodes in the graph. From this it follows that it may be necessary for an agent to pass through the same node several times before he is finally able to determine his position in the graph. We then consider the more difficult question of assigning colors to a graph so as to make it observable and we prove that two different versions of this problem are NP-complete.
Paging and Registration in Cellular Networks: Jointly Optimal Policies and an Iterative Algorithm
Venue: arXiv cs.IT 2007
Year: 2007

This paper explores optimization of paging and registration policies in cellular networks. Motion is modeled as a discrete-time Markov process, and minimization of the discounted, infinite-horizon average cost is addressed. The structure of jointly optimal paging and registration policies is investigated through the use of dynamic programming for partially observed Markov processes. It is shown that there exist policies with a certain simple form that are jointly optimal, though the dynamic programming approach does not directly provide an efficient method to find the policies. An iterative algorithm for policies with the simple form is proposed and investigated. The algorithm alternates between paging policy optimization and registration policy optimization. It finds a pair of individually optimal policies, but an example is given showing that the policies need not be jointly optimal. Majorization theory and Riesz's rearrangement inequality are used to show that jointly optimal paging and registration policies are given for symmetric or Gaussian random walk models by the nearest-location-first paging policy and distance threshold registration policies.
Transmitter and Precoding Order Optimization for Nonlinear Downlink Beamforming
Venue: arXiv cs.IT 2007
Year: 2007

The downlink of a multiple-input multiple output (MIMO) broadcast channel (BC) is considered, where each receiver is equipped with a single antenna and the transmitter performs nonlinear Dirty-Paper Coding (DPC). We present an efficient algorithm that finds the optimum transmit filters and power allocation as well as the optimum precoding order(s) possibly affording time-sharing between individual DPC orders. Subsequently necessary and sufficient conditions for the optimality of an arbitrary precoding order are derived. Based on these we propose a suboptimal algorithm showing excellent performance and having low complexity.
Bayesian Network Tomography and Inference
Venue: arXiv cs.NI 2007
Year: 2007

The aim of this technical report is to give a short overview of known techniques for network tomography (introduced in the paper of Vardi (1996)), extended by a Bayesian approach originating Tebaldi and West (1998). Since the studies of A.K. Erlang (1878-1929) on telephone networks in the last millennium, lots of needs are seen in todays applications of networks and network tomography, so for instance networks are a critical component of the information structure supporting finance, commerce and even civil and national defence. An attack on a network can be performed as an intrusion in the network or as sending a lot of fault information and disturbing the network flow. Such attacks can be detected by modelling the traffic flows in a network, by counting the source destination packets and even by measuring counts over time and by drawing a comparison with this 'time series' for instance.
Reconstructing the Nonlinear Filter Function of LILI-128 Stream Cipher Based on Complexity
Venue: arXiv cs.CR 2007
Year: 2007

In this letter we assert that we have reconstructed the nonlinear filter function of LILI-128 stream cipher on IBM notebook PC using MATLAB. Our reconstruction need approximately 2^12~2^13 and the attack consumes 5825.016 sec (using tic and toc sentences of MATLAB) or 5825.016/3600=1.6181hours. We got the expression of the nonlinear filter function fd of Lili-128 which has 46 items from liner items to nonlinear items based on complexity, the phase space reconstruction, Clustering and nonlinear prediction. We have verified our reconstruction result correctness by simulating the overview of Lili-128 keystream generators using our getting fd and implement designers reference module of the Lili-128 stream cipher, and two methods produce the same synchronous keystream sequence on same initial state, so that our research work proves that the nonlinear filter function of LILI-128 stream cipher is successfully reconstructed.
Syndrome Decoding of Reed-Solomon Codes Beyond Half the Minimum Distance based on Shift-Register Synthesis
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, a new approach for decoding low-rate Reed-Solomon codes beyond half the minimum distance is considered and analyzed. Unlike the Sudan algorithm published in 1997, this new approach is based on multi-sequence shift-register synthesis, which makes it easy to understand and simple to implement. The computational complexity of this shift-register based algorithm is of the same order as the complexity of the well-known Berlekamp-Massey algorithm. Moreover, the error correcting radius coincides with the error correcting radius of the original Sudan algorithm, and the practical decoding performance observed on a q-ary symmetric channel (QSC) is virtually identical to the decoding performance of the Sudan algorithm. Bounds for the failure and error probability as well as for the QSC decoding performance of the new algorithm are derived, and the performance is illustrated by means of examples.
Essential Inputs and Minimal Tree Automata
Venue: arXiv cs.CC 2007
Year: 2007

We continue studying essential inputs of trees and automata. Strongly essential inputs of trees are introduced and studied. Various examples for application in Computer Science are shown.
Coupling Control and Human-Centered Automation in Mathematical Models of Complex Systems
Venue: arXiv cs.CE 2007
Year: 2007

In this paper we analyze mathematically how human factors can be effectively incorporated into the analysis and control of complex systems. As an example, we focus our discussion around one of the key problems in the Intelligent Transportation Systems (ITS) theory and practice, the problem of speed control, considered here as a decision making process with limited information available. The problem is cast mathematically in the general framework of control problems and is treated in the context of dynamically changing environments where control is coupled to human-centered automation. Since in this case control might not be limited to a small number of control settings, as it is often assumed in the control literature, serious difficulties arise in the solution of this problem. We demonstrate that the problem can be reduced to a set of Hamilton-Jacobi-Bellman equations where human factors are incorporated via estimations of the system Hamiltonian. In the ITS context, these estimations can be obtained with the use of on-board equipment like sensors/receivers/actuators, in-vehicle communication devices, etc. The proposed methodology provides a way to integrate human factor into the solving process of the models for other complex dynamic systems.
A Quantifier-Free String Theory for ALOGTIME Reasoning
Venue: arXiv cs.CC 2007
Year: 2007

The main contribution of this work is the definition of a quantifier-free string theory T_1 suitable for formalizing ALOGTIME reasoning. After describing L_1 -- a new, simple, algebraic characterization of the complexity class ALOGTIME based on strings instead of numbers -- the theory T_1 is defined (based on L_1), and a detailed formal development of T_1 is given. Then, theorems of T_1 are shown to translate into families of propositional tautologies that have uniform polysize Frege proofs, T_1 is shown to prove the soundness of a particular Frege system F, and F is shown to provably p-simulate any proof system whose soundness can be proved in T_1. Finally, T_1 is compared with other theories for ALOGTIME reasoning in the literature. To our knowledge, this is the first formal theory for ALOGTIME reasoning whose basic objects are strings instead of numbers, and the first quantifier-free theory formalizing ALOGTIME reasoning in which a direct proof of the soundness of some Frege system has been given (in the case of first-order theories, such a proof was first given by Arai for his theory AID). Also, the polysize Frege proofs we give for the propositional translations of theorems of T_1 are considerably simpler than those for other theories, and so is our proof of the soundness of a particular F-system in T_1. Together with the simplicity of T_1's recursion schemes, axioms, and rules these facts suggest that T_1 is one of the most natural theories available for ALOGTIME reasoning.
First Passage Time for Multivariate Jump-diffusion Stochastic Models With Applications in Finance
Venue: arXiv cs.CE 2007
Year: 2007

The ``first passage-time'' (FPT) problem is an important problem with a wide range of applications in mathematics, physics, biology and finance. Mathematically, such a problem can be reduced to estimating the probability of a (stochastic) process first to reach a critical level or threshold. While in other areas of applications the FPT problem can often be solved analytically, in finance we usually have to resort to the application of numerical procedures, in particular when we deal with jump-diffusion stochastic processes (JDP). In this paper, we develop a Monte-Carlo-based methodology for the solution of the FPT problem in the context of a multivariate jump-diffusion stochastic process. The developed methodology is tested by using different parameters, the simulation results indicate that the developed methodology is much more efficient than the conventional Monte Carlo method. It is an efficient tool for further practical applications, such as the analysis of default correlation and predicting barrier options in finance.
Generic Global Constraints based on MDDs
Venue: arXiv cs.AI 2007
Year: 2007

Constraint Programming (CP) has been successfully applied to both constraint satisfaction and constraint optimization problems. A wide variety of specialized global constraints provide critical assistance in achieving a good model that can take advantage of the structure of the problem in the search for a solution. However, a key outstanding issue is the representation of 'ad-hoc' constraints that do not have an inherent combinatorial nature, and hence are not modeled well using narrowly specialized global constraints. We attempt to address this issue by considering a hybrid of search and compilation. Specifically we suggest the use of Reduced Ordered Multi-Valued Decision Diagrams (ROMDDs) as the supporting data structure for a generic global constraint. We give an algorithm for maintaining generalized arc consistency (GAC) on this constraint that amortizes the cost of the GAC computation over a root-to-leaf path in the search tree without requiring asymptotically more space than used for the MDD. Furthermore we present an approach for incrementally maintaining the reduced property of the MDD during the search, and show how this can be used for providing domain entailment detection. Finally we discuss how to apply our approach to other similar data structures such as AOMDDs and Case DAGs. The technique used can be seen as an extension of the GAC algorithm for the regular language constraint on finite length input.
Embedding Graphs into the Extended Grid
Venue: arXiv cs.DM 2007
Year: 2007

Let $G=(V,E)$ be an arbitrary undirected source graph to be embedded in a target graph $EM$, the extended grid with vertices on integer grid points and edges to nearest and next-nearest neighbours. We present an algorithm showing how to embed $G$ into $EM$ in both time and space $O(|V|^2)$ using the new notions of islands and bridges. An island is a connected subgraph in the target graph which is mapped from exactly one vertex in the source graph while a bridge is an edge between two islands which is mapped from exactly one edge in the source graph. This work is motivated by real industrial applications in the field of quantum computing and a need to efficiently embed source graphs in the extended grid.
Accelerating Socio-Technological Evolution: from ephemeralization and stigmergy to the global brain
Venue: arXiv cs.CY 2007
Year: 2007

Evolution is presented as a trial-and-error process that produces a progressive accumulation of knowledge. At the level of technology, this leads to ephemeralization, i.e. ever increasing productivity, or decreasing of the friction that normally dissipates resources. As a result, flows of matter, energy and information circulate ever more easily across the planet. This global connectivity increases the interactions between agents, and thus the possibilities for conflict. However, evolutionary progress also reduces social friction, via the creation of institutions. The emergence of such "mediators" is facilitated by stigmergy: the unintended collaboration between agents resulting from their actions on a shared environment. The Internet is a near ideal medium for stigmergic interaction. Quantitative stigmergy allows the web to learn from the activities of its users, thus becoming ever better at helping them to answer their queries. Qualitative stigmergy stimulates agents to collectively develop novel knowledge. Both mechanisms have direct analogues in the functioning of the human brain. This leads us to envision the future, super-intelligent web as a "global brain" for humanity. The feedback between social and technological advances leads to an extreme acceleration of innovation. An extrapolation of the corresponding hyperbolic growth model would forecast a singularity around 2040. This can be interpreted as the evolutionary transition to the Global Brain regime.
XORSAT: An Efficient Algorithm for the DIMACS 32-bit Parity Problem
Venue: arXiv cs.DS 2007
Year: 2007

The DIMACS 32-bit parity problem is a satisfiability (SAT) problem hard to solve. So far, EqSatz by Li is the only solver which can solve this problem. However, This solver is very slow. It is reported that it spent 11855 seconds to solve a par32-5 instance on a Maxintosh G3 300 MHz. The paper introduces a new solver, XORSAT, which splits the original problem into two parts: structured part and random part, and then solves separately them with WalkSAT and an XOR equation solver. Based our empirical observation, XORSAT is surprisingly fast, which is approximately 1000 times faster than EqSatz. For a par32-5 instance, XORSAT took 2.9 seconds, while EqSatz took 2844 seconds on Intel Pentium IV 2.66GHz CPU. We believe that this method significantly different from traditional methods is also useful beyond this domain.
A Methodological Framework for Socio-Cognitive Analyses of Collaborative Design of Open Source Software
Venue: arXiv cs.HC 2007
Year: 2007

Open Source Software (OSS) development challenges traditional software engineering practices. In particular, OSS projects are managed by a large number of volunteers, working freely on the tasks they choose to undertake. OSS projects also rarely rely on explicit system-level design, or on project plans or schedules. Moreover, OSS developers work in arbitrary locations and collaborate almost exclusively over the Internet, using simple tools such as email and software code tracking databases (e.g. CVS). All the characteristics above make OSS development akin to weaving a tapestry of heterogeneous components. The OSS design process relies on various types of actors: people with prescribed roles, but also elements coming from a variety of information spaces (such as email and software code). The objective of our research is to understand the specific hybrid weaving accomplished by the actors of this distributed, collective design process. This, in turn, challenges traditional methodologies used to understand distributed software engineering: OSS development is simply too "fibrous" to lend itself well to analysis under a single methodological lens. In this paper, we describe the methodological framework we articulated to analyze collaborative design in the Open Source world. Our framework focuses on the links between the heterogeneous components of a project's hybrid network. We combine ethnography, text mining, and socio-technical network analysis and visualization to understand OSS development in its totality. This way, we are able to simultaneously consider the social, technical, and cognitive aspects of OSS development. We describe our methodology in detail, and discuss its implications for future research on distributed collective practices.
Pre-Requirement Specification Traceability: Bridging the Complexity Gap through Capabilities
Venue: arXiv cs.SE 2007
Year: 2007

Pre-Requirement Specification traceability is the activity of capturing relations between requirements and their sources, in particular user needs. Requirements are formal technical specifications in the solution space; needs are natural language expressions codifying user expectations in the problem space. Current traceability techniques are challenged by the complexity gap that results from the disparity between the spaces, and thereby, often neglect traceability to and from requirements. We identify the existence of an intermediary region -- the transition space -- which structures the progression from needs to requirements. More specifically, our approach to developing change-tolerant systems, termed Capabilities Engineering, identifies highly cohesive, minimally coupled, optimized functional abstractions called Capabilities in the transition space. These Capabilities link the problem and solution spaces through directives (entities derived from user needs). Directives connect the problem and transition spaces; Capabilities link the transition and solution spaces. Furthermore, the process of Capabilities Engineering addresses specific traceability challenges. It supports the evolution of traces, provides semantic and structural information about dependencies, incorporates human factors, generates traceability relations with negligible overhead, and thereby, fosters pre-Requirement Specification traceability.
Rate of Channel Hardening of Antenna Selection Diversity Schemes and Its Implication on Scheduling
Venue: arXiv cs.IT 2007
Year: 2007

For a multiple antenna system, we compute the asymptotic distribution of antenna selection gain when the transmitter selects the transmit antenna with the strongest channel. We use this to asymptotically estimate the underlying channel capacity distributions, and demonstrate that unlike multiple-input/multiple-output (MIMO) systems, the channel for antenna selection systems hardens at a slower rate, and thus a significant multiuser scheduling gain can exist - O(1/ log m) for channel selection as opposed to O(1/ sqrt{m}) for MIMO, where m is the number of transmit antennas. Additionally, even without this scheduling gain, it is demonstrated that transmit antenna selection systems outperform open loop MIMO systems in low signal-to-interference-plus-noise ratio (SINR) regimes, particularly for a small number of receive antennas. This may have some implications on wireless system design, because most of the users in modern wireless systems have low SINRs
Transforming structures by set interpretations
Venue: arXiv cs.LO 2007
Year: 2007

We consider a new kind of interpretation over relational structures: finite sets interpretations. Those interpretations are defined by weak monadic second-order (WMSO) formulas with free set variables. They transform a given structure into a structure with a domain consisting of finite sets of elements of the orignal structure. The definition of these interpretations directly implies that they send structures with a decidable WMSO theory to structures with a decidable first-order theory. In this paper, we investigate the expressive power of such interpretations applied to infinite deterministic trees. The results can be used in the study of automatic and tree-automatic structures.
Why the Standard Data Processing should be changed
Venue: arXiv cs.MS 2007
Year: 2007

The basic statistical methods of data representation did not change since their emergence. Their simplicity was dictated by the intricacies of computations in the before computers epoch. It turns out that such approach is not uniquely possible in the presence of quick computers. The suggested here method improves significantly the reliability of data processing and their graphical representation. In this paper we show problems of the standard data processing which can bring to incorrect results. A method solving these problems is proposed. It is based on modification of data representation. The method was implemented in a computer program Consensus5. The program performances are illustrated through varied examples.
Comparing Architectures of Mobile Applications
Venue: arXiv cs.OH 2007
Year: 2007

This article describes various advantages and disadvantages of SMS, WAP, J2ME and Windows CE technologies in designing mobile applications. In defining the architecture of any software application it is important to get the best trade-off between platform's possibilities and design requirements. Achieving optimum software design is even more important with mobile applications where all computer resources are limited. Therefore, it is important to have a comparative analysis of all relevant contemporary approaches in designing mobile applications. As always, the choice between these technologies is determined by application requirements and system capabilities.