International Journal of Foundations of Computer Science

In this paper, we introduce some basic measures for insertion-deletion system and matrix insertion-deletion system. These measures are based on the number of variables, the number of productions and the number of symbols in a grammar. We show that with respect to these measures, both the systems are more succinct over context-free grammars in representing certain families of context-free languages.

We introduce a new generalization of weighted automata – automata with auxiliary weights. They allow to compute several quantities not directly computable over semirings by generalizing both semiring addition and semiring multiplication. Moreover, our automata retain key properties of ordinary weighted automata. We prove that automata over multi-hemirings of Droste and Kuich [7] can be modelled using our framework, and that automata with auxiliary weights can be used to describe several additional settings. Finally, we introduce rational expressions with auxiliary weights and prove that they are equivalent to our automata.

We consider the problem of exploration of networks, some of whose edges are faulty. A mobile agent, situated at a starting node and unaware of which edges are faulty, has to explore the connected fault-free component of this node by visiting all of its nodes. The cost of the exploration is the number of edge traversals. For a given network and given starting node, the overhead of an exploration algorithm is the worst-case ratio (taken over all fault configurations) of its cost to the cost of an optimal algorithm which knows where faults are situated. An exploration algorithm, for a given network and given starting node, is called perfectly competitive if its overhead is the smallest among all exploration algorithms not knowing the location of faults. We design a perfectly competitive exploration algorithm for any ring, and show that, for networks modeled by hamiltonian graphs, the overhead of any DFS exploration is at most 10/9 times larger than that of a perfectly competitive algorithm. Moreover, for hamiltonian graphs of size at least 24, this overhead is less than 6% larger than that of a perfectly competitive algorithm.

A connected dominating set (CDS, for short) for graph G is a dominating set which induces a connected subgraph of G. In this paper, we consider the problem of finding a minimum CDS for unit disk graphs, which have recently attracted considerable attention as a model of virtual backbone in multi-hop wireless networks. This optimization problem is known to be NP-hard and many approximation algorithms have been proposed in the literature. This paper proves a lower bound on the performance ratio of a greedy algorithm of Guha and Khuller which was originally proposed for general graphs and is known to be a representative in which the lookahead plays a crucial role in selecting a vertex to be contained in the CDS. More specifically, we show that for any fixed $\epsilon >0$ and integer $n_0\ge 1$, there is a unit disk graph with bounded degree consisting of at least $n_0$ vertices for which the output of the greedy algorithm is no better than $3-\epsilon$ times of an optimum solution to the same graph.

A rumor spreading model for the web forums based on the heterogeneity of the web forum user behaviors and SEIR model is proposed in this paper. First, according to the meanfield equations of the model on inhomogeneous networks, the critical threshold of the spreading of rumor is deduced; Then the simulation and numerical analysis of the model itself and the influences of trust mechanism to the model are given, which verify the validity of the model and the introduction of trust mechanism can effectively reduce the rumor influence, the velocity of rumor spreading and the rumor size; Finally, combined with the previous conclusions and the high-influence limited trust relationships between the web forum users, a high-influence immunization algorithm is given. The experimental results show that the algorithm able to reach better effect than traditional immunization algorithm.

It is well known that the resulting language obtained by inserting a regular language to a regular language is regular. We study the nondeterministic and deterministic state complexity of the insertion operation. Given two incomplete DFAs of sizes m and n, we give an upper bound $(m+2)·2^{mn-m-1}·3^m$ and find a lower bound for an asymp-totically tight bound. We also present the tight nondeterministic state complexity by a fooling set technique. The deterministic state complexity of insertion is $2^{\Theta (mn)}$ and the nondeterministic state complexity of insertion is precisely $mn+2m$, where m and n are the size of input finite automata. We also consider the state complexity of insertion in the case where the inserted language is bifix-free or non-returning.

In this paper, 2-adic complexity of two classes of generalized cyclotomic binary sequences is investigated. The sequences in the first class have period $p(p+4)$, and their 2-adic complexity attains the maximum, where both p and $p+4$ are primes, and gcd$(p-1,p+3)=2$. The sequences in the second one have period $p^2$, and their 2-adic complexity also reaches the maximum if p is an odd prime with $p\cancel{\equiv }5,19$ (mod 24).