OpenRaiser/Intern-Atlas huggingface dataset:
Hybrid 3-D Formation Control for Unmanned Helicopters
Venue: arXiv cs.SY 2011
Year: 2011

Teams of Unmanned Aerial Vehicles (UAVs) form typical networked cyber-physical systems that involve the interaction of discrete logic and continuous dynamics. This paper presents a hybrid supervisory control framework for the three-dimensional leader follower formation control of unmanned helicopters. The proposed hybrid control framework captures internal interactions between the decision making unit and the path planner continuous dynamics of the system, and hence improves the system's overall reliability. To design such a hybrid controller, a spherical abstraction of the state space is proposed as a new method of abstraction. Utilizing the properties of multi-affine functions over the partitioned space leads to a finite state Discrete Event System (DES) model, which is shown to be bisimilar to the original continuous-variable dynamical system. Then, in the discrete domain, a logic supervisor is modularly designed for the abstracted model. Due to the bisimilarity between the abstracted DES model and the original UAV dynamics, the designed logic supervisor can be implemented as a hybrid controller through an interface layer. This supervisor drives the UAV dynamics to satisfy the design requirements. In other words, the hybrid controller is able to bring the UAVs to the desired formation starting from any initial state inside the control horizon and then, maintain the formation. Moreover, a collision avoidance mechanism is embedded in the designed supervisor. Finally, the algorithm has been verified by a hardware-in-the-loop simulation platform, which is developed for unmanned helicopters. The presented results show the effectiveness of the algorithm.
Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks
Venue: arXiv cs.DS 2011
Year: 2011

We show that randomization can lead to significant improvements for a few fundamental problems in distributed tracking. Our basis is the {\em count-tracking} problem, where there are $k$ players, each holding a counter $n_i$ that gets incremented over time, and the goal is to track an $\eps$-approximation of their sum $n=\sum_i n_i$ continuously at all times, using minimum communication. While the deterministic communication complexity of the problem is $Θ(k/\eps \cdot \log N)$, where $N$ is the final value of $n$ when the tracking finishes, we show that with randomization, the communication cost can be reduced to $Θ(\sqrt{k}/\eps \cdot \log N)$. Our algorithm is simple and uses only O(1) space at each player, while the lower bound holds even assuming each player has infinite computing power. Then, we extend our techniques to two related distributed tracking problems: {\em frequency-tracking} and {\em rank-tracking}, and obtain similar improvements over previous deterministic algorithms. Both problems are of central importance in large data monitoring and analysis, and have been extensively studied in the literature.
Infinite permutations vs. infinite words
Venue: arXiv cs.FL 2011
Year: 2011

I am going to compare well-known properties of infinite words with those of infinite permutations, a new object studied since middle 2000s. Basically, it was Sergey Avgustinovich who invented this notion, although in an early study by Davis et al. permutations appear in a very similar framework as early as in 1977. I am going to tell about periodicity of permutations, their complexity according to several definitions and their automatic properties, that is, about usual parameters of words, now extended to permutations and behaving sometimes similarly to those for words, sometimes not. Another series of results concerns permutations generated by infinite words and their properties. Although this direction of research is young, many people, including two other speakers of this meeting, have participated in it, and I believe that several more topics for further study are really promising.
Combinatorics on words in information security: Unavoidable regularities in the construction of multicollision attacks on iterated hash functions
Venue: arXiv cs.FL 2011
Year: 2011

Classically in combinatorics on words one studies unavoidable regularities that appear in sufficiently long strings of symbols over a fixed size alphabet. In this paper we take another viewpoint and focus on combinatorial properties of long words in which the number of occurrences of any symbol is restritced by a fixed constant. We then demonstrate the connection of these properties to constructing multicollision attacks on so called generalized iterated hash functions.
Finite-Repetition threshold for infinite ternary words
Venue: arXiv cs.FL 2011
Year: 2011

