OpenRaiser/Intern-Atlas huggingface dataset:
Reconciling Synthesis and Decomposition: A Composite Approach to Capability Identification
Venue: arXiv cs.SE 2007
Year: 2007

Stakeholders' expectations and technology constantly evolve during the lengthy development cycles of a large-scale computer based system. Consequently, the traditional approach of baselining requirements results in an unsatisfactory system because it is ill-equipped to accommodate such change. In contrast, systems constructed on the basis of Capabilities are more change-tolerant; Capabilities are functional abstractions that are neither as amorphous as user needs nor as rigid as system requirements. Alternatively, Capabilities are aggregates that capture desired functionality from the users' needs, and are designed to exhibit desirable software engineering characteristics of high cohesion, low coupling and optimum abstraction levels. To formulate these functional abstractions we develop and investigate two algorithms for Capability identification: Synthesis and Decomposition. The synthesis algorithm aggregates detailed rudimentary elements of the system to form Capabilities. In contrast, the decomposition algorithm determines Capabilities by recursively partitioning the overall mission of the system into more detailed entities. Empirical analysis on a small computer based library system reveals that neither approach is sufficient by itself. However, a composite algorithm based on a complementary approach reconciling the two polar perspectives results in a more feasible set of Capabilities. In particular, the composite algorithm formulates Capabilities using the cohesion and coupling measures as defined by the decomposition algorithm and the abstraction level as determined by the synthesis algorithm.
Conditionally Cycle-Free Generalized Tanner Graphs: Theory and Application to High-Rate Serially Concatenated Codes
Venue: arXiv cs.IT 2007
Year: 2007

Generalized Tanner graphs have been implicitly studied by a number of authors under the rubric of generalized parity-check matrices. This work considers the conditioning of binary hidden variables in such models in order to break all cycles and thus derive optimal soft-in soft-out (SISO) decoding algorithms. Conditionally cycle-free generalized Tanner graphs are shown to imply optimal SISO decoding algorithms for the first order Reed-Muller codes and their duals - the extended Hamming codes - which are substantially less complex than conventional bit-level trellis decoding. The study of low-complexity optimal SISO decoding algorithms for the family of extended Hamming codes is practically motivated. Specifically, it is shown that exended Hamming codes offer an attractive alternative to high-rate convolutional codes in terms of both performance and complexity for use in very high-rate, very low-floor, serially concatenated coding schemes.
Object-Oriented Program Comprehension: Effect of Expertise, Task and Phase
Venue: arXiv cs.HC 2007
Year: 2007

The goal of our study is to evaluate the effect on program comprehension of three factors that have not previously been studied in a single experiment. These factors are programmer expertise (expert vs. novice), programming task (documentation vs. reuse), and the development of understanding over time (phase 1 vs. phase 2). This study is carried out in the context of the mental model approach to comprehension based on van Dijk and Kintsch's model (1983). One key aspect of this model is the distinction between two kinds of representation the reader might construct from a text: 1) the textbase, which refers to what is said in the text and how it is said, and 2) the situation model, which represents the situation referred to by the text. We have evaluated the effect of the three factors mentioned above on the development of both the textbase (or program model) and the situation model in object-oriented program comprehension. We found a four-way interaction of expertise, phase, task and type of model. For the documentation group we found that experts and novices differ in the elaboration of their situation model but not their program model. There was no interaction of expertise with phase and type of model in the documentation group. For the reuse group, there was a three-way interaction between phase, expertise and type of model. For the novice reuse group, the effect of the phase was to increase the construction of the situation model but not the program model. With respect to the task, our results show that novices do not spontaneously construct a strong situation model but are able to do so if the task demands it.
Multimodality and parallelism in design interaction: co-designers' alignment and coalitions
Venue: arXiv cs.HC 2007
Year: 2007

This paper presents an analysis of various forms of articulation between graphico-gestural and verbal modalities in parallel interactions between designers in a collaborative design situation. Based on our methodological framework, we illustrate several forms of multimodal articulations, that is, integrated and non-integrated, through extracts from a corpus on an architectural design meeting. These modes reveal alignment or disalignment between designers, with respect to the focus of their activities. They also show different forms of coalition.
An equilibrium model for matching impatient demand and patient supply over time
Venue: arXiv cs.GT 2007
Year: 2007

We present a simple dynamic equilibrium model for an online exchange where both buyers and sellers arrive according to a exogenously defined stochastic process. The structure of this exchange is motivated by the limit order book mechanism used in stock markets. Both buyers and sellers are elastic in the price-quantity space; however, only the sellers are assumed to be patient, i.e. only the sellers have a price - time elasticity, whereas the buyers are assumed to be impatient. Sellers select their selling price as a best response to all the other sellers' strategies. We define and establish the existence of the equilibrium in this model and show how to numerically compute this equilibrium. We also show how to compute other relevant quantities such as the equilibrium expected time to sale and equilibrium expected order density, as well as the expected order density conditioned on current selling price. We derive a closed form for the equilibrium distribution when the demand is price independent. At this equilibrium the selling (limit order) price distribution is power tailed as is empirically observed in order driven financial markets.
Cores of Countably Categorical Structures
Venue: arXiv cs.LO 2007
Year: 2007

