OpenRaiser/Intern-Atlas huggingface dataset:
Orthomodular Lattices Induced by the Concurrency Relation
Venue: arXiv cs.LO 2009
Year: 2009

We apply to locally finite partially ordered sets a construction which associates a complete lattice to a given poset; the elements of the lattice are the closed subsets of a closure operator, defined starting from the concurrency relation. We show that, if the partially ordered set satisfies a property of local density, i.e.: N-density, then the associated lattice is also orthomodular. We then consider occurrence nets, introduced by C.A. Petri as models of concurrent computations, and define a family of subsets of the elements of an occurrence net; we call those subsets "causally closed" because they can be seen as subprocesses of the whole net which are, intuitively, closed with respect to the forward and backward local state changes. We show that, when the net is K-dense, the causally closed sets coincide with the closed sets induced by the closure operator defined starting from the concurrency relation. K-density is a property of partially ordered sets introduced by Petri, on the basis of former axiomatizations of special relativity theory.
A Type System for Required/Excluded Elements in CLS
Venue: arXiv cs.LO 2009
Year: 2009

The calculus of looping sequences is a formalism for describing the evolution of biological systems by means of term rewriting rules. We enrich this calculus with a type discipline to guarantee the soundness of reduction rules with respect to some biological properties deriving from the requirement of certain elements, and the repellency of others. As an example, we model a toy system where the repellency of a certain element is captured by our type system and forbids another element to exit a compartment.
Deterministic Autopoietic Automata
Venue: arXiv cs.NE 2009
Year: 2009

This paper studies two issues related to the paper on Computing by Self-reproduction: Autopoietic Automata by Jiri Wiedermann. It is shown that all results presented there extend to deterministic computations. In particular, nondeterminism is not needed for a lineage to generate all autopoietic automata.
Diffusion Controlled Reactions, Fluctuation Dominated Kinetics, and Living Cell Biochemistry
Venue: arXiv cs.CE 2009
Year: 2009

In recent years considerable portion of the computer science community has focused its attention on understanding living cell biochemistry and efforts to understand such complication reaction environment have spread over wide front, ranging from systems biology approaches, through network analysis (motif identification) towards developing language and simulators for low level biochemical processes. Apart from simulation work, much of the efforts are directed to using mean field equations (equivalent to the equations of classical chemical kinetics) to address various problems (stability, robustness, sensitivity analysis, etc.). Rarely is the use of mean field equations questioned. This review will provide a brief overview of the situations when mean field equations fail and should not be used. These equations can be derived from the theory of diffusion controlled reactions, and emerge when assumption of perfect mixing is used.
Asymmetric Multilevel Diversity Coding and Asymmetric Gaussian Multiple Descriptions
Venue: arXiv cs.IT 2009
Year: 2009

We consider the asymmetric multilevel diversity (A-MLD) coding problem, where a set of $2^K-1$ information sources, ordered in a decreasing level of importance, is encoded into $K$ messages (or descriptions). There are $2^K-1$ decoders, each of which has access to a non-empty subset of the encoded messages. Each decoder is required to reproduce the information sources up to a certain importance level depending on the combination of descriptions available to it. We obtain a single letter characterization of the achievable rate region for the 3-description problem. In contrast to symmetric multilevel diversity coding, source-separation coding is not sufficient in the asymmetric case, and ideas akin to network coding need to be used strategically. Based on the intuitions gained in treating the A-MLD problem, we derive inner and outer bounds for the rate region of the asymmetric Gaussian multiple description (MD) problem with three descriptions. Both the inner and outer bounds have a similar geometric structure to the rate region template of the A-MLD coding problem, and moreover, we show that the gap between them is small, which results in an approximate characterization of the asymmetric Gaussian three description rate region.
Towards a Number Theoretic Discrete Hilbert Transform
Venue: arXiv cs.DM 2009
Year: 2009

This paper presents an approach for the development of a number theoretic discrete Hilbert transform. The forward transformation has been applied by taking the odd reciprocals that occur in the DHT matrix with respect to a power of 2. Specifically, the expression for a 16-point transform is provided and results of a few representative signals are provided. The inverse transform is the inverse of the forward 16-point matrix. But at this time the inverse transform is not identical to the forward transform and, therefore, our proposed number theoretic transform must be taken as a provisional result.
Active Flows in Diagnostic of Troubleshooting on Backbone Links
Venue: arXiv cs.NI 2009
Year: 2009

