OpenRaiser/Intern-Atlas huggingface dataset:
Processing Uncertainty and Indeterminacy in Information Systems success mapping
Venue: arXiv cs.AI 2005
Year: 2005

IS success is a complex concept, and its evaluation is complicated, unstructured and not readily quantifiable. Numerous scientific publications address the issue of success in the IS field as well as in other fields. But, little efforts have been done for processing indeterminacy and uncertainty in success research. This paper shows a formal method for mapping success using Neutrosophic Success Map. This is an emerging tool for processing indeterminacy and uncertainty in success research. EIS success have been analyzed using this tool.
High-Throughput SNP Genotyping by SBE/SBH
Venue: arXiv cs.DS 2005
Year: 2005

Despite much progress over the past decade, current Single Nucleotide Polymorphism (SNP) genotyping technologies still offer an insufficient degree of multiplexing when required to handle user-selected sets of SNPs. In this paper we propose a new genotyping assay architecture combining multiplexed solution-phase single-base extension (SBE) reactions with sequencing by hybridization (SBH) using universal DNA arrays such as all $k$-mer arrays. In addition to PCR amplification of genomic DNA, SNP genotyping using SBE/SBH assays involves the following steps: (1) Synthesizing primers complementing the genomic sequence immediately preceding SNPs of interest; (2) Hybridizing these primers with the genomic DNA; (3) Extending each primer by a single base using polymerase enzyme and dideoxynucleotides labeled with 4 different fluorescent dyes; and finally (4) Hybridizing extended primers to a universal DNA array and determining the identity of the bases that extend each primer by hybridization pattern analysis. Our contributions include a study of multiplexing algorithms for SBE/SBH genotyping assays and preliminary experimental results showing the achievable tradeoffs between the number of array probes and primer length on one hand and the number of SNPs that can be assayed simultaneously on the other. Simulation results on datasets both randomly generated and extracted from the NCBI dbSNP database suggest that the SBE/SBH architecture provides a flexible and cost-effective alternative to genotyping assays currently used in the industry, enabling genotyping of up to hundreds of thousands of user-specified SNPs per assay.
Resource Control for Synchronous Cooperative Threads
Venue: arXiv cs.PL 2005
Year: 2005

We develop new methods to statically bound the resources needed for the execution of systems of concurrent, interactive threads. Our study is concerned with a \emph{synchronous} model of interaction based on cooperative threads whose execution proceeds in synchronous rounds called instants. Our contribution is a system of compositional static analyses to guarantee that each instant terminates and to bound the size of the values computed by the system as a function of the size of its parameters at the beginning of the instant. Our method generalises an approach designed for first-order functional languages that relies on a combination of standard termination techniques for term rewriting systems and an analysis of the size of the computed values based on the notion of quasi-interpretation. We show that these two methods can be combined to obtain an explicit polynomial bound on the resources needed for the execution of the system during an instant. As a second contribution, we introduce a virtual machine and a related bytecode thus producing a precise description of the resources needed for the execution of a system. In this context, we present a suitable control flow analysis that allows to formulte the static analyses for resource control at byte code level.
Reactive concurrent programming revisited
Venue: arXiv cs.PL 2005
Year: 2005

In this note we revisit the so-called reactive programming style, which evolves from the synchronous programming model of the Esterel language by weakening the assumption that the absence of an event can be detected instantaneously. We review some research directions that have been explored since the emergence of the reactive model ten years ago. We shall also outline some questions that remain to be investigated.
Reconstructing Websites for the Lazy Webmaster
Venue: arXiv cs.IR 2005
Year: 2005

Backup or preservation of websites is often not considered until after a catastrophic event has occurred. In the face of complete website loss, "lazy" webmasters or concerned third parties may be able to recover some of their website from the Internet Archive. Other pages may also be salvaged from commercial search engine caches. We introduce the concept of "lazy preservation"- digital preservation performed as a result of the normal operations of the Web infrastructure (search engines and caches). We present Warrick, a tool to automate the process of website reconstruction from the Internet Archive, Google, MSN and Yahoo. Using Warrick, we have reconstructed 24 websites of varying sizes and composition to demonstrate the feasibility and limitations of website reconstruction from the public Web infrastructure. To measure Warrick's window of opportunity, we have profiled the time required for new Web resources to enter and leave search engine caches.
The Limits of Motion Prediction Support for Ad hoc Wireless Network Performance
Venue: arXiv cs.NI 2005
Year: 2005