A relational structure is a core, if all its endomorphisms are embeddings. This notion is important for computational complexity classification of constraint satisfaction problems. It is a fundamental fact that every finite structure has a core, i.e., has an endomorphism such that the structure induced by its image is a core; moreover, the core is unique up to isomorphism. Weprove that every ω-categorical structure has a core. Moreover, every ω-categorical structure is homomorphically equivalent to a model-complete core, which is unique up to isomorphism, and which is finite or ω-categorical. We discuss consequences for constraint satisfaction with ω-categorical templates.
Adventures in time and space
Venue: arXiv cs.LO 2007
Year: 2007

This paper investigates what is essentially a call-by-value version of PCF under a complexity-theoretically motivated type system. The programming formalism, ATR, has its first-order programs characterize the polynomial-time computable functions, and its second-order programs characterize the type-2 basic feasible functionals of Mehlhorn and of Cook and Urquhart. (The ATR-types are confined to levels 0, 1, and 2.) The type system comes in two parts, one that primarily restricts the sizes of values of expressions and a second that primarily restricts the time required to evaluate expressions. The size-restricted part is motivated by Bellantoni and Cook's and Leivant's implicit characterizations of polynomial-time. The time-restricting part is an affine version of Barber and Plotkin's DILL. Two semantics are constructed for ATR. The first is a pruning of the naive denotational semantics for ATR. This pruning removes certain functions that cause otherwise feasible forms of recursion to go wrong. The second semantics is a model for ATR's time complexity relative to a certain abstract machine. This model provides a setting for complexity recurrences arising from ATR recursions, the solutions of which yield second-order polynomial time bounds. The time-complexity semantics is also shown to be sound relative to the costs of interpretation on the abstract machine.
Flow-optimized Cooperative Transmission for the Relay Channel
Venue: arXiv cs.IT 2007
Year: 2007

This paper describes an approach for half-duplex cooperative transmission in a classical three-node relay channel. Assuming availability of channel state information at nodes, the approach makes use of this information to optimize distinct flows through the direct link from the source to the destination and the path via the relay, respectively. It is shown that such a design can effectively harness diversity advantage of the relay channel in both high-rate and low-rate scenarios. When the rate requirement is low, the proposed design gives a second-order outage diversity performance approaching that of full-duplex relaying. When the rate requirement becomes asymptotically large, the design still gives a close-to-second-order outage diversity performance. The design also achieves the best diversity-multiplexing tradeoff possible for the relay channel. With optimal long-term power control over the fading relay channel, the proposed design achieves a delay-limited rate performance that is only 3.0dB (5.4dB) worse than the capacity performance of the additive white Gaussian channel in low- (high-) rate scenarios.
Definable functions in the simply typed lambda-calculus
Venue: arXiv cs.LO 2007
Year: 2007

It is a common knowledge that the integer functions definable in simply typed lambda-calculus are exactly the extended polynomials. This is indeed the case when one interprets integers over the type (p->p)->p->p where p is a base type and/or equality is taken as beta-conversion. It is commonly believed that the same holds for beta-eta equality and for integers represented over any fixed type of the form (t->t)->t->t. In this paper we show that this opinion is not quite true. We prove that the class of functions strictly definable in simply typed lambda-calculus is considerably larger than the extended polynomials. Namely, we define F as the class of strictly definable functions and G as a class that contains extended polynomials and two additional functions, or more precisely, two function schemas, and is closed under composition. We prove that G is a subset of F. We conjecture that G exactly characterizes strictly definable functions, i.e. G=F, and we gather some evidence for this conjecture proving, for example, that every skewly representable finite range function is strictly representable over (t->t)->t->t for some t.
Secure Communication over Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

The fading broadcast channel with confidential messages (BCC) is investigated, where a source node has common information for two receivers (receivers 1 and 2), and has confidential information intended only for receiver 1. The confidential information needs to be kept as secret as possible from receiver 2. The broadcast channel from the source node to receivers 1 and 2 is corrupted by multiplicative fading gain coefficients in addition to additive Gaussian noise terms. The channel state information (CSI) is assumed to be known at both the transmitter and the receivers. The parallel BCC with independent subchannels is first studied, which serves as an information-theoretic model for the fading BCC. The secrecy capacity region of the parallel BCC is established. This result is then specialized to give the secrecy capacity region of the parallel BCC with degraded subchannels. The secrecy capacity region is then established for the parallel Gaussian BCC, and the optimal source power allocations that achieve the boundary of the secrecy capacity region are derived. In particular, the secrecy capacity region is established for the basic Gaussian BCC. The secrecy capacity results are then applied to study the fading BCC. Both the ergodic and outage performances are studied.
On the Complexity of the Numerically Definite Syllogistic and Related Fragments
Venue: arXiv cs.LO 2007
Year: 2007