This paper aims to identify the operational region of a link in terms of its utilization and alert operators at the point where the link becomes overloaded and requires a capacity upgrade. The number of active flows is considered the real network state and is proposed to use a proxy for utilization. The Gaussian approximation gives the expression for the confidence interval on an operational region. The easy rule has been formulated to display the network defects by means of measurements of router loading and number of active flows. Mean flow performance is considered as the basic universal index characterized quality of network services provided to single user.
Visualization of the Citation Impact Environments of Scientific Journals: An online mapping exercise
Venue: arXiv cs.DL 2009
Year: 2009

Aggregated journal-journal citation networks based on the Journal Citation Reports 2004 of the Science Citation Index (5968 journals) and the Social Science Citation Index (1712 journals) are made accessible from the perspective of any of these journals. The user is thus able to analyze the citation environment in terms of links and graphs. Furthermore, the local impact of a journal is defined as its share of the total citations in the specific journal's citation environments; the vertical size of the nodes is varied proportionally to this citation impact. The horizontal size of each node can be used to provide the same information after correction for within-journal (self)-citations. In the "citing" environment, the equivalents of this measure can be considered as a citation activity index which maps how the relevant journal environment is perceived by the collective of authors of a given journal. As a policy application, the mechanism of interdisciplinary developments among the sciences is elaborated for the case of nanotechnology journals.
Robustness of a bisimulation-type faster-than preorder
Venue: arXiv cs.LO 2009
Year: 2009

TACS is an extension of CCS where upper time bounds for delays can be specified. Luettgen and Vogler defined three variants of bismulation-type faster-than relations and showed that they all three lead to the same preorder, demonstrating the robustness of their approach. In the present paper, the operational semantics of TACS is extended; it is shown that two of the variants still give the same preorder as before, underlining robustness. An explanation is given why this result fails for the third variant. It is also shown that another variant, which mixes old and new operational semantics, can lead to smaller relations that prove the same preorder.
Boltzmann Samplers for v-balanced Colored Necklaces
Venue: arXiv cs.DM 2009
Year: 2009

This paper is devoted to the random generation of particular colored necklaces for which the number of beads of a given color is constrained (these necklaces are called v-balanced). We propose an efficient sampler (its expected time complexity is linear) which satisfies the Boltzmann model principle introduced by Duchon, Flajolet, Louchard and Schaeffer. Our main motivation is to show that the absence of a decomposable specification can be circumvented by mixing the Boltzmann samplers with other types of samplers.
Moderate-Density Parity-Check Codes
Venue: arXiv cs.IT 2009
Year: 2009

We propose a new type of short to moderate block-length, linear error-correcting codes, called moderate-density parity-check (MDPC) codes. The number of ones of the parity-check matrix of the codes presented is typically higher than the number of ones of the parity-check matrix of low-density parity-check (LDPC) codes. But, still lower than those of the parity-check matrix of classical block codes. The proposed MDPC codes are cyclic and are designed by constructing idempotents using cyclotomic cosets. The construction is simple and allows finding short block-length, high-rate codes with good minimum distance. Inspired by some recent iterative soft-input soft-output (SISO) decoders used in a context of classical block codes, we propose a low complexity, efficient, iterative decoder called Auto-Diversity (AD) decoder. AD decoder is based on belief propagation (BP) decoder and takes advantage of the fundamental property of automorphism group of the constructed cyclic code.
On external presentations of infinite graphs
Venue: arXiv cs.FL 2009
Year: 2009

The vertices of a finite state system are usually a subset of the natural numbers. Most algorithms relative to these systems only use this fact to select vertices. For infinite state systems, however, the situation is different: in particular, for such systems having a finite description, each state of the system is a configuration of some machine. Then most algorithmic approaches rely on the structure of these configurations. Such characterisations are said internal. In order to apply algorithms detecting a structural property (like identifying connected components) one may have first to transform the system in order to fit the description needed for the algorithm. The problem of internal characterisation is that it hides structural properties, and each solution becomes ad hoc relatively to the form of the configurations. On the contrary, external characterisations avoid explicit naming of the vertices. Such characterisation are mostly defined via graph transformations. In this paper we present two kind of external characterisations: deterministic graph rewriting, which in turn characterise regular graphs, deterministic context-free languages, and rational graphs. Inverse substitution from a generator (like the complete binary tree) provides characterisation for prefix-recognizable graphs, the Caucal Hierarchy and rational graphs. We illustrate how these characterisation provide an efficient tool for the representation of infinite state systems.
Fundamentals of Large Sensor Networks: Connectivity, Capacity, Clocks and Computation
Venue: arXiv cs.NI 2009
Year: 2009

