OpenRaiser/Intern-Atlas huggingface dataset:
A verification algorithm for Declarative Concurrent Programming
Venue: arXiv cs.DC 2006
Year: 2006

A verification method for distributed systems based on decoupling forward and backward behaviour is proposed. This method uses an event structure based algorithm that, given a CCS process, constructs its causal compression relative to a choice of observable actions. Verifying the original process equipped with distributed backtracking on non-observable actions, is equivalent to verifying its relative compression which in general is much smaller. We call this method Declarative Concurrent Programming (DCP). DCP technique compares well with direct bisimulation based methods. Benchmarks for the classic dining philosophers problem show that causal compression is rather efficient both time- and space-wise. State of the art verification tools can successfully handle more than 15 agents, whereas they can handle no more than 5 following the traditional direct method; an altogether spectacular improvement, since in this example the specification size is exponential in the number of agents.
Building a resource for studying translation shifts
Venue: arXiv cs.CL 2006
Year: 2006

This paper describes an interdisciplinary approach which brings together the fields of corpus linguistics and translation studies. It presents ongoing work on the creation of a corpus resource in which translation shifts are explicitly annotated. Translation shifts denote departures from formal correspondence between source and target text, i.e. deviations that have occurred during the translation process. A resource in which such shifts are annotated in a systematic way will make it possible to study those phenomena that need to be addressed if machine translation output is to resemble human translation. The resource described in this paper contains English source texts (parliamentary proceedings) and their German translations. The shift annotation is based on predicate-argument structures and proceeds in two steps: first, predicates and their arguments are annotated monolingually in a straightforward manner. Then, the corresponding English and German predicates and arguments are aligned with each other. Whenever a shift - mainly grammatical or semantic -has occurred, the alignment is tagged accordingly.
Fairness in Multiuser Systems with Polymatroid Capacity Region
Venue: arXiv cs.IT 2006
Year: 2006

For a wide class of multi-user systems, a subset of capacity region which includes the corner points and the sum-capacity facet has a special structure known as polymatroid. Multiaccess channels with fixed input distributions and multiple-antenna broadcast channels are examples of such systems. Any interior point of the sum-capacity facet can be achieved by time-sharing among corner points or by an alternative method known as rate-splitting. The main purpose of this paper is to find a point on the sum-capacity facet which satisfies a notion of fairness among active users. This problem is addressed in two cases: (i) where the complexity of achieving interior points is not feasible, and (ii) where the complexity of achieving interior points is feasible. For the first case, the corner point for which the minimum rate of the active users is maximized (max-min corner point) is desired for signaling. A simple greedy algorithm is introduced to find the optimum max-min corner point. For the second case, the polymatroid properties are exploited to locate a rate-vector on the sum-capacity facet which is optimally fair in the sense that the minimum rate among all users is maximized (max-min rate). In the case that the rate of some users can not increase further (attain the max-min value), the algorithm recursively maximizes the minimum rate among the rest of the users. It is shown that the problems of deriving the time-sharing coefficients or rate-spitting scheme can be solved by decomposing the problem to some lower-dimensional subproblems. In addition, a fast algorithm to compute the time-sharing coefficients to attain a general point on the sum-capacity facet is proposed.
A common framework for aspect mining based on crosscutting concern sorts
Venue: arXiv cs.SE 2006
Year: 2006

The increasing number of aspect mining techniques proposed in literature calls for a methodological way of comparing and combining them in order to assess, and improve on, their quality. This paper addresses this situation by proposing a common framework based on crosscutting concern sorts which allows for consistent assessment, comparison and combination of aspect mining techniques. The framework identifies a set of requirements that ensure homogeneity in formulating the mining goals, presenting the results and assessing their quality. We demonstrate feasibility of the approach by retrofitting an existing aspect mining technique to the framework, and by using it to design and implement two new mining techniques. We apply the three techniques to a known aspect mining benchmark and show how they can be consistently assessed and combined to increase the quality of the results. The techniques and combinations are implemented in FINT, our publicly available free aspect mining tool.
Hidden Markov Process: A New Representation, Entropy Rate and Estimation Entropy
Venue: arXiv cs.IT 2006
Year: 2006

We consider a pair of correlated processes {Z_n} and {S_n} (two sided), where the former is observable and the later is hidden. The uncertainty in the estimation of Z_n upon its finite past history is H(Z_n|Z_0^{n-1}), and for estimation of S_n upon this observation is H(S_n|Z_0^{n-1}), which are both sequences of n. The limits of these sequences (and their existence) are of practical and theoretical interest. The first limit, if exists, is the entropy rate. We call the second limit the estimation entropy. An example of a process jointly correlated to another one is the hidden Markov process. It is the memoryless observation of the Markov state process where state transitions are independent of past observations. We consider a new representation of hidden Markov process using iterated function system. In this representation the state transitions are deterministically related to the process. This representation provides a unified framework for the analysis of the two limiting entropies for this process, resulting in integral expressions for the limits. This analysis shows that under mild conditions the limits exist and provides a simple method for calculating the elements of the corresponding sequences.
On symmetric sandpiles
Venue: arXiv cs.CC 2006
Year: 2006