The exponent of a word is the ratio of its length over its smallest period. The repetitive threshold r(a) of an a-letter alphabet is the smallest rational number for which there exists an infinite word whose finite factors have exponent at most r(a). This notion was introduced in 1972 by Dejean who gave the exact values of r(a) for every alphabet size a as it has been eventually proved in 2009. The finite-repetition threshold for an a-letter alphabet refines the above notion. It is the smallest rational number FRt(a) for which there exists an infinite word whose finite factors have exponent at most FRt(a) and that contains a finite number of factors with exponent r(a). It is known from Shallit (2008) that FRt(2)=7/3. With each finite-repetition threshold is associated the smallest number of r(a)-exponent factors that can be found in the corresponding infinite word. It has been proved by Badkobeh and Crochemore (2010) that this number is 12 for infinite binary words whose maximal exponent is 7/3. We show that FRt(3)=r(3)=7/4 and that the bound is achieved with an infinite word containing only two 7/4-exponent words, the smallest number. Based on deep experiments we conjecture that FRt(4)=r(4)=7/5. The question remains open for alphabets with more than four letters. Keywords: combinatorics on words, repetition, repeat, word powers, word exponent, repetition threshold, pattern avoidability, word morphisms.
A new proof for the decidability of D0L ultimate periodicity
Venue: arXiv cs.FL 2011
Year: 2011

We give a new proof for the decidability of the D0L ultimate periodicity problem based on the decidability of p-periodicity of morphic words adapted to the approach of Harju and Linna.
Abelian returns in Sturmian words
Venue: arXiv cs.FL 2011
Year: 2011

In this paper we study an abelian version of the notion of return word. Our main result is a new characterization of Sturmian words via abelian returns. Namely, we prove that a word is Sturmian if and only if each of its factors has two or three abelian returns. In addition, we describe the structure of abelian returns in Sturmian words, and discuss connections between abelian returns and periodicity.
Information theory: Sources, Dirichlet series, and realistic analyses of data structures
Venue: arXiv cs.IT 2011
Year: 2011

Most of the text algorithms build data structures on words, mainly trees, as digital trees (tries) or binary search trees (bst). The mechanism which produces symbols of the words (one symbol at each unit time) is called a source, in information theory contexts. The probabilistic behaviour of the trees built on words emitted by the same source depends on two factors: the algorithmic properties of the tree, together with the information-theoretic properties of the source. Very often, these two factors are considered in a too simplified way: from the algorithmic point of view, the cost of the Bst is only measured in terms of the number of comparisons between words --from the information theoretic point of view, only simple sources (memoryless sources or Markov chains) are studied. We wish to perform here a realistic analysis, and we choose to deal together with a general source and a realistic cost for data structures: we take into account comparisons between symbols, and we consider a general model of source, related to a dynamical system, which is called a dynamical source. Our methods are close to analytic combinatorics, and our main object of interest is the generating function of the source Lambda(s), which is here of Dirichlet type. Such an object transforms probabilistic properties of the source into analytic properties. The tameness of the source, which is defined through analytic properties of Lambda(s), appears to be central in the analysis, and is precisely studied for the class of dynamical sources. We focus here on arithmetical conditions, of diophantine type, which are sufficient to imply tameness on a domain with hyperbolic shape.
Systems of Word Equations and Polynomials: a New Approach
Venue: arXiv cs.FL 2011
Year: 2011

We develop new polynomial methods for studying systems of word equations. We use them to improve some earlier results and to analyze how sizes of systems of word equations satisfying certain independence properties depend on the lengths of the equations. These methods give the first nontrivial upper bounds for the sizes of the systems.
Optimizing Properties of Balanced Words
Venue: arXiv cs.DM 2011
Year: 2011