A fundamental understanding of gain provided by motion prediction in wireless ad hoc routing is currently lacking. This paper examines benefits in routing obtainable via prediction. A theoretical best-case non-predictive routing model is quantified in terms of both message overhead and update time for non-predictive routing. This best- case model of existing routing performance is compared with predictive routing. Several specific instances of predictive improvements in routing are examined. The primary contribution of this paper is quantification of predictive gain for wireless ad hoc routing.
Low-Energy Sensor Network Time Synchronization as an Emergent Property
Venue: arXiv cs.NI 2005
Year: 2005

The primary contribution of this work is to examine the energy efficiency of pulse coupled oscillation for time synchronization in a realistic wireless network environment and to explore the impact of mobility on convergence rate. Energy coupled oscillation is susceptible to interference; this approach uses reception and decoding of short packet bursts to eliminate this problem. The energy efficiency of a commonly used timestamp broadcast algorithm is compared and contrasted with pulse-coupled oscillation. The emergent pulse coupled oscillation technique shows greater energy efficiency as well as robustness with mobility. A proportion of the sensors may be integrated with GPS receivers in order to obtain a master clock time.
The Internet AS-Level Topology: Three Data Sources and One Definitive Metric
Venue: arXiv cs.NI 2005
Year: 2005

We calculate an extensive set of characteristics for Internet AS topologies extracted from the three data sources most frequently used by the research community: traceroutes, BGP, and WHOIS. We discover that traceroute and BGP topologies are similar to one another but differ substantially from the WHOIS topology. Among the widely considered metrics, we find that the joint degree distribution appears to fundamentally characterize Internet AS topologies as well as narrowly define values for other important metrics. We discuss the interplay between the specifics of the three data collection mechanisms and the resulting topology views. In particular, we show how the data collection peculiarities explain differences in the resulting joint degree distributions of the respective topologies. Finally, we release to the community the input topology datasets, along with the scripts and output of our calculations. This supplement should enable researchers to validate their models against real data and to make more informed selection of topology data sources for their specific needs.
Efficient generation of rotating workforce schedules
Venue: arXiv cs.OH 2006
Year: 2006

Generating high-quality schedules for a rotating workforce is a critical task in all settings where a certain staffing level must be guaranteed beyond the capacity of single employees, such as for instance in industrial plants, hospitals, or airline companies. Results from ergonomics \cite{BEST91} indicate that rotating workforce schedules have a profound impact on the health and social life of employees as well as on their performance at work. Moreover, rotating workforce schedules must satisfy legal requirements and should also meet the objectives of the employing organization. We describe our solution to this problem. A basic design decision was to aim at quickly obtaining high-quality schedules for realistically sized problems while maintaining human control. The interaction between the decision maker and the algorithm therefore consists in four steps: (1) choosing a set of lengths of work blocks (a work block is a sequence of consecutive days of work shifts), (2) choosing a particular sequence of work and days-off blocks among those that have optimal weekend characteristics, (3) enumerating possible shift sequences for the chosen work blocks subject to shift change constraints and bounds on sequences of shifts, and (4) assignment of shift sequences to work blocks while fulfilling the staffing requirements. The combination of constraint satisfaction and problem-oriented intelligent backtracking algorithms in each of the four steps allows to find good solutions for real-world problems in acceptable time. Computational results from real-world problems and from benchmark examples found in the literature confirm the viability of our approach. The algorithms are now part of a commercial shift scheduling software package.
Splitting an operator: Algebraic modularity results for logics with fixpoint semantics
Venue: arXiv cs.AI 2006
Year: 2006

It is well known that, under certain conditions, it is possible to split logic programs under stable model semantics, i.e. to divide such a program into a number of different "levels", such that the models of the entire program can be constructed by incrementally constructing models for each level. Similar results exist for other non-monotonic formalisms, such as auto-epistemic logic and default logic. In this work, we present a general, algebraicsplitting theory for logics with a fixpoint semantics. Together with the framework of approximation theory, a general fixpoint theory for arbitrary operators, this gives us a uniform and powerful way of deriving splitting results for each logic with a fixpoint semantics. We demonstrate the usefulness of these results, by generalizing existing results for logic programming, auto-epistemic logic and default logic.
Erratum : MCColor is not optimal on Meyniel graphs
Venue: arXiv cs.DM 2006
Year: 2006

A Meyniel graph is a graph in which every odd cycle of length at least five has two chords. In the manuscript "Coloring Meyniel graphs in linear time" we claimed that our algorithm MCColor produces an optimal coloring for every Meyniel graph. But later we found a mistake in the proof and a couterexample to the optimality, which we present here. MCColor can still be used to find a stable set that intersects all maximal cliques of a Meyniel graph in linear time. Consequently it can be used to find an optimal coloring in time O(nm), and the same holds for Algorithm MCS+Color. This is explained in the manuscript "A linear algorithm to find a strong stable set in a Meyniel graph" but this is equivalent to Hertz's algorithm. The current best algorithm for coloring Meyniel graphs is the O(n^2) algorithm LexColor due to Roussel and Rusu. The question of finding a linear-time algorithm to color Meyniel graphs is still open.
Fast Simulation of Multicomponent Dynamic Systems
Venue: arXiv cs.DS 2006
Year: 2006