A symmetric version of the well-known SPM model for sandpiles is introduced. We prove that the new model has fixed point dynamics. Although there might be several fixed points, a precise description of the fixed points is given. Moreover, we provide a simple closed formula for counting the number of fixed points originated by initial conditions made of a single column of grains.
Coding for Parallel Channels: Gallager Bounds for Binary Linear Codes with Applications to Repeat-Accumulate Codes and Variations
Venue: arXiv cs.IT 2006
Year: 2006

This paper is focused on the performance analysis of binary linear block codes (or ensembles) whose transmission takes place over independent and memoryless parallel channels. New upper bounds on the maximum-likelihood (ML) decoding error probability are derived. These bounds are applied to various ensembles of turbo-like codes, focusing especially on repeat-accumulate codes and their recent variations which possess low encoding and decoding complexity and exhibit remarkable performance under iterative decoding. The framework of the second version of the Duman and Salehi (DS2) bounds is generalized to the case of parallel channels, along with the derivation of their optimized tilting measures. The connection between the generalized DS2 and the 1961 Gallager bounds, addressed by Divsalar and by Sason and Shamai for a single channel, is explored in the case of an arbitrary number of independent parallel channels. The generalization of the DS2 bound for parallel channels enables to re-derive specific bounds which were originally derived by Liu et al. as special cases of the Gallager bound. In the asymptotic case where we let the block length tend to infinity, the new bounds are used to obtain improved inner bounds on the attainable channel regions under ML decoding. The tightness of the new bounds for independent parallel channels is exemplified for structured ensembles of turbo-like codes. The improved bounds with their optimized tilting measures show, irrespectively of the block length of the codes, an improvement over the union bound and other previously reported bounds for independent parallel channels; this improvement is especially pronounced for moderate to large block lengths.
On the Error Exponents of Some Improved Tangential-Sphere Bounds
Venue: arXiv cs.IT 2006
Year: 2006

The performance of maximum-likelihood (ML) decoded binary linear block codes over the AWGN channel is addressed via the tangential-sphere bound (TSB) and two of its recent improved versions. The paper is focused on the derivation of the error exponents of these bounds. Although it was exemplified that some recent improvements of the TSB tighten this bound for finite-length codes, it is demonstrated in this paper that their error exponents coincide. For an arbitrary ensemble of binary linear block codes, the common value of these error exponents is explicitly expressed in terms of the asymptotic growth rate of the average distance spectrum.
Almost Periodicity, Finite Automata Mappings and Related Effectiveness Issues
Venue: arXiv cs.DM 2006
Year: 2006

The paper studies different variants of almost periodicity notion. We introduce the class of eventually strongly almost periodic sequences where some suffix is strongly almost periodic (=uniformly recurrent). The class of almost periodic sequences includes the class of eventually strongly almost periodic sequences, and we prove this inclusion to be strict. We prove that the class of eventually strongly almost periodic sequences is closed under finite automata mappings and finite transducers. Moreover, an effective form of this result is presented. Finally we consider some algorithmic questions concerning almost periodicity.
Database Querying under Changing Preferences
Venue: arXiv cs.DB 2006
Year: 2006

We present here a formal foundation for an iterative and incremental approach to constructing and evaluating preference queries. Our main focus is on query modification: a query transformation approach which works by revising the preference relation in the query. We provide a detailed analysis of the cases where the order-theoretic properties of the preference relation are preserved by the revision. We consider a number of different revision operators: union, prioritized and Pareto composition. We also formulate algebraic laws that enable incremental evaluation of preference queries. Finally, we consider two variations of the basic framework: finite restrictions of preference relations and weak-order extensions of strict partial order preference relations.
Performance of STBC MC-CDMA systems over outdoor realistic MIMO channels
Venue: arXiv cs.IT 2006
Year: 2006

The paper deals with orthogonal space-time block coded MC-CDMA systems in outdoor realistic downlink scenarios with up to two transmit and receive antennas. Assuming no channel state information at the transmitter, we compare several linear single-user detection and spreading schemes, with or without channel coding, achieving a spectral efficiency of 1-2 bits/s/Hz. The different results obtained demonstrate that spatial diversity significantly improves the performance of MC-CDMA systems, and allows different chip-mapping without notably decreasing performance. Moreover, the global system exhibits a good trade-off between complexity at mobile stations and performance. Then, Alamouti's STBC MC-CDMA schemes derive full benefit from the frequency and spatial diversities and can be considered as a very realistic and promising candidate for the air interface downlink of the 4/sup th/ generation mobile radio systems.
Ten Incredibly Dangerous Software Ideas
Venue: arXiv cs.GL 2006
Year: 2006

