OpenRaiser/Intern-Atlas huggingface dataset:
A Distributed AI Aided 3D Domino Game
Venue: arXiv cs.AI 2010
Year: 2010

In the article a turn-based game played on four computers connected via network is investigated. There are three computers with natural intelligence and one with artificial intelligence. Game table is seen by each player's own view point in all players' monitors. Domino pieces are three dimensional. For distributed systems TCP/IP protocol is used. In order to get 3D image, Microsoft XNA technology is applied. Domino 101 game is nondeterministic game that is result of the game depends on the initial random distribution of the pieces. Number of the distributions is equal to the multiplication of following combinations: . Moreover, in this game that is played by four people, players are divided into 2 pairs. Accordingly, we cannot predict how the player uses the dominoes that is according to the dominoes of his/her partner or according to his/her own dominoes. The fact that the natural intelligence can be a player in any level affects the outcome. These reasons make it difficult to develop an AI. In the article four levels of AI are developed. The AI in the first level is equivalent to the intelligence of a child who knows the rules of the game and recognizes the numbers. The AI in this level plays if it has any domino, suitable to play or says pass. In most of the games which can be played on the internet, the AI does the same. But the AI in the last level is a master player, and it can develop itself according to its competitors' levels.
On interleaving in {P,A}-Time Petri nets with strong semantics
Venue: arXiv cs.FL 2010
Year: 2010

This paper deals with the reachability analysis of {P,A}-Time Petri nets ({P,A}-TPN in short) in the context of strong semantics. It investigates the convexity of the union of state classes reached by different interleavings of the same set of transitions. In BB08, the authors have considered the T-TPN model and its Contracted State Class Graph (CSCG) and shown that this union is not necessarily convex. They have however established some sufficient conditions which ensure convexity. This paper shows that for the CSCG of {P,A}-TPN, this union is convex and can be computed without computing intermediate state classes. These results allow to improve the forward reachability analysis by agglomerating, in the same state class, all state classes reached by different interleavings of the same set of transitions (abstraction by convex-union).
A Game-theoretic Approach for Synthesizing Fault-Tolerant Embedded Systems
Venue: arXiv cs.GT 2010
Year: 2010

In this paper, we present an approach for fault-tolerant synthesis by combining predefined patterns for fault-tolerance with algorithmic game solving. A non-fault-tolerant system, together with the relevant fault hypothesis and fault-tolerant mechanism templates in a pool are translated into a distributed game, and we perform an incomplete search of strategies to cope with undecidability. The result of the game is translated back to executable code concretizing fault-tolerant mechanisms using constraint solving. The overall approach is implemented to a prototype tool chain and is illustrated using examples.
Formalization of the data flow diagram rules for consistency check
Venue: arXiv cs.SE 2010
Year: 2010

In system development life cycle (SDLC), a system model can be developed using Data Flow Diagram (DFD). DFD is graphical diagrams for specifying, constructing and visualizing the model of a system. DFD is used in defining the requirements in a graphical view. In this paper, we focus on DFD and its rules for drawing and defining the diagrams. We then formalize these rules and develop the tool based on the formalized rules. The formalized rules for consistency check between the diagrams are used in developing the tool. This is to ensure the syntax for drawing the diagrams is correct and strictly followed. The tool automates the process of manual consistency check between data flow diagrams.
From UML Specification into Implementation using Object Mapping
Venue: arXiv cs.SE 2010
Year: 2010

In information systems, a system is analyzed using a modeling tool. Analysis is an important phase prior to implementation in order to obtain the correct requirements of the system. During the requirements phase, the software requirements specification (SRS) is used to specify the system requirements. Then, this requirements specification is used to implement the system. The requirements specification can be represented using either a structure approach or an object-oriented approach. A UML (Unified Modeling Language) specification is a well-known for representation of requirements specification in an object-oriented approach. In this paper, we present one case study and discuss how mapping from UML specification into implementation is done. The case study does not require advanced programming skills. However, it does require familiarity in creating and instantiating classes, object-oriented programming with inheritance, data structure, file processing and control loop. For the case study, UML specification is used in requirements phase and Borland C++ is used in implementation phase. Based on the case study, it shows that the proposed approach improved the understanding of mapping from UML specification into implementation.
Semantic Query Optimisation with Ontology Simulation
Venue: arXiv cs.IR 2010
Year: 2010