A computer simulation has to be fast to be helpful, if it is employed to study the behavior of a multicomponent dynamic system. This paper discusses modeling concepts and algorithmic techniques useful for creating such fast simulations. Concrete examples of simulations that range from econometric modeling to communications to material science are used to illustrate these techniques and concepts. The algorithmic and modeling methods discussed include event-driven processing, ``anticipating'' data structures, and ``lazy'' evaluation, Poisson dispenser, parallel processing by cautious advancements and by synchronous relaxations. The paper gives examples of how these techniques and models are employed in assessing efficiency of capacity management methods in wireless and wired networks, in studies of magnetization, crystalline structure, and sediment formation in material science, in studies of competition in economics.
Balanced Overlay Networks (BON): Decentralized Load Balancing via Self-Organized Random Networks
Venue: arXiv cs.DC 2006
Year: 2006

We present a novel framework, called balanced overlay networks (BON), that provides scalable, decentralized load balancing for distributed computing using large-scale pools of heterogeneous computers. Fundamentally, BON encodes the information about each node's available computational resources in the structure of the links connecting the nodes in the network. This distributed encoding is self-organized, with each node managing its in-degree and local connectivity via random-walk sampling. Assignment of incoming jobs to nodes with the most free resources is also accomplished by sampling the nodes via short random walks. Extensive simulations show that the resulting highly dynamic and self-organized graph structure can efficiently balance computational load throughout large-scale networks. These simulations cover a wide spectrum of cases, including significant heterogeneity in available computing resources and high burstiness in incoming load. We provide analytical results that prove BON's scalability for truly large-scale networks: in particular we show that under certain ideal conditions, the network structure converges to Erdos-Renyi (ER) random graphs; our simulation results, however, show that the algorithm does much better, and the structures seem to approach the ideal case of d-regular random graphs. We also make a connection between highly-loaded BONs and the well-known ball-bin randomized load balancing framework.
Labelled transition systems as a Stone space
Venue: arXiv cs.LO 2006
Year: 2006

A fully abstract and universal domain model for modal transition systems and refinement is shown to be a maximal-points space model for the bisimulation quotient of labelled transition systems over a finite set of events. In this domain model we prove that this quotient is a Stone space whose compact, zero-dimensional, and ultra-metrizable Hausdorff topology measures the degree of bisimilarity such that image-finite labelled transition systems are dense. Using this compactness we show that the set of labelled transition systems that refine a modal transition system, its ''set of implementations'', is compact and derive a compactness theorem for Hennessy-Milner logic on such implementation sets. These results extend to systems that also have partially specified state propositions, unify existing denotational, operational, and metric semantics on partial processes, render robust consistency measures for modal transition systems, and yield an abstract interpretation of compact sets of labelled transition systems as Scott-closed sets of modal transition systems.
Minimum-Cost Multicast over Coded Packet Networks
Venue: arXiv cs.IT 2006
Year: 2006

We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e. packet networks where the contents of outgoing packets are arbitrary, causal functions of the contents of received packets. We consider both wireline and wireless packet networks as well as both static multicast (where membership of the multicast group remains constant for the duration of the connection) and dynamic multicast (where membership of the multicast group changes in time, with nodes joining and leaving the group). For static multicast, we reduce the problem to a polynomial-time solvable optimization problem, and we present decentralized algorithms for solving it. These algorithms, when coupled with existing decentralized schemes for constructing network codes, yield a fully decentralized approach for achieving minimum-cost multicast. By contrast, establishing minimum-cost static multicast connections over routed packet networks is a very difficult problem even using centralized computation, except in the special cases of unicast and broadcast connections. For dynamic multicast, we reduce the problem to a dynamic programming problem and apply the theory of dynamic programming to suggest how it may be solved.
Theories for TC0 and Other Small Complexity Classes
Venue: arXiv cs.LO 2006
Year: 2006