This is a rough draft synopsis of a book presently in preparation. This book provides a systematic critique of the software industry. This critique is accomplished using classical methods in practical design science.
A general computation rule for lossy summaries/messages with examples from equalization
Venue: arXiv cs.IT 2006
Year: 2006

Elaborating on prior work by Minka, we formulate a general computation rule for lossy messages. An important special case (with many applications in communications) is the conversion of "soft-bit" messages to Gaussian messages. By this method, the performance of a Kalman equalizer is improved, both for uncoded and coded transmission.
Towards a General Theory of Simultaneous Diophantine Approximation of Formal Power Series: Multidimensional Linear Complexity
Venue: arXiv cs.IT 2006
Year: 2006

We model the development of the linear complexity of multisequences by a stochastic infinite state machine, the Battery-Discharge-Model, BDM. The states s in S of the BDM have asymptotic probabilities or mass Pr(s)=1/(P(q,M) q^K(s)), where K(s) in N_0 is the class of the state s, and P(q,M)=\sum_(K in\N0) P_M(K)q^(-K)=\prod_(i=1..M) q^i/(q^i-1) is the generating function of the number of partitions into at most M parts. We have (for each timestep modulo M+1) just P_M(K) states of class K \. We obtain a closed formula for the asymptotic probability for the linear complexity deviation d(n) := L(n)-\lceil n\cdot M/(M+1)\rceil with Pr(d)=O(q^(-|d|(M+1))), for M in N, for d in Z. The precise formula is given in the text. It has been verified numerically for M=1..8, and is conjectured to hold for all M in N. From the asymptotic growth (proven for all M in N), we infer the Law of the Logarithm for the linear complexity deviation, -liminf_{n\to\infty} d_a(n) / log n = 1 /((M+1)log q) = limsup_{n\to\infty} d_a(n) / log n, which immediately yields L_a(n)/n \to M/(M+1) with measure one, for all M in N, a result recently shown already by Niederreiter and Wang. Keywords: Linear complexity, linear complexity deviation, multisequence, Battery Discharge Model, isometry.
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
Venue: arXiv cs.CC 2006
Year: 2006

We prove that every triconnected planar graph is definable by a first order sentence that uses at most 15 variables and has quantifier depth at most $11\log_2 n+43$. As a consequence, a canonic form of such graphs is computable in $AC^1$ by the 14-dimensional Weisfeiler-Lehman algorithm. This provides another way to show that the planar graph isomorphism is solvable in $AC^1$.
Set-Theoretic Preliminaries for Computer Scientists
Venue: arXiv cs.DM 2006
Year: 2006

The basics of set theory are usually copied, directly or indirectly, by computer scientists from introductions to mathematical texts. Often mathematicians are content with special cases when the general case is of no mathematical interest. But sometimes what is of no mathematical interest is of great practical interest in computer science. For example, non-binary relations in mathematics tend to have numerical indexes and tend to be unsorted. In the theory and practice of relational databases both these simplifications are unwarranted. In response to this situation we present here an alternative to the ``set-theoretic preliminaries'' usually found in computer science texts. This paper separates binary relations from the kind of relations that are needed in relational databases. Its treatment of functions supports both computer science in general and the kind of relations needed in databases. As a sample application this paper shows how the mathematical theory of relations naturally leads to the relational data model and how the operations on relations are by themselves already a powerful vehicle for queries.
Use of UML and Model Transformations for Workflow Process Definitions
Venue: arXiv cs.SE 2006
Year: 2006

Currently many different modeling languages are used for workflow definitions in BPM systems. Authors of this paper analyze the two most popular graphical languages, with highest possibility of wide practical usage - UML Activity diagrams (AD) and Business Process Modeling Notation (BPMN). The necessary in practice workflow aspects are briefly discussed, and on this basis a natural AD profile is proposed, which covers all of them. A functionally equivalent BPMN subset is also selected. The semantics of both languages in the context of process execution (namely, mapping to BPEL) is also analyzed in the paper. By analyzing AD and BPMN metamodels, authors conclude that an exact transformation from AD to BPMN is not trivial even for the selected subset, though these languages are considered to be similar. Authors show how this transformation could be defined in the MOLA transformation language.
Circle Formation of Weak Mobile Robots
Venue: arXiv cs.RO 2006
Year: 2006

In this paper we prove the conjecture of Défago & Konagaya. Furthermore, we describe a deterministic protocol for forming a regular n-gon in finite time.
Competing with stationary prediction strategies
Venue: arXiv cs.LG 2006
Year: 2006