In this paper, we determine the complexity of the satisfiability problem for various logics obtained by adding numerical quantifiers, and other constructions, to the traditional syllogistic. In addition, we demonstrate the incompleteness of some recently proposed proof-systems for these logics.
Cooperation Between Stations in Wireless Networks
Venue: arXiv cs.NI 2007
Year: 2007

In a wireless network, mobile nodes (MNs) repeatedly perform tasks such as layer 2 (L2) handoff, layer 3 (L3) handoff and authentication. These tasks are critical, particularly for real-time applications such as VoIP. We propose a novel approach, namely Cooperative Roaming (CR), in which MNs can collaborate with each other and share useful information about the network in which they move. We show how we can achieve seamless L2 and L3 handoffs regardless of the authentication mechanism used and without any changes to either the infrastructure or the protocol. In particular, we provide a working implementation of CR and show how, with CR, MNs can achieve a total L2+L3 handoff time of less than 16 ms in an open network and of about 21 ms in an IEEE 802.11i network. We consider behaviors typical of IEEE 802.11 networks, although many of the concepts and problems addressed here apply to any kind of mobile network.
Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability
Venue: arXiv cs.CC 2007
Year: 2007

We demonstrate a family of propositional formulas in conjunctive normal form so that a formula of size $N$ requires size $2^{Ω(\sqrt[7]{N/logN})}$ to refute using the tree-like OBDD refutation system of Atserias, Kolaitis and Vardi with respect to all variable orderings. All known symbolic quantifier elimination algorithms for satisfiability generate tree-like proofs when run on unsatisfiable CNFs, so this lower bound applies to the run-times of these algorithms. Furthermore, the lower bound generalizes earlier results on OBDD-based proofs of unsatisfiability in that it applies for all variable orderings, it applies when the clauses are processed according to an arbitrary schedule, and it applies when variables are eliminated via quantification.
Can Punctured Rate-1/2 Turbo Codes Achieve a Lower Error Floor than their Rate-1/3 Parent Codes?
Venue: arXiv cs.IT 2007
Year: 2007

In this paper we concentrate on rate-1/3 systematic parallel concatenated convolutional codes and their rate-1/2 punctured child codes. Assuming maximum-likelihood decoding over an additive white Gaussian channel, we demonstrate that a rate-1/2 non-systematic child code can exhibit a lower error floor than that of its rate-1/3 parent code, if a particular condition is met. However, assuming iterative decoding, convergence of the non-systematic code towards low bit-error rates is problematic. To alleviate this problem, we propose rate-1/2 partially-systematic codes that can still achieve a lower error floor than that of their rate-1/3 parent codes. Results obtained from extrinsic information transfer charts and simulations support our conclusion.
Tagging, Folksonomy & Co - Renaissance of Manual Indexing?
Venue: arXiv cs.IR 2007
Year: 2007

This paper gives an overview of current trends in manual indexing on the Web. Along with a general rise of user generated content there are more and more tagging systems that allow users to annotate digital resources with tags (keywords) and share their annotations with other users. Tagging is frequently seen in contrast to traditional knowledge organization systems or as something completely new. This paper shows that tagging should better be seen as a popular form of manual indexing on the Web. Difference between controlled and free indexing blurs with sufficient feedback mechanisms. A revised typology of tagging systems is presented that includes different user roles and knowledge organization systems with hierarchical relationships and vocabulary control. A detailed bibliography of current research in collaborative tagging is included.
Practical Binary Adaptive Block Coder
Venue: arXiv cs.IT 2007
Year: 2007

This paper describes design of a low-complexity algorithm for adaptive encoding/ decoding of binary sequences produced by memoryless sources. The algorithm implements universal block codes constructed for a set of contexts identified by the numbers of non-zero bits in previous bits in a sequence. We derive a precise formula for asymptotic redundancy of such codes, which refines previous well-known estimate by Krichevsky and Trofimov, and provide experimental verification of this result. In our experimental study we also compare our implementation with existing binary adaptive encoders, such as JBIG's Q-coder, and MPEG AVC (ITU-T H.264)'s CABAC algorithms.
Pseudo-codeword Landscape
Venue: arXiv cs.IT 2007
Year: 2007