In the past few decades there has been a good deal of papers which are concerned with optimization problems in different areas of mathematics (along 0-1 words, finite or infinite) and which yield - sometimes quite unexpectedly - balanced words as optimal. In this note we list some key results along these lines known to date.
Evaluating Impact of Mobility on Wireless Routing Protocols
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we evaluate, analyze, and compare the impact of mobility on the behavior of three reactive protocols (AODV, DSR, DYMO) and three proactive protocols (DSDV, FSR, OLSR) in multi-hop wireless networks. We take into account throughput, end-to-end delay, and normalized routing load as performance parameters. Based upon the extensive simulation results in NS-2, we rank all of six protocols according to the performance parameters. Besides providing the interesting facts regarding the response of each protocol on varying mobilities and speeds, we also study the trade-offs, the routing protocols have to make. Such as, to achieve throughput, a protocol has to pay some cost in the form of increased end-to-end delay or routing overhead.
On the Intersection of All Critical Sets of a Unicyclic Graph
Venue: arXiv cs.DM 2011
Year: 2011

A set S is independent in a graph G if no two vertices from S are adjacent. The independence number alpha(G) is the cardinality of a maximum independent set, while mu(G) is the size of a maximum matching in G. If alpha(G)+mu(G)=|V|, then G=(V,E) is called a Konig-Egervary graph. The number d_{c}(G)=max{|A|-|N(A)|} is called the critical difference of G (Zhang, 1990). By core(G) (corona(G)) we denote the intersection (union, respectively) of all maximum independent sets, while by ker(G) we mean the intersection of all critical independent sets. A connected graph having only one cycle is called unicyclic. It is known that ker(G) is a subset of core(G) for every graph G, while the equality is true for bipartite graphs (Levit and Mandrescu, 2011). For Konig-Egervary unicyclic graphs, the difference |core(G)|-|ker(G)| may equal any non-negative integer. In this paper we prove that if G is a non-Konig-Egervary unicyclic graph, then: (i) ker(G)= core(G) and (ii) |corona(G)|+|core(G)|=2*alpha(G)+1. Pay attention that |corona(G)|+|core(G)|=2*alpha(G) holds for every Konig-Egervary graph.
Solving puzzles described in English by automated translation to answer set programming and learning how to do that translation
Venue: arXiv cs.CL 2011
Year: 2011

We present a system capable of automatically solving combinatorial logic puzzles given in (simplified) English. It involves translating the English descriptions of the puzzles into answer set programming(ASP) and using ASP solvers to provide solutions of the puzzles. To translate the descriptions, we use a lambda-calculus based approach using Probabilistic Combinatorial Categorial Grammars (PCCG) where the meanings of words are associated with parameters to be able to distinguish between multiple meanings of the same word. Meaning of many words and the parameters are learned. The puzzles are represented in ASP using an ontology which is applicable to a large set of logic puzzles.
The inconsistency of the h-index
Venue: arXiv cs.DL 2011
Year: 2011

The h-index is a popular bibliometric indicator for assessing individual scientists. We criticize the h-index from a theoretical point of view. We argue that for the purpose of measuring the overall scientific impact of a scientist (or some other unit of analysis) the h-index behaves in a counterintuitive way. In certain cases, the mechanism used by the h-index to aggregate publication and citation statistics into a single number leads to inconsistencies in the way in which scientists are ranked. Our conclusion is that the h-index cannot be considered an appropriate indicator of a scientist's overall scientific impact. Based on recent theoretical insights, we discuss what kind of indicators can be used as an alternative to the h-index. We pay special attention to the highly cited publications indicator. This indicator has a lot in common with the h-index, but unlike the h-index it does not produce inconsistent rankings.
Toward Parts-Based Scene Understanding with Pixel-Support Parts-Sparse Pictorial Structures
Venue: arXiv cs.CV 2011
Year: 2011