Sensor networks potentially feature large numbers of nodes that can sense their environment over time, communicate with each other over a wireless network, and process information. They differ from data networks in that the network as a whole may be designed for a specific application. We study the theoretical foundations of such large scale sensor networks, addressing four fundamental issues- connectivity, capacity, clocks and function computation. To begin with, a sensor network must be connected so that information can indeed be exchanged between nodes. The connectivity graph of an ad-hoc network is modeled as a random graph and the critical range for asymptotic connectivity is determined, as well as the critical number of neighbors that a node needs to connect to. Next, given connectivity, we address the issue of how much data can be transported over the sensor network. We present fundamental bounds on capacity under several models, as well as architectural implications for how wireless communication should be organized. Temporal information is important both for the applications of sensor networks as well as their operation.We present fundamental bounds on the synchronizability of clocks in networks, and also present and analyze algorithms for clock synchronization. Finally we turn to the issue of gathering relevant information, that sensor networks are designed to do. One needs to study optimal strategies for in-network aggregation of data, in order to reliably compute a composite function of sensor measurements, as well as the complexity of doing so. We address the issue of how such computation can be performed efficiently in a sensor network and the algorithms for doing so, for some classes of functions.
Can Scientific Journals be Classified in terms of Aggregated Journal-Journal Citation Relations using the Journal Citation Reports?
Venue: arXiv cs.DL 2009
Year: 2009

The aggregated citation relations among journals included in the Science Citation Index provide us with a huge matrix which can be analyzed in various ways. Using principal component analysis or factor analysis, the factor scores can be used as indicators of the position of the cited journals in the citing dimensions of the database. Unrotated factor scores are exact, and the extraction of principal components can be made stepwise since the principal components are independent. Rotation may be needed for the designation, but in the rotated solution a model is assumed. This assumption can be legitimated on pragmatic or theoretical grounds. Since the resulting outcomes remain sensitive to the assumptions in the model, an unambiguous classification is no longer possible in this case. However, the factor-analytic solutions allow us to test classifications against the structures contained in the database. This will be demonstrated for the delineation of a set of biochemistry journals.
Estimating Network Link Characteristics using Packet-Pair Dispersion: A Discrete Time Queueing Theoretic View
Venue: arXiv cs.NI 2009
Year: 2009