Semantic Web is, without a doubt, gaining momentum in both industry and academia. The word "Semantic" refers to "meaning" - a semantic web is a web of meaning. In this fast changing and result oriented practical world, gone are the days where an individual had to struggle for finding information on the Internet where knowledge management was the major issue. The semantic web has a vision of linking, integrating and analysing data from various data sources and forming a new information stream, hence a web of databases connected with each other and machines interacting with other machines to yield results which are user oriented and accurate. With the emergence of Semantic Web framework the naïve approach of searching information on the syntactic web is cliché. This paper proposes an optimised semantic searching of keywords exemplified by simulation an ontology of Indian universities with a proposed algorithm which ramifies the effective semantic retrieval of information which is easy to access and time saving.
The fractal structure of cellular automata on Abelian groups
Venue: arXiv cs.DM 2010
Year: 2010

It is well-known that the spacetime diagrams of some cellular automata have a fractal structure: for instance Pascal's triangle modulo 2 generates a Sierpinski triangle. Explaining the fractal structure of the spacetime diagrams of cellular automata is a much explored topic, but virtually all of the results revolve around a special class of automata, whose typical features include irreversibility, an alphabet with a ring structure, a global evolution that is a ring homomorphism, and a property known as (weakly) p-Fermat. The class of automata that we study in this article has none of these properties. Their cell structure is weaker, as it does not come with a multiplication, and they are far from being p-Fermat, even weakly. However, they do produce fractal spacetime diagrams, and we explain why and how.
Mining Frequent Itemsets Using Genetic Algorithm
Venue: arXiv cs.DB 2010
Year: 2010

In general frequent itemsets are generated from large data sets by applying association rule mining algorithms like Apriori, Partition, Pincer-Search, Incremental, Border algorithm etc., which take too much computer time to compute all the frequent itemsets. By using Genetic Algorithm (GA) we can improve the scenario. The major advantage of using GA in the discovery of frequent itemsets is that they perform global search and its time complexity is less compared to other algorithms as the genetic algorithm is based on the greedy approach. The main aim of this paper is to find all the frequent itemsets from given data sets using genetic algorithm.
A Path Algebra for Multi-Relational Graphs
Venue: arXiv cs.DM 2010
Year: 2010

A multi-relational graph maintains two or more relations over a vertex set. This article defines an algebra for traversing such graphs that is based on an $n$-ary relational algebra, a concatenative single-relational path algebra, and a tensor-based multi-relational algebra. The presented algebra provides a monoid, automata, and formal language theoretic foundation for the construction of a multi-relational graph traversal engine.
Functional Dependence of Secrets in a Collaboration Network
Venue: arXiv cs.LO 2010
Year: 2010

A collaboration network is a graph formed by communication channels between parties. Parties communicate over these channels to establish secrets, simultaneously enforcing interdependencies between the secrets. The paper studies properties of these interdependencies that are induced by the topology of the network. In previous work, the authors developed a complete logical system for one such property, independence, also known in the information flow literature as nondeducibility. This work describes a complete and decidable logical system for the functional dependence relation between sets of secrets over a collaboration network. The system extends Armstrong's system of axioms for functional dependency in databases.
Stochastic Simulation of Process Calculi for Biology
Venue: arXiv cs.PL 2010
Year: 2010

