Search results for "Theoretical Computer Science"

Transience versus recurrence for scale-free spatial networks

2020

Weight-dependent random connection graphs are a class of local network models that combine scale-free degree distribution, small-world properties and clustering. In this paper we discuss recurrence or transience of these graphs, features that are relevant for the performance of search and information diffusion algorithms on the network.

Structural clustering of millions of molecular graphs

2014

We propose an algorithm for clustering very large molecular graph databases according to scaffolds (i.e., large structural overlaps) that are common between cluster members. Our approach first partitions the original dataset into several smaller datasets using a greedy clustering approach named APreClus based on dynamic seed clustering. APreClus is an online and instance incremental clustering algorithm delaying the final cluster assignment of an instance until one of the so-called pending clusters the instance belongs to has reached significant size and is converted to a fixed cluster. Once a cluster is fixed, APreClus recalculates the cluster centers, which are used as representatives for…

ROS/Gazebo Based Simulation of Co-operative UAVs

2019

UAVs can be assigned different tasks such as e.g., rendez-vous and space coverage, which require processing and communication capabilities. This work extends the architecture ROS/Gazebo with the possibility of simulation of co-operative UAVs. We assume UAV with the underlying attitude controller based on the open-source Ardupilot software. The integration of the co-ordination algorithm in Gazebo is implemented with software modules extending Ardupilot with the capability of sending/receiving messages to/from drones, and executing the co-ordination protocol. As far as it concerns the simulation environment, we have extended the world in Gazebo to hold more than one drone and to open a specif…

The dual equivalence of equations and coequations for automata

2015

The transition structure α : X ? X A of a deterministic automaton with state set X and with inputs from an alphabet A can be viewed both as an algebra and as a coalgebra. We use this algebra-coalgebra duality as a common perspective for the study of equations and coequations. For every automaton ( X , α ) , we define two new automata: free ( X , α ) and cofree ( X , α ) representing, respectively, the greatest set of equations and the smallest set of coequations satisfied by ( X , α ) . Both constructions are shown to be functorial. Our main result is that the restrictions of free and cofree to, respectively, preformations of languages and to quotients A * / C of A * with respect to a congr…

Distributed Pseudo-Gossip Algorithm and Finite-Length Computational Codes for Efficient In-Network Subspace Projection

2013

In this paper, we design a practical power-efficient algorithm for Wireless Sensor Networks (WSN) in order to obtain, in a distributed manner, the projection of an observed sampled spatial field on a subspace of lower dimension. This is an important problem that is motivated in various applications where there are well defined subspaces of interest (e.g., spectral maps in cognitive radios). As opposed to traditional Gossip Algorithms used for subspace projection, where separation of channel coding and computation is assumed, our algorithm combines binary finite-length Computational Coding and a novel gossip-like protocol with certain communication rules, achieving important savings in conve…

Channel selection in Cognitive Radio Networks: A Switchable Bayesian Learning Automata approach

2013

We consider the problem of a user operating within a Cognitive Radio Network (CRN) which involves N channels each associated with a Primary User (PU). The problem consists of allocating a channel which, at any given time instant is not being used by a PU, to a Secondary User (SU). Within our study, we assume that a SU is allowed to perform “channel switching”, i.e., to choose an alternate channel S times (where S +1 ≤ N) if the previous choice does not lead to a channel which is vacant. The paper first presents a formal probabilistic model for the problem itself, referred to as the Formal Secondary Channel Selection (FSCS) problem, and the characteristics of the FSCS are then analyzed. Ther…

Connectivity and Transformation in Work-Related Learning – Theoretical Foundations

2008

Discrete and Conservative Factorizations in Fib(B)

2021

AbstractWe focus on the transfer of some known orthogonal factorization systems from$$\mathsf {Cat}$$Catto the 2-category$${\mathsf {Fib}}(B)$$Fib(B)of fibrations over a fixed base categoryB: the internal version of thecomprehensive factorization, and the factorization systems given by (sequence of coidentifiers, discrete morphism) and (sequence of coinverters, conservative morphism) respectively. For the class of fibrewise opfibrations in$${\mathsf {Fib}}(B)$$Fib(B), the construction of the latter two simplify to a single coidentifier (respectively coinverter) followed by an internal discrete opfibration (resp. fibrewise opfibration in groupoids). We show how these results follow from thei…

Tabu search for min-max edge crossing in graphs

2020

Abstract Graph drawing is a key issue in the field of data analysis, given the ever-growing amount of information available today that require the use of automatic tools to represent it. Graph Drawing Problems (GDP) are hard combinatorial problems whose applications have been widely relevant in fields such as social network analysis and project management. While classically in GDPs the main aesthetic concern is related to the minimization of the total sum of crossing in the graph (min-sum), in this paper we focus on a particular variant of the problem, the Min-Max GDP, consisting in the minimization of the maximum crossing among all egdes. Recently proposed in scientific literature, the Min…

Languages with mismatches

2007

AbstractIn this paper we study some combinatorial properties of a class of languages that represent sets of words occurring in a text S up to some errors. More precisely, we consider sets of words that occur in a text S with k mismatches in any window of size r. The study of this class of languages mainly focuses both on a parameter, called repetition index, and on the set of the minimal forbidden words of the language of factors of S with errors. The repetition index of a string S is defined as the smallest integer such that all strings of this length occur at most in a unique position of the text S up to errors. We prove that there is a strong relation between the repetition index of S an…