Scene understanding remains a significant challenge in the computer vision community. The visual psychophysics literature has demonstrated the importance of interdependence among parts of the scene. Yet, the majority of methods in computer vision remain local. Pictorial structures have arisen as a fundamental parts-based model for some vision problems, such as articulated object detection. However, the form of classical pictorial structures limits their applicability for global problems, such as semantic pixel labeling. In this paper, we propose an extension of the pictorial structures approach, called pixel-support parts-sparse pictorial structures, or PS3, to overcome this limitation. Our model extends the classical form in two ways: first, it defines parts directly based on pixel-support rather than in a parametric form, and second, it specifies a space of plausible parts-based scene models and permits one to be used for inference on any given image. PS3 makes strides toward unifying object-level and pixel-level modeling of scene elements. In this report, we implement the first half of our model and rely upon external knowledge to provide an initial graph structure for a given image. Our experimental results on benchmark datasets demonstrate the capability of this new parts-based view of scene modeling.
A New Trusted and Collaborative Agent Based Approach for Ensuring Cloud Security
Venue: arXiv cs.CR 2011
Year: 2011

In order to determine the user's trust is a growing concern for ensuring privacy and security in a cloud computing environment. In cloud, user's data is stored in one or more remote server(s) which poses more security challenges for the system. One of the most important concerns is to protect user's sensitive information from other users and hackers that may cause data leakage in cloud storage. Having this security challenge in mind, this paper focuses on the development of a more secure cloud environment, to determine the trust of the service requesting authorities by using a novel VM (Virtual Machine) monitoring system. Moreover, this research aims towards proposing a new trusted and collaborative agent-based two-tier framework, titled WAY (Who Are You?), to protect cloud resources. The framework can be used to provide security in network, infrastructure, as well as data storage in a heterogeneous cloud platform. If the trust updating policy is based on network activities, then the framework can provide network security. Similarly, it provides storage security by monitoring unauthorized access activities by the Cloud Service Users (CSU). Infrastructure security can be provided by monitoring the use of privileged instructions within the isolated VMs. The uniqueness of the proposed security solution lies in the fact that it ensures security and privacy both at the service provider level as well as at the user level in a cloud environment.
The Information Flow Framework: A Descriptive Category Metatheory
Venue: arXiv cs.NI 2011
Year: 2011

The Information Flow Framework (IFF) is a descriptive category metatheory. It is an experiment in foundations, which follows a bottom-up approach to logical description. The IFF forms the structural aspect of the IEEE P1600.1 Standard Upper Ontology (SUO) project. The categorical approach of the IFF provides a principled framework for the modular design of object-level ontologies. The IFF represents meta-logic, and as such operates at the structural level of ontologies. In the IFF, there is a precise boundary between the metalevel and the object level. The modular architecture of the IFF consists of metalevels, namespaces and meta-ontologies. Each metalevel services the levels below by providing a metalanguage used to declare and axiomatize those levels. Corresponding to the metalevels are nested metalanguages, where each metalanguage axiomatization includes specialization of the one immediately above. Within each metalevel, the terminology is partitioned into namespaces, and various namespaces are collected together into meaningful composites called meta-ontologies. All of the various meta-ontologies in the IFF are anchored to the IFF metastack. The IFF development is largely driven by the principles of conceptual warrant, categorical design and institutional logic.
Edge detection based on morphological amoebas
Venue: arXiv cs.CV 2011
Year: 2011

Detecting the edges of objects within images is critical for quality image processing. We present an edge-detecting technique that uses morphological amoebas that adjust their shape based on variation in image contours. We evaluate the method both quantitatively and qualitatively for edge detection of images, and compare it to classic morphological methods. Our amoeba-based edge-detection system performed better than the classic edge detectors.
Formalization of Abstract State Transition Systems for SAT
Venue: arXiv cs.LO 2011
Year: 2011