Biological systems typically involve large numbers of components with complex, highly parallel interactions and intrinsic stochasticity. To model this complexity, numerous programming languages based on process calculi have been developed, many of which are expressive enough to generate unbounded numbers of molecular species and reactions. As a result of this expressiveness, such calculi cannot rely on standard reaction-based simulation methods, which require fixed numbers of species and reactions. Rather than implementing custom stochastic simulation algorithms for each process calculus, we propose to use a generic abstract machine that can be instantiated to a range of process calculi and a range of reaction-based simulation algorithms. The abstract machine functions as a just-in-time compiler, which dynamically updates the set of possible reactions and chooses the next reaction in an iterative cycle. In this short paper we give a brief summary of the generic abstract machine, and show how it can be instantiated with the stochastic simulation algorithm known as Gillespie's Direct Method. We also discuss the wider implications of such an abstract machine, and outline how it can be used to simulate multiple calculi simultaneously within a common framework.
Measurable Stochastics for Brane Calculus
Venue: arXiv cs.CE 2010
Year: 2010

We give a stochastic extension of the Brane Calculus, along the lines of recent work by Cardelli and Mardare. In this presentation, the semantics of a Brane process is a measure of the stochastic distribution of possible derivations. To this end, we first introduce a labelled transition system for Brane Calculus, proving its adequacy w.r.t. the usual reduction semantics. Then, brane systems are presented as Markov processes over the measurable space generated by terms up-to syntactic congruence, and where the measures are indexed by the actions of this new LTS. Finally, we provide a SOS presentation of this stochastic semantics, which is compositional and syntax-driven.
Hybrid Calculus of Wrapped Compartments
Venue: arXiv cs.PL 2010
Year: 2010

The modelling and analysis of biological systems has deep roots in Mathematics, specifically in the field of ordinary differential equations (ODEs). Alternative approaches based on formal calculi, often derived from process algebras or term rewriting systems, provide a quite complementary way to analyze the behaviour of biological systems. These calculi allow to cope in a natural way with notions like compartments and membranes, which are not easy (sometimes impossible) to handle with purely numerical approaches, and are often based on stochastic simulation methods. Recently, it has also become evident that stochastic effects in regulatory networks play a crucial role in the analysis of such systems. Actually, in many situations it is necessary to use stochastic models. For example when the system to be described is based on the interaction of few molecules, when we are at the presence of a chemical instability, or when we want to simulate the functioning of a pool of entities whose compartmentalised structure evolves dynamically. In contrast, stable metabolic networks, involving a large number of reagents, for which the computational cost of a stochastic simulation becomes an insurmountable obstacle, are efficiently modelled with ODEs. In this paper we define a hybrid simulation method, combining the stochastic approach with ODEs, for systems described in CWC, a calculus on which we can express the compartmentalisation of a biological system whose evolution is defined by a set of rewrite rules.
On reversible cascades in scale-free and Erdős-Rényi random graphs
Venue: arXiv cs.DM 2010
Year: 2010

Consider the following cascading process on a simple undirected graph $G(V,E)$ with diameter $Δ$. In round zero, a set $S\subseteq V$ of vertices, called the seeds, are active. In round $i+1,$ $i\in\mathbb{N},$ a non-isolated vertex is activated if at least a $ρ\in(\,0,1\,]$ fraction of its neighbors are active in round $i$; it is deactivated otherwise. For $k\in\mathbb{N},$ let $\text{min-seed}^{(k)}(G,ρ)$ be the minimum number of seeds needed to activate all vertices in or before round $k$. This paper derives upper bounds on $\text{min-seed}^{(k)}(G,ρ)$. In particular, if $G$ is connected and there exist constants $C>0$ and $γ>2$ such that the fraction of degree-$k$ vertices in $G$ is at most $C/k^γ$ for all $k\in\mathbb{Z}^+,$ then $\text{min-seed}^{(Δ)}(G,ρ)=O(\lceilρ^{γ-1}\,|\,V\,|\rceil)$. Furthermore, for $n\in\mathbb{Z}^+,$ $p=Ω((\ln{(e/ρ)})/(ρn))$ and with probability $1-\exp{(-n^{Ω(1)})}$ over the Erdős-Rényi random graphs $G(n,p),$ $\text{min-seed}^{(1)}(G(n,p),ρ)=O(ρn)$.
A PDTB-Styled End-to-End Discourse Parser
Venue: arXiv cs.CL 2010
Year: 2010

