OpenRaiser/Intern-Atlas huggingface dataset:
The topology of covert conflict
Venue: arXiv cs.NI 2006
Year: 2006

Often an attacker tries to disconnect a network by destroying nodes or edges, while the defender counters using various resilience mechanisms. Examples include a music industry body attempting to close down a peer-to-peer file-sharing network; medics attempting to halt the spread of an infectious disease by selective vaccination; and a police agency trying to decapitate a terrorist organisation. Albert, Jeong and Barabasi famously analysed the static case, and showed that vertex-order attacks are effective against scale-free networks. We extend this work to the dynamic case by developing a framework based on evolutionary game theory to explore the interaction of attack and defence strategies. We show, first, that naive defences don't work against vertex-order attack; second, that defences based on simple redundancy don't work much better, but that defences based on cliques work well; third, that attacks based on centrality work better against clique defences than vertex-order attacks do; and fourth, that defences based on complex strategies such as delegation plus clique resist centrality attacks better than simple clique defences. Our models thus build a bridge between network analysis and evolutionary game theory, and provide a framework for analysing defence and attack in networks where topology matters. They suggest definitions of efficiency of attack and defence, and may even explain the evolution of insurgent organisations from networks of cells to a more virtual leadership that facilitates operations rather than directing them. Finally, we draw some conclusions and present possible directions for future research.
Decision Making with Side Information and Unbounded Loss Functions
Venue: arXiv cs.LG 2006
Year: 2006

We consider the problem of decision-making with side information and unbounded loss functions. Inspired by probably approximately correct learning model, we use a slightly different model that incorporates the notion of side information in a more generic form to make it applicable to a broader class of applications including parameter estimation and system identification. We address sufficient conditions for consistent decision-making with exponential convergence behavior. In this regard, besides a certain condition on the growth function of the class of loss functions, it suffices that the class of loss functions be dominated by a measurable function whose exponential Orlicz expectation is uniformly bounded over the probabilistic model. Decay exponent, decay constant, and sample complexity are discussed. Example applications to method of moments, maximum likelihood estimation, and system identification are illustrated, as well.
Query-Monotonic Turing Reductions
Venue: arXiv cs.CC 2006
Year: 2006

We study reductions that limit the extreme adaptivity of Turing reductions. In particular, we study reductions that make a rapid, structured progression through the set to which they are reducing: Each query is strictly longer (shorter) than the previous one. We call these reductions query-increasing (query-decreasing) Turing reductions. We also study query-nonincreasing (query-nondecreasing) Turing reductions. These are Turing reductions in which the sequence of query lengths is nonincreasing (nondecreasing). We ask whether these restrictions in fact limit the power of reductions. We prove that query-increasing and query-decreasing Turing reductions are incomparable with (that is, are neither strictly stronger than nor strictly weaker than) truth-table reductions and are strictly weaker than Turing reductions. In addition, we prove that query-nonincreasing and query-nondecreasing Turing reductions are strictly stronger than truth-table reductions and strictly weaker than Turing reductions. Despite the fact that we prove query-increasing and query-decreasing Turing reductions to in the general case be strictly weaker than Turing reductions, we identify a broad class of sets A for which any set that Turing reduces to A will also reduce to A via both query-increasing and query-decreasing Turing reductions. In particular, this holds for all tight paddable sets, where a set is said to be tight paddable exactly if it is paddable via a function whose output length is bounded tightly both from above and from below in the length of the input. We prove that many natural NP-complete problems such as satisfiability, clique, and vertex cover are tight paddable.
Demand Analysis with Partial Predicates
Venue: arXiv cs.PL 2006
Year: 2006

In order to alleviate the inefficiencies caused by the interaction of the logic and functional sides, integrated languages may take advantage of \emph{demand} information -- i.e. knowing in advance which computations are needed and, to which extent, in a particular context. This work studies \emph{demand analysis} -- which is closely related to \emph{backwards strictness analysis} -- in a semantic framework of \emph{partial predicates}, which in turn are constructive realizations of ideals in a domain. This will allow us to give a concise, unified presentation of demand analysis, to relate it to other analyses based on abstract interpretation or strictness logics, some hints for the implementation, and, more important, to prove the soundness of our analysis based on \emph{demand equations}. There are also some innovative results. One of them is that a set constraint-based analysis has been derived in a stepwise manner using ideas taken from the area of program transformation. The other one is the possibility of using program transformation itself to perform the analysis, specially in those domains of properties where algorithms based on constraint solving are too weak.
Adaptive Channel Allocation Spectrum Etiquette for Cognitive Radio Networks
Venue: arXiv cs.GT 2006
Year: 2006