We discuss the performance of Low-Density-Parity-Check (LDPC) codes decoded by means of Linear Programming (LP) at moderate and large Signal-to-Noise-Ratios (SNR). Utilizing a combination of the previously introduced pseudo-codeword-search method and a new "dendro" trick, which allows us to reduce the complexity of the LP decoding, we analyze the dependence of the Frame-Error-Rate (FER) on the SNR. Under Maximum-A-Posteriori (MAP) decoding the dendro-code, having only checks with connectivity degree three, performs identically to its original code with high-connectivity checks. For a number of popular LDPC codes performing over the Additive-White-Gaussian-Noise (AWGN) channel we found that either an error-floor sets at a relatively low SNR, or otherwise a transient asymptote, characterized by a faster decay of FER with the SNR increase, precedes the error-floor asymptote. We explain these regimes in terms of the pseudo-codeword spectra of the codes.
A Theory and Calculus for Reasoning about Sequential Behavior
Venue: arXiv cs.LO 2007
Year: 2007

Basic results in combinatorial mathematics provide the foundation for a theory and calculus for reasoning about sequential behavior. A key concept of the theory is a generalization of Boolean implicant which deals with statements of the form: A sequence of Boolean expressions alpha is an implicant of a set of sequences of Boolean expressions A This notion of a generalized implicant takes on special significance when each of the sequences in the set A describes a disallowed pattern of behavior. That is because a disallowed sequence of Boolean expressions represents a logical/temporal dependency, and because the implicants of a set of disallowed Boolean sequences A are themselves disallowed and represent precisely those dependencies that follow as a logical consequence from the dependencies represented by A. The main result of the theory is a necessary and sufficient condition for a sequence of Boolean expressions to be an implicant of a regular set of sequences of Boolean expressions. This result is the foundation for two new proof methods. Sequential resolution is a generalization of Boolean resolution which allows new logical/temporal dependencies to be inferred from existing dependencies. Normalization starts with a model (system) and a set of logical/temporal dependencies and determines which of those dependencies are satisfied by the model.
About the domino problem in the hyperbolic plane, a new solution
Venue: arXiv cs.CG 2007
Year: 2007

In this paper we improve the approach of a previous paper about the domino problem in the hyperbolic plane, see arXiv.cs.CG/0603093. This time, we prove that the general problem of the hyperbolic plane with à la Wang tiles is undecidable.
Delayed Feedback Capacity of Stationary Sources over Linear Gaussian Noise Channels
Venue: arXiv cs.IT 2007
Year: 2007

We consider a linear Gaussian noise channel used with delayed feedback. The channel noise is assumed to be a ARMA (autoregressive and/or moving average) process. We reformulate the Gaussian noise channel into an intersymbol interference channel with white noise, and show that the delayed-feedback of the original channel is equivalent to the instantaneous-feedback of the derived channel. By generalizing results previously developed for Gaussian channels with instantaneous feedback and applying them to the derived intersymbol interference channel, we show that conditioned on the delayed feedback, a conditional Gauss-Markov source achieves the feedback capacity and its Markov memory length is determined by the noise spectral order and the feedback delay. A Kalman-Bucy filter is shown to be optimal for processing the feedback. The maximal information rate for stationary sources is derived in terms of channel input power constraint and the steady state solution of the Riccati equation of the Kalman-Bucy filter used in the feedback loop.
JavaTA: A Logic-based Debugger for Java
Venue: arXiv cs.PL 2007
Year: 2007

This paper presents a logic based approach to debugging Java programs. In contrast with traditional debugging we propose a debugging methodology for Java programs using logical queries on individual execution states and also over the history of execution. These queries were arrived at by a systematic study of errors in object-oriented programs in our earlier research. We represent the salient events during the execution of a Java program by a logic database, and implement the queries as logic programs. Such an approach allows us to answer a number of useful and interesting queries about a Java program, such as the calling sequence that results in a certain outcome, the state of an object at a particular execution point, etc. Our system also provides the ability to compose new queries during a debugging session. We believe that logic programming offers a significant contribution to the art of object-oriented programs debugging.
Towards Execution Time Estimation for Logic Programs via Static Analysis and Profiling
Venue: arXiv cs.PL 2007
Year: 2007

Effective static analyses have been proposed which infer bounds on the number of resolutions or reductions. These have the advantage of being independent from the platform on which the programs are executed and have been shown to be useful in a number of applications, such as granularity control in parallel execution. On the other hand, in distributed computation scenarios where platforms with different capabilities come into play, it is necessary to express costs in metrics that include the characteristics of the platform. In particular, it is specially interesting to be able to infer upper and lower bounds on actual execution times. With this objective in mind, we propose an approach which combines compile-time analysis for cost bounds with a one-time profiling of the platform in order to determine the values of certain parameters for a given platform. These parameters calibrate a cost model which, from then on, is able to compute statically time bound functions for procedures and to predict with a significant degree of accuracy the execution times of such procedures in the given platform. The approach has been implemented and integrated in the CiaoPP system.