We have developed a full discourse parser in the Penn Discourse Treebank (PDTB) style. Our trained parser first identifies all discourse and non-discourse relations, locates and labels their arguments, and then classifies their relation types. When appropriate, the attribution spans to these relations are also determined. We present a comprehensive evaluation from both component-wise and error-cascading perspectives.
Beyond Quantifier-Free Interpolation in Extensions of Presburger Arithmetic (Extended Technical Report)
Venue: arXiv cs.LO 2010
Year: 2010

Craig interpolation has emerged as an effective means of generating candidate program invariants. We present interpolation procedures for the theories of Presburger arithmetic combined with (i) uninterpreted predicates (QPA+UP), (ii) uninterpreted functions (QPA+UF) and (iii) extensional arrays (QPA+AR). We prove that none of these combinations can be effectively interpolated without the use of quantifiers, even if the input formulae are quantifier-free. We go on to identify fragments of QPA+UP and QPA+UF with restricted forms of guarded quantification that are closed under interpolation. Formulae in these fragments can easily be mapped to quantifier-free expressions with integer division. For QPA+AR, we formulate a sound interpolation procedure that potentially produces interpolants with unrestricted quantifiers.
Group Anonymity: Problems and Solutions
Venue: arXiv cs.CR 2010
Year: 2010

Existing methods of providing data anonymity preserve individual privacy, but, the task of protecting respondent groups' information in publicly available datasets remains open. Group anonymity lies in hiding (masking) data patterns that cannot be revealed by analyzing individual records. We discuss main corresponding problems, and provide methods for solving each one. Keywords: group anonymity, wavelet transform.
Rank k Cholesky Up/Down-dating on the GPU: gpucholmodV0.2
Venue: arXiv cs.DC 2010
Year: 2010

In this note we briefly describe our Cholesky modification algorithm for streaming multiprocessor architectures. Our implementation is available in C++ with Matlab binding, using CUDA to utilise the graphics processing unit (GPU). Limited speed ups are possible due to the bandwidth bound nature of the problem. Furthermore, a complex dependency pattern must be obeyed, requiring multiple kernels to be launched. Nonetheless, this makes for an interesting problem, and our approach can reduce the computation time by a factor of around 7 for matrices of size 5000 by 5000 and k=16, in comparison with the LINPACK suite running on a CPU of comparable vintage. Much larger problems can be handled however due to the O(n) scaling in required GPU memory of our method.
A short proof that adding some permutation rules to $β$ preserves $SN$
Venue: arXiv cs.LO 2010
Year: 2010

I show that, if a term is $SN$ for $β$, it remains $SN$ when some permutation rules are added.
Geometric Complexity Theory and Tensor Rank
Venue: arXiv cs.CC 2010
Year: 2010

Mulmuley and Sohoni (GCT1 in SICOMP 2001, GCT2 in SICOMP 2008) proposed to view the permanent versus determinant problem as a specific orbit closure problem and to attack it by methods from geometric invariant and representation theory. We adopt these ideas towards the goal of showing lower bounds on the border rank of specific tensors, in particular for matrix multiplication. We thus study specific orbit closure problems for the group $G = GL(W_1)\times GL(W_2)\times GL(W_3)$ acting on the tensor product $W=W_1\otimes W_2\otimes W_3$ of complex finite dimensional vector spaces. Let $G_s = SL(W_1)\times SL(W_2)\times SL(W_3)$. A key idea from GCT2 is that the irreducible $G_s$-representations occurring in the coordinate ring of the $G$-orbit closure of a stable tensor $w\in W$ are exactly those having a nonzero invariant with respect to the stabilizer group of $w$. However, we prove that by considering $G_s$-representations, as suggested in GCT1-2, only trivial lower bounds on border rank can be shown. It is thus necessary to study $G$-representations, which leads to geometric extension problems that are beyond the scope of the subgroup restriction problems emphasized in GCT1-2. We prove a very modest lower bound on the border rank of matrix multiplication tensors using $G$-representations. This shows at least that the barrier for $G_s$-representations can be overcome. To advance, we suggest the coarser approach to replace the semigroup of representations of a tensor by its moment polytope. We prove first results towards determining the moment polytopes of matrix multiplication and unit tensors.
Mixed Reality Serious Games: The Therapist Perspective
Venue: arXiv cs.HC 2010
Year: 2010