We present a formalization of modern SAT solvers and their properties in a form of abstract state transition systems. SAT solving procedures are described as transition relations over states that represent the values of the solver's global variables. Several different SAT solvers are formalized, including both the classical DPLL procedure and its state-of-the-art successors. The formalization is made within the Isabelle/HOL system and the total correctness (soundness, termination, completeness) is shown for each presented system (with respect to a simple notion of satisfiability that can be manually checked). The systems are defined in a general way and cover procedures used in a wide range of modern SAT solvers. Our formalization builds up on the previous work on state transition systems for SAT, but it gives machine-verifiable proofs, somewhat more general specifications, and weaker assumptions that ensure the key correctness properties. The presented proofs of formal correctness of the transition systems can be used as a key building block in proving correctness of SAT solvers by using other verification approaches.
Taking the Final Step to a Full Dichotomy of the Possible Winner Problem in Pure Scoring Rules
Venue: arXiv cs.CC 2011
Year: 2011

The Possible Winner problem asks, given an election where the voters' preferences over the candidates are specified only partially, whether a designated candidate can become a winner by suitably extending all the votes. Betzler and Dorn [1] proved a result that is only one step away from a full dichotomy of this problem for the important class of pure scoring rules in the case of unweighted voters and an unbounded number of candidates: Possible Winner is NP-complete for all pure scoring rules except plurality, veto, and the scoring rule with vector (2,1,...,1,0), but is solvable in polynomial time for plurality and veto. We take the final step to a full dichotomy by showing that Possible Winner is NP-complete also for the scoring rule with vector (2,1,...,1,0).
Linearization of CIF Through SOS
Venue: arXiv cs.LO 2011
Year: 2011

Linearization is the procedure of rewriting a process term into a linear form, which consist only of basic operators of the process language. This procedure is interesting both from a theoretical and a practical point of view. In particular, a linearization algorithm is needed for the Compositional Interchange Format (CIF), an automaton based modeling language. The problem of devising efficient linearization algorithms is not trivial, and has been already addressed in literature. However, the linearization algorithms obtained are the result of an inventive process, and the proof of correctness comes as an afterthought. Furthermore, the semantic specification of the language does not play an important role on the design of the algorithm. In this work we present a method for obtaining an efficient linearization algorithm, through a step-wise refinement of the SOS rules of CIF. As a result, we show how the semantic specification of the language can guide the implementation of such a procedure, yielding a simple proof of correctness.
Synchrony vs. Causality in Asynchronous Petri Nets
Venue: arXiv cs.DC 2011
Year: 2011

Given a synchronous system, we study the question whether the behaviour of that system can be exhibited by a (non-trivially) distributed and hence asynchronous implementation. In this paper we show, by counterexample, that synchronous systems cannot in general be implemented in an asynchronous fashion without either introducing an infinite implementation or changing the causal structure of the system behaviour.
Capacitated Domination: Constant Factor Approximation for Planar Graphs
Venue: arXiv cs.DS 2011
Year: 2011

We consider the capacitated domination problem, which models a service-requirement assigning scenario and which is also a generalization of the dominating set problem. In this problem, we are given a graph with three parameters defined on the vertex set, which are cost, capacity, and demand. The objective of this problem is to compute a demand assignment of least cost, such that the demand of each vertex is fully-assigned to some of its closed neighbours without exceeding the amount of capacity they provide. In this paper, we provide the first constant factor approximation for this problem on planar graphs, based on a new perspective on the hierarchical structure of outer-planar graphs. We believe that this new perspective and technique can be applied to other capacitated covering problems to help tackle vertices of large degrees.
Artificial Neural Network and Rough Set for HV Bushings Condition Monitoring
Venue: arXiv cs.NE 2011
Year: 2011

Most transformer failures are attributed to bushings failures. Hence it is necessary to monitor the condition of bushings. In this paper three methods are developed to monitor the condition of oil filled bushing. Multi-layer perceptron (MLP), Radial basis function (RBF) and Rough Set (RS) models are developed and combined through majority voting to form a committee. The MLP performs better that the RBF and the RS is terms of classification accuracy. The RBF is the fasted to train. The committee performs better than the individual models. The diversity of models is measured to evaluate their similarity when used in the committee.