In this paper we introduce the class of stationary prediction strategies and construct a prediction algorithm that asymptotically performs as well as the best continuous stationary strategy. We make mild compactness assumptions but no stochastic assumptions about the environment. In particular, no assumption of stationarity is made about the environment, and the stationarity of the considered strategies only means that they do not depend explicitly on time; we argue that it is natural to consider only stationary strategies even for highly non-stationary environments.
Fault-Tolerant Real-Time Streaming with FEC thanks to Capillary Multi-Path Routing
Venue: arXiv cs.NI 2006
Year: 2006

Erasure resilient FEC codes in off-line packetized streaming rely on time diversity. This requires unrestricted buffering time at the receiver. In real-time streaming the playback buffering time must be very short. Path diversity is an orthogonal strategy. However, the large number of long paths increases the number of underlying links and consecutively the overall link failure rate. This may increase the overall requirement in redundant FEC packets for combating the link failures. We introduce the Redundancy Overall Requirement (ROR) metric, a routing coefficient specifying the total number of FEC packets required for compensation of all underlying link failures. We present a capillary routing algorithm for constructing layer by layer steadily diversifying multi-path routing patterns. By measuring the ROR coefficients of a dozen of routing layers on hundreds of network samples, we show that the number of required FEC packets decreases substantially when the path diversity is increased by the capillary routing construction algorithm.
New Model of Internet Topology Using k-shell Decomposition
Venue: arXiv cs.NI 2006
Year: 2006

We introduce and use k-shell decomposition to investigate the topology of the Internet at the AS level. Our analysis separates the Internet into three sub-components: (a) a nucleus which is a small (~100 nodes) very well connected globally distributed subgraph; (b) a fractal sub-component that is able to connect the bulk of the Internet without congesting the nucleus, with self similar properties and critical exponents; and (c) dendrite-like structures, usually isolated nodes that are connected to the rest of the network through the nucleus only. This unique decomposition is robust, and provides insight into the underlying structure of the Internet and its functional consequences. Our approach is general and useful also when studying other complex networks.
About Norms and Causes
Venue: arXiv cs.AI 2006
Year: 2006

Knowing the norms of a domain is crucial, but there exist no repository of norms. We propose a method to extract them from texts: texts generally do not describe a norm, but rather how a state-of-affairs differs from it. Answers concerning the cause of the state-of-affairs described often reveal the implicit norm. We apply this idea to the domain of driving, and validate it by designing algorithms that identify, in a text, the "basic" norms to which it refers implicitly.
Ideas by Statistical Mechanics (ISM)
Venue: arXiv cs.CE 2006
Year: 2006

Ideas by Statistical Mechanics (ISM) is a generic program to model evolution and propagation of ideas/patterns throughout populations subjected to endogenous and exogenous interactions. The program is based on the author's work in Statistical Mechanics of Neocortical Interactions (SMNI), and uses the author's Adaptive Simulated Annealing (ASA) code for optimizations of training sets, as well as for importance-sampling to apply the author's copula financial risk-management codes, Trading in Risk Dimensions (TRD), for assessments of risk and uncertainty. This product can be used for decision support for projects ranging from diplomatic, information, military, and economic (DIME) factors of propagation/evolution of ideas, to commercial sales, trading indicators across sectors of financial markets, advertising and political campaigns, etc. A statistical mechanical model of neocortical interactions, developed by the author and tested successfully in describing short-term memory and EEG indicators, is the proposed model. Parameters with a given subset of macrocolumns will be fit using ASA to patterns representing ideas. Parameters of external and inter-regional interactions will be determined that promote or inhibit the spread of these ideas. Tools of financial risk management, developed by the author to process correlated multivariate systems with differing non-Gaussian distributions using modern copula analysis, importance-sampled using ASA, will enable bona fide correlations and uncertainties of success and failure to be calculated. Marginal distributions will be evolved to determine their expected duration and stability using algorithms developed by the author, i.e., PATHTREE and PATHINT codes.
Reducing the Computation of Linear Complexities of Periodic Sequences over $GF(p^m)$
Venue: arXiv cs.CR 2006
Year: 2006

The linear complexity of a periodic sequence over $GF(p^m)$ plays an important role in cryptography and communication [12]. In this correspondence, we prove a result which reduces the computation of the linear complexity and minimal connection polynomial of a period $un$ sequence over $GF(p^m)$ to the computation of the linear complexities and minimal connection polynomials of $u$ period $n$ sequences. The conditions $u|p^m-1$ and $\gcd(n,p^m-1)=1$ are required for the result to hold. Some applications of this reduction in fast algorithms to determine the linear complexities and minimal connection polynomials of sequences over $GF(p^m)$ are presented.