We present a general method for introducing finitely axiomatizable "minimal" two-sorted theories for various subclasses of P (problems solvable in polynomial time). The two sorts are natural numbers and finite sets of natural numbers. The latter are essentially the finite binary strings, which provide a natural domain for defining the functions and sets in small complexity classes. We concentrate on the complexity class TC^0, whose problems are defined by uniform polynomial-size families of bounded-depth Boolean circuits with majority gates. We present an elegant theory VTC^0 in which the provably-total functions are those associated with TC^0, and then prove that VTC^0 is "isomorphic" to a different-looking single-sorted theory introduced by Johannsen and Pollet. The most technical part of the isomorphism proof is defining binary number multiplication in terms a bit-counting function, and showing how to formalize the proofs of its algebraic properties.
Broadcast Channels with Cooperating Decoders
Venue: arXiv cs.IT 2006
Year: 2006

We consider the problem of communicating over the general discrete memoryless broadcast channel (BC) with partially cooperating receivers. In our setup, receivers are able to exchange messages over noiseless conference links of finite capacities, prior to decoding the messages sent from the transmitter. In this paper we formulate the general problem of broadcast with cooperation. We first find the capacity region for the case where the BC is physically degraded. Then, we give achievability results for the general broadcast channel, for both the two independent messages case and the single common message case.
On Searching a Table Consistent with Division Poset
Venue: arXiv cs.DM 2006
Year: 2006

Suppose $P_n=\{1,2,...,n\}$ is a partially ordered set with the partial order defined by divisibility, that is, for any two distinct elements $i,j\in P_n$ satisfying $i$ divides $j$, $i<_{P_n} j$. A table $A_n=\{a_i|i=1,2,...,n\}$ of distinct real numbers is said to be \emph{consistent} with $P_n$, provided for any two distinct elements $i,j\in \{1,2,...,n\}$ satisfying $i$ divides $j$, $a_i< a_j$. Given an real number $x$, we want to determine whether $x\in A_n$, by comparing $x$ with as few entries of $A_n$ as possible. In this paper we investigate the complexity $τ(n)$, measured in the number of comparisons, of the above search problem. We present a $\frac{55n}{72}+O(\ln^2 n)$ search algorithm for $A_n$ and prove a lower bound $({3/4}+{17/2160})n+O(1)$ on $τ(n)$ by using an adversary argument.
State-Based Control of Fuzzy Discrete Event Systems
Venue: arXiv cs.DM 2006
Year: 2006

To effectively represent possibility arising from states and dynamics of a system, fuzzy discrete event systems as a generalization of conventional discrete event systems have been introduced recently. Supervisory control theory based on event feedback has been well established for such systems. Noting that the system state description, from the viewpoint of specification, seems more convenient, we investigate the state-based control of fuzzy discrete event systems in this paper. We first present an approach to finding all fuzzy states that are reachable by controlling the system. After introducing the notion of controllability for fuzzy states, we then provide a necessary and sufficient condition for a set of fuzzy states to be controllable. We also find that event-based control and state-based control are not equivalent and further discuss the relationship between them. Finally, we examine the possibility of driving a fuzzy discrete event system under control from a given initial state to a prescribed set of fuzzy states and then keeping it there indefinitely.
Optimal Relay Functionality for SNR Maximization in Memoryless Relay Networks
Venue: arXiv cs.IT 2006
Year: 2006

We explore the SNR-optimal relay functionality in a \emph{memoryless} relay network, i.e. a network where, during each channel use, the signal transmitted by a relay depends only on the last received symbol at that relay. We develop a generalized notion of SNR for the class of memoryless relay functions. The solution to the generalized SNR optimization problem leads to the novel concept of minimum mean square uncorrelated error estimation(MMSUEE). For the elemental case of a single relay, we show that MMSUEE is the SNR-optimal memoryless relay function regardless of the source and relay transmit power, and the modulation scheme. This scheme, that we call estimate and forward (EF), is also shown to be SNR-optimal with PSK modulation in a parallel relay network. We demonstrate that EF performs better than the best of amplify and forward (AF) and demodulate and forward (DF), in both parallel and serial relay networks. We also determine that AF is near-optimal at low transmit power in a parallel network, while DF is near-optimal at high transmit power in a serial network. For hybrid networks that contain both serial and parallel elements, and when robust performance is desired, the advantage of EF over the best of AF and DF is found to be significant. Error probabilities are provided to substantiate the performance gain obtained through SNR optimality. We also show that, for \emph{Gaussian} inputs, AF, DF and EF become identical.
Geometrical relations between space time block code designs and complexity reduction
Venue: arXiv cs.IT 2006
Year: 2006

In this work, the geometric relation between space time block code design for the coherent channel and its non-coherent counterpart is exploited to get an analogue of the information theoretic inequality $I(X;S)\le I((X,H);S)$ in terms of diversity. It provides a lower bound on the performance of non-coherent codes when used in coherent scenarios. This leads in turn to a code design decomposition result splitting coherent code design into two complexity reduced sub tasks. Moreover a geometrical criterion for high performance space time code design is derived.