In this work, we propose a game theoretic framework to analyze the behavior of cognitive radios for distributed adaptive channel allocation. We define two different objective functions for the spectrum sharing games, which capture the utility of selfish users and cooperative users, respectively. Based on the utility definition for cooperative users, we show that the channel allocation problem can be formulated as a potential game, and thus converges to a deterministic channel allocation Nash equilibrium point. Alternatively, a no-regret learning implementation is proposed for both scenarios and it is shown to have similar performance with the potential game when cooperation is enforced, but with a higher variability across users. The no-regret learning formulation is particularly useful to accommodate selfish users. Non-cooperative learning games have the advantage of a very low overhead for information exchange in the network. We show that cooperation based spectrum sharing etiquette improves the overall network performance at the expense of an increased overhead required for information exchange.
Algorithmic correspondence and completeness in modal logic. I. The core algorithm SQEMA
Venue: arXiv cs.LO 2006
Year: 2006

Modal formulae express monadic second-order properties on Kripke frames, but in many important cases these have first-order equivalents. Computing such equivalents is important for both logical and computational reasons. On the other hand, canonicity of modal formulae is important, too, because it implies frame-completeness of logics axiomatized with canonical formulae. Computing a first-order equivalent of a modal formula amounts to elimination of second-order quantifiers. Two algorithms have been developed for second-order quantifier elimination: SCAN, based on constraint resolution, and DLS, based on a logical equivalence established by Ackermann. In this paper we introduce a new algorithm, SQEMA, for computing first-order equivalents (using a modal version of Ackermann's lemma) and, moreover, for proving canonicity of modal formulae. Unlike SCAN and DLS, it works directly on modal formulae, thus avoiding Skolemization and the subsequent problem of unskolemization. We present the core algorithm and illustrate it with some examples. We then prove its correctness and the canonicity of all formulae on which the algorithm succeeds. We show that it succeeds not only on all Sahlqvist formulae, but also on the larger class of inductive formulae, introduced in our earlier papers. Thus, we develop a purely algorithmic approach to proving canonical completeness in modal logic and, in particular, establish one of the most general completeness results in modal logic so far.
Self-stabilization of Circular Arrays of Automata
Venue: arXiv cs.DC 2006
Year: 2006

[Gacs, Kurdiumov, Levin, 78] proposed simple one-dimensional cellular automata with 2 states. In an infinite array they are self-stabilizing: if all but a finite minority of automata are in the same state, the minority states disappear. Implicit in the paper was a stronger result that a sufficiently small minority of states vanish even in a finite circular array. The following note makes this strengthening explicit.
The Computational and Storage Potential of Volunteer Computing
Venue: arXiv cs.DC 2006
Year: 2006

"Volunteer computing" uses Internet-connected computers, volunteered by their owners, as a source of computing power and storage. This paper studies the potential capacity of volunteer computing. We analyzed measurements of over 330,000 hosts participating in a volunteer computing project. These measurements include processing power, memory, disk space, network throughput, host availability, user-specified limits on resource usage, and host churn. We show that volunteer computing can support applications that are significantly more data-intensive, or have larger memory and storage requirements, than those in current projects.
Renyi to Renyi -- Source Coding under Siege
Venue: arXiv cs.IT 2006
Year: 2006

A novel lossless source coding paradigm applies to problems of unreliable lossless channels with low bit rates, in which a vital message needs to be transmitted prior to termination of communications. This paradigm can be applied to Alfred Renyi's secondhand account of an ancient siege in which a spy was sent to scout the enemy but was captured. After escaping, the spy returned to his base in no condition to speak and unable to write. His commander asked him questions that he could answer by nodding or shaking his head, and the fortress was defended with this information. Renyi told this story with reference to prefix coding, but maximizing probability of survival in the siege scenario is distinct from yet related to the traditional source coding objective of minimizing expected codeword length. Rather than finding a code minimizing expected codeword length $\sum_{i=1}^n p(i) l(i)$, the siege problem involves maximizing $\sum_{i=1}^n p(i) θ^{l(i)}$ for a known $θ\in (0,1)$. When there are no restrictions on codewords, this problem can be solve using a known generalization of Huffman coding. The optimal solution has coding bounds which are functions of Renyi entropy; in addition to known bounds, new bounds are derived here. The alphabetically constrained version of this problem has applications in search trees and diagnostic testing. A novel dynamic programming algorithm -- based upon the oldest known algorithm for the traditional alphabetic problem -- optimizes this problem in $O(n^3)$ time and $O(n^2)$ space, whereas two novel approximation algorithms can find a suboptimal solution faster: one in linear time, the other in $O(n \log n)$. Coding bounds for the alphabetic version of this problem are also presented.
Digital Libraries: From Process Modelling to Grid-based Service Oriented Architecture
Venue: arXiv cs.DL 2006
Year: 2006

Graphical Business Process Modelling Languages (BPML) like Role Activity Diagrams (RAD) provide ease and flexibility for modelling business behaviour. However, these languages show limited applicability in terms of enactment over distributed systems paradigms like Service Oriented Architecture (SOA) based grid computing. This paper investigates RAD modelling of a Scientific Publishing Process (SPP) for Digital Libraries (DL) and tries to determine the suitability of Pi-Calculus based formal approaches to enact SOA based grid computing. In order to achieve this purpose, the Pi-Calculus based formal transformation from a RAD model of SPP for DL draws attention towards a number of challenging issues including issues that require particular design considerations for appropriate enactment in a SOA based grid system.
A third level trigger programmable on FPGA for the gamma/hadron separation in a Cherenkov telescope using pseudo-Zernike moments and the SVM classifier
Venue: arXiv cs.CV 2006
Year: 2006

We studied the application of the Pseudo-Zernike features as image parameters (instead of the Hillas parameters) for the discrimination between the images produced by atmospheric electromagnetic showers caused by gamma-rays and the ones produced by atmospheric electromagnetic showers caused by hadrons in the MAGIC Experiment. We used a Support Vector Machine as classification algorithm with the computed Pseudo-Zernike features as classification parameters. We implemented on a FPGA board a kernel function of the SVM and the Pseudo-Zernike features to build a third level trigger for the gamma-hadron separation task of the MAGIC Experiment.
Towards Applicative Relational Programming
Venue: arXiv cs.PL 2006
Year: 2006

Functional programming comes in two flavours: one where ``functions are first-class citizens'' (we call this applicative) and one which is based on equations (we call this declarative). In relational programming clauses play the role of equations. Hence Prolog is declarative. The purpose of this paper is to provide in relational programming a mathematical basis for the relational analog of applicative functional programming. We use the cylindric semantics of first-order logic due to Tarski and provide a new notation for the required cylinders that we call tables. We define the Table/Relation Algebra with operators sufficient to translate Horn clauses into algebraic form. We establish basic mathematical properties of these operators. We show how relations can be first-class citizens, and devise mechanisms for modularity, for local scoping of predicates, and for exporting/importing relations between programs.
On Non-coherent MIMO Channels in the Wideband Regime: Capacity and Reliability
Venue: arXiv cs.IT 2006
Year: 2006

We consider a multiple-input, multiple-output (MIMO) wideband Rayleigh block fading channel where the channel state is unknown to both the transmitter and the receiver and there is only an average power constraint on the input. We compute the capacity and analyze its dependence on coherence length, number of antennas and receive signal-to-noise ratio (SNR) per degree of freedom. We establish conditions on the coherence length and number of antennas for the non-coherent channel to have a "near coherent" performance in the wideband regime. We also propose a signaling scheme that is near-capacity achieving in this regime. We compute the error probability for this wideband non-coherent MIMO channel and study its dependence on SNR, number of transmit and receive antennas and coherence length. We show that error probability decays inversely with coherence length and exponentially with the product of the number of transmit and receive antennas. Moreover, channel outage dominates error probability in the wideband regime. We also show that the critical as well as cut-off rates are much smaller than channel capacity in this regime.
Inter-component communication methods in object-oriented frameworks
Venue: arXiv cs.SE 2006
Year: 2006

Modern frameworks for development of graphical interfaces are using the native controls of the operating system. Because of that they are using operating system events model for inter-component communication. We consider a method to increase inter-component communication speed by sending messages from one component to the other passing over the operating system. Besides the messages subscription helps to avoid receiving of unnecessary messages.
Deriving Conceptual Data Models from Domain Ontologies for Bioinformatics
Venue: arXiv cs.SE 2006
Year: 2006

This paper studies the role that ontologies can play in establishing conceptual data models during the process of information systems development. A mapping algorithm has been proposed and embedded in a special purpose Transformation-Engine to generate a conceptual data model from a given domain ontology. In addition, this paper focuses on applying the proposed approach to a bioinformatics context as the nature of biological data is considered a barrier in representing biological conceptual data models. Both quantitative and qualitative methods have been adopted to critically evaluate this new approach. The results of this evaluation indicate that the quality of the generated conceptual data models can reflect the problem domain entities and the associations between them. The results are encouraging and support the potential role that this approach can play in providing a suitable starting point for conceptual data model development.
State Space Realizations and Monomial Equivalence for Convolutional Codes
Venue: arXiv cs.IT 2006
Year: 2006

We will study convolutional codes with the help of state space realizations. It will be shown that two such minimal realizations belong to the same code if and only if they are equivalent under the full state feedback group. This result will be used in order to prove that two codes with positive Forney indices are monomially equivalent if and only if they share the same adjacency matrix. The adjacency matrix counts in a detailed way the weights of all possible outputs and thus contains full information about the weights of the codewords in the given code.
Guessing under source uncertainty
Venue: arXiv cs.IT 2006
Year: 2006

This paper considers the problem of guessing the realization of a finite alphabet source when some side information is provided. The only knowledge the guesser has about the source and the correlated side information is that the joint source is one among a family. A notion of redundancy is first defined and a new divergence quantity that measures this redundancy is identified. This divergence quantity shares the Pythagorean property with the Kullback-Leibler divergence. Good guessing strategies that minimize the supremum redundancy (over the family) are then identified. The min-sup value measures the richness of the uncertainty set. The min-sup redundancies for two examples - the families of discrete memoryless sources and finite-state arbitrarily varying sources - are then determined.
Yet Another Efficient Unification Algorithm
Venue: arXiv cs.LO 2006
Year: 2006

The unification algorithm is at the core of the logic programming paradigm, the first unification algorithm being developed by Robinson [5]. More efficient algorithms were developed later [3] and I introduce here yet another efficient unification algorithm centered on a specific data structure, called the Unification Table.
Random 3CNF formulas elude the Lovasz theta function
Venue: arXiv cs.CC 2006
Year: 2006

Let $ϕ$ be a 3CNF formula with n variables and m clauses. A simple nonconstructive argument shows that when m is sufficiently large compared to n, most 3CNF formulas are not satisfiable. It is an open question whether there is an efficient refutation algorithm that for most such formulas proves that they are not satisfiable. A possible approach to refute a formula $ϕ$ is: first, translate it into a graph $G_ϕ$ using a generic reduction from 3-SAT to max-IS, then bound the maximum independent set of $G_ϕ$ using the Lovasz $\vartheta$ function. If the $\vartheta$ function returns a value $< m$, this is a certificate for the unsatisfiability of $ϕ$. We show that for random formulas with $m < n^{3/2 -o(1)}$ clauses, the above approach fails, i.e. the $\vartheta$ function is likely to return a value of m.
Access Control for Hierarchical Joint-Tenancy
Venue: arXiv cs.CR 2006
Year: 2006

Basic role based access control [RBAC] provides a mechanism for segregating access privileges based upon a user's hierarchical roles within an organization. This model doesn't scale well when there is tight integration of multiple hierarchies. In a case where there is joint-tenancy and a requirement for different levels of disclosure based upon a user's hierarchy, or in our case, organization or company, basic RBAC requires these hierarchies to be effectively merged. Specific roles that effectively represent both the user's organizations and roles must be translated to fit within the merged hierarchy to be used to control access. Essentially, users from multiple organizations are served from a single role base with roles designed to constrain their access as needed. Our work proposes, through parameterized roles and privileges, a means for accurately representing both users' roles within their respective hierarchies for providing access to controlled objects. Using this method will reduce the amount of complexity required in terms of the number of roles and privileges. The resulting set of roles, privileges, and objects will make modeling and visualizing the access role hierarchy significantly simplified. This paper will give some background on role based access control, parameterized roles and privileges, and then focus on how RBAC with parameterized roles and privileges can be leveraged as an access control solution for the problems presented by joint tenancy.
Efficient Compression of Prolog Programs
Venue: arXiv cs.PL 2006
Year: 2006

We propose a special-purpose class of compression algorithms for efficient compression of Prolog programs. It is a dictionary-based compression method, specially designed for the compression of Prolog code, and therefore we name it PCA (Prolog Compression Algorithm). According to the experimental results this method provides better compression than state-of-the-art general-purpose compression algorithms. Since the algorithm works with Prolog syntactic entities (e.g. atoms, terms, etc.) the implementation of a Prolog prototype is straightforward and very easy to use in any Prolog application that needs compression. Although the algorithm is designed for Prolog programs, the idea can be easily applied for the compression of programs written in other (logic) languages.
Prolog Server Pages
Venue: arXiv cs.NI 2006
Year: 2006

Prolog Server Pages (PSP) is a scripting language, based on Prolog, than can be embedded in HTML documents. To run PSP applications one needs a web server, a web browser and a PSP interpreter. The code is executed, by the interpreter, on the server-side (web server) and the output (together with the html code in witch the PSP code is embedded) is sent to the client-side (browser). The current implementation supports Apache Web Server. We implemented an Apache web server module that handles PSP files, and sends the result (an html document) to the client. PSP supports both GET and POST http requests. It also provides methods for working with http cookies.
Remote-control and clustering of physical computations using the XML-RPC protocol and the open-Mosix system
Venue: arXiv cs.DC 2006
Year: 2006

The applications of the remote control of physical simulations performed in clustered computers running under an open-Mosix system are presented. Results from the simulation of a 2-dimensional ferromagnetic system of spins in the Ising scheme are provided. Basic parameters of a simulated hysteresis loop like coercivity and exchange bias due to pinning of ferromagnetic spins are given. The paper describes in physicists terminology a cost effective solution which utilizes an XML-RPC protocol (Extensible Markup Language - Remote Procedure Calling) and standard C++ and Python languages.