The objective of this paper is to present a Mixed Reality System (MRS) for rehabilitation of the upper limb after stroke. The system answers the following challenges: (i) increase motivation of patients by making the training a personalized experience; (ii) take into account patients' impairments by offering intuitive and easy to use interaction modalities; (iii) make it possible to therapists to track patient's activities and to evaluate/track their progress; (iv) open opportunities for telemedicine and tele rehabilitation; (v) and provide an economically acceptable system by reducing both equipment and management costs. In order to test this system a pilot study has been conducted in conjunction with a French hospital in order to understand the potential and benefits of mixed reality. The pilot involved 3 therapists who 'played the role' of patients. Three sessions, one using conventional rehabilitation, another using an ad hoc developed game on a PC, and another using a mixed reality version of the same game were held. Results have shown the MRS and the PC game to be accepted more than physical rehabilitation.
Processor-Dependent Malware... and codes
Venue: arXiv cs.CR 2010
Year: 2010

Malware usually target computers according to their operating system. Thus we have Windows malwares, Linux malwares and so on ... In this paper, we consider a different approach and show on a technical basis how easily malware can recognize and target systems selectively, according to the onboard processor chip. This technology is very easy to build since it does not rely on deep analysis of chip logical gates architecture. Floating Point Arithmetic (FPA) looks promising to define a set of tests to identify the processor or, more precisely, a subset of possible processors. We give results for different families of processors: AMD, Intel (Dual Core, Atom), Sparc, Digital Alpha, Cell, Atom ... As a conclusion, we propose two {\it open problems} that are new, to the authors' knowledge.
Finding topological subgraphs is fixed-parameter tractable
Venue: arXiv cs.DS 2010
Year: 2010

We show that for every fixed undirected graph $H$, there is a $O(|V(G)|^3)$ time algorithm that tests, given a graph $G$, if $G$ contains $H$ as a topological subgraph (that is, a subdivision of $H$ is subgraph of $G$). This shows that topological subgraph testing is fixed-parameter tractable, resolving a longstanding open question of Downey and Fellows from 1992. As a corollary, for every $H$ we obtain an $O(|V(G)|^3)$ time algorithm that tests if there is an immersion of $H$ into a given graph $G$. This answers another open question raised by Downey and Fellows in 1992.
Reusing optical supports using a simple software
Venue: arXiv cs.OH 2010
Year: 2010

In this paper we show how it is possible to reuse optical supports (CDs, DVDs, etc.) without using chemical or physical transformation, only employing a software that can easily run on domestic computers. This software can make obsolete optical supports useful again, converting de facto WEEE (Waste electric and electronic equipment) into EEE (Electric and electronic equipment). A massive use of such a software can lead to a significant change in EEE every-day use, reducing its production to sustainable levels.
Comparison of Spearman's rho and Kendall's tau in Normal and Contaminated Normal Models
Venue: arXiv cs.IT 2010
Year: 2010

This paper analyzes the performances of the Spearman's rho (SR) and Kendall's tau (KT) with respect to samples drawn from bivariate normal and bivariate contaminated normal populations. The exact analytical formulae of the variance of SR and the covariance between SR and KT are obtained based on the Childs's reduction formula for the quadrivariate normal positive orthant probabilities. Close form expressions with respect to the expectations of SR and KT are established under the bivariate contaminated normal models. The bias, mean square error (MSE) and asymptotic relative efficiency (ARE) of the three estimators based on SR and KT to the Pearson's product moment correlation coefficient (PPMCC) are investigated in both the normal and contaminated normal models. Theoretical and simulation results suggest that, contrary to the opinion of equivalence between SR and KT in some literature, the behaviors of SR and KT are strikingly different in the aspects of bias effect, variance, mean square error, and asymptotic relative efficiency. The new findings revealed in this work provide not only deeper insights into the two most widely used rank based correlation coefficients, but also a guidance for choosing which one to use under the circumstances where the PPMCC fails to apply.