Packet-dispersion based measurement tools insert pairs of probe packets with a known separation into the network for transmission over a unicast path or a multicast tree. Samples of the separation between the probe pairs at the destination(s) are observed. Heuristic techniques are then used by these tools to estimate the path characteristics from the observations. In this paper we present a queueing theoretic setting for packet-dispersion based probing. Analogous to network tomography, we develop techniques to estimate the parameters of the arrival process to the individual links from the samples of the output separations, i.e., from the end-to-end measurements. The links are modeled as independent discrete time queues with i.i.d. arrivals. We first obtain an algorithm to obtain the (joint) distribution of the separation between the probes at the destination(s) for a given distribution of the spacing at the input. The parameter estimates of the arrival process are obtained as the minimizer of a cost function between the empirical and calculated distributions. We also carry out extensive simulations and numerical experiments to study the performance of the estimation algorithm under the fairly `harsh' conditions of non stationarity of the arrival process. We find that the estimations work fairly well for two queues in series and for multicast.
A Meta-evaluation of Scientific Research Proposals: Different Ways of Comparing Rejected to Awarded Applications
Venue: arXiv cs.CY 2009
Year: 2009

Combining different data sets with information on grant and fellowship applications submitted to two renowned funding agencies, we are able to compare their funding decisions (award and rejection) with scientometric performance indicators across two fields of science (life sciences and social sciences). The data sets involve 671 applications in social sciences and 668 applications in life sciences. In both fields, awarded applicants perform on average better than all rejected applicants. If only the most preeminent rejected applicants are considered in both fields, they score better than the awardees on citation impact. With regard to productivity we find differences between the fields: While the awardees in life sciences outperform on average the most preeminent rejected applicants, the situation is reversed in social sciences.
"Almost automatic" and semantic integration of XML Schemas at various "severity" levels
Venue: arXiv cs.DB 2009
Year: 2009

This paper presents a novel approach for the integration of a set of XML Schemas. The proposed approach is specialized for XML, is almost automatic, semantic and "light". As a further, original, peculiarity, it is parametric w.r.t. a "severity" level against which the integration task is performed. The paper describes the approach in all details, illustrates various theoretical results, presents the experiments we have performed for testing it and, finally, compares it with various related approaches already proposed in the literature.
A Geometric Approach to Sample Compression
Venue: arXiv cs.LG 2009
Year: 2009

The Sample Compression Conjecture of Littlestone & Warmuth has remained unsolved for over two decades. This paper presents a systematic geometric investigation of the compression of finite maximum concept classes. Simple arrangements of hyperplanes in Hyperbolic space, and Piecewise-Linear hyperplane arrangements, are shown to represent maximum classes, generalizing the corresponding Euclidean result. A main result is that PL arrangements can be swept by a moving hyperplane to unlabeled d-compress any finite maximum class, forming a peeling scheme as conjectured by Kuzmin & Warmuth. A corollary is that some d-maximal classes cannot be embedded into any maximum class of VC dimension d+k, for any constant k. The construction of the PL sweeping involves Pachner moves on the one-inclusion graph, corresponding to moves of a hyperplane across the intersection of d other hyperplanes. This extends the well known Pachner moves for triangulations to cubical complexes.
Deciding Regularity of the Set of Instances of a Set of Terms with Regular Constraints is EXPTIME-Complete
Venue: arXiv cs.SC 2009
Year: 2009

Finite-state tree automata are a well studied formalism for representing term languages. This paper studies the problem of determining the regularity of the set of instances of a finite set of terms with variables, where each variable is restricted to instantiations of a regular set given by a tree automaton. The problem was recently proved decidable, but with an unknown complexity. Here, the exact complexity of the problem is determined by proving EXPTIME-completeness. The main contribution is a new, exponential time algorithm that performs various exponential transformations on the involved terms and tree automata, and decides regularity by analyzing formulas over inequality and height predicates.
Applications of the Dynamic Distance Potential Field Method
Venue: arXiv cs.MA 2009
Year: 2009

Recently the dynamic distance potential field (DDPF) was introduced as a computationally efficient method to make agents in a simulation of pedestrians move rather on the quickest path than the shortest. It can be considered to be an estimated-remaining-journey-time-based one-shot dynamic assignment method for pedestrian route choice on the operational level of dynamics. In this contribution the method is shortly introduced and the effect of the method on RiMEA's test case 11 is investigated.
Extending Firewall Session Table to Accelerate NAT, QoS Classification and Routing
Venue: arXiv cs.CR 2009
Year: 2009

security and QoS are the two most precious objectives for network systems to be attained. Unfortunately, they are in conflict, while QoS tries to minimize processing delay, strong security protection requires more processing time and cause packet delay. This article is a step towards resolving this conflict by extending the firewall session table to accelerate NAT, QoS classification, and routing processing time while providing the same level of security protection. Index Terms ? stateful packet filtering; firewall; session/state table; QoS; NAT; Routing.
Network congestion control using NetFlow
Venue: arXiv cs.NI 2009
Year: 2009

The goal of congestion control is to avoid congestion in network elements. A network element is congested if it is being offered more traffic than it can process. To detect such situations and to neutralize them we should monitor traffic in the network. In this paper, we propose using Cisco's NetFlow technology, which allows collecting statistics about traffic in the network by generating special NetFlow packets. Cisco's routers can send NetFlow packets to a special node, so we can collect these packets, analyze its content and detect network congestion. We use Cisco's feature as example, some other vendors (Juniper, 3COM, Alcatel, etc.) provide similar features for their routers. We also consider a simple system, which collects statistical information about network elements, determines overloaded elements and identifies flows, which congest them.
Similarity Measures, Author Cocitation Analysis, and Information Theory
Venue: arXiv cs.IR 2009
Year: 2009

The use of Pearson's correlation coefficient in Author Cocitation Analysis was compared with Salton's cosine measure in a number of recent contributions. Unlike the Pearson correlation, the cosine is insensitive to the number of zeros. However, one has the option of applying a logarithmic transformation in correlation analysis. Information calculus is based on both the logarithmic transformation and provides a non-parametric statistics. Using this methodology one can cluster a document set in a precise way and express the differences in terms of bits of information. The algorithm is explained and used on the data set which was made the subject of this discussion.
Covering of ordinals
Venue: arXiv cs.LO 2009
Year: 2009

The paper focuses on the structure of fundamental sequences of ordinals smaller than $ε_0$. A first result is the construction of a monadic second-order formula identifying a given structure, whereas such a formula cannot exist for ordinals themselves. The structures are precisely classified in the pushdown hierarchy. Ordinals are also located in the hierarchy, and a direct presentation is given.
A Process Calculus for Molecular Interaction Maps
Venue: arXiv cs.CE 2009
Year: 2009

We present the MIM calculus, a modeling formalism with a strong biological basis, which provides biologically-meaningful operators for representing the interaction capabilities of molecular species. The operators of the calculus are inspired by the reaction symbols used in Molecular Interaction Maps (MIMs), a diagrammatic notation used by biologists. Models of the calculus can be easily derived from MIM diagrams, for which an unambiguous and executable interpretation is thus obtained. We give a formal definition of the syntax and semantics of the MIM calculus, and we study properties of the formalism. A case study is also presented to show the use of the calculus for modeling biomolecular networks.