On a conjecture about finite fixed points of morphisms

A conjecture of M. Billaud is: given a word $w$, if, for each letter x occurring in $w$, the word obtained by erasing all the occurrences of x in $w$ is a fixed point of a nontrivial morphism $f_x$, then $w$ is also a fixed point of a non-trivial morphism. We prove that this conjecture is equivalent to a similar one on sets of words. Using this equivalence, we solve these conjectures in the particular case where each morphism $f_x$ has only one expansive letter.     

On locally reversible languages

There exist several works that study the class of reversible languages defined as the union closure of 0-reversible languages, their properties and suitable representations. In this work we define and study the class of locally reversible languages, defined as the union closure of $k$-reversible languages. We characterize the class and prove that it is a local (positive) variety of formal languages. We also extend the definition of quasi-reversible automata to deal with locally reversible languages and propose a polynomial algorithm to obtain, for any given locally $k$-reversible language, a quasi-$k$-reversible automaton.     

Pancyclic out-arcs of a vertex in oriented graphs

Let D be an oriented graph with $n?9$ vertices and minimum degree at least $n?2$, such that, for any two vertices x and y, either x dominates y or $d_D^{+}(x)+d_D^{?}(y)?n?3$. Song (1994) [5] proved that D is pancyclic. Bang-Jensen and Guo (1999) [2] proved, based on Song?s result, that D is vertex pancyclic. In this article, we give a sufficient condition for D to contain a vertex whose out-arcs are pancyclic in D, when $n?14$.     

Avoiding large squares in infinite binary words

We consider three aspects of avoiding large squares in infinite binary words. First, we construct an infinite binary word avoiding both cubes xxx and squares yy with $\left|y\right|⩾4$; our construction is somewhat simpler than the original construction of Dekking. Second, we construct an infinite binary word avoiding all squares except $0^2$, $1^2$, and $(01{)}^2$; our construction is somewhat simpler than the original construction of Fraenkel and Simpson. In both cases, we also show how to modify our construction to obtain exponentially many words of length n with the given avoidance properties. Finally, we answer an open question of Prodinger and Urbanek from 1979 by demonstrating the existence of two infinite binary words, each avoiding arbitrarily large squares, such that their perfect shuffle has arbitrarily large squares.     

Bounds on the cover time of parallel rotor walks

The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider the cover time of such a system, i.e., the number of steps after which each node has been visited by at least one walk, regardless of the initialization of the walks. We show that for any graph with m edges and diameter D, this cover time is at most $\mathrm{\Theta }(mD/\log k)$ and at least $\mathrm{\Theta }(mD/k)$, which corresponds to a speedup of between $\mathrm{\Theta }(\log k)$ and $\mathrm{\Theta }(k)$ with respect to the cover time of a single walk.     

Precise contact motion planning for deformable planar curved shapes

We present a precise contact motion planning algorithm for a deformable robot in a planar environment with stationary obstacles. The robot and obstacles are both represented with $C^1$-continuous implicit or parametric curves. The robot is changing its shape using a single degree of freedom (via a one-parameter family of deformable curves). In order to reduce the dimensionality of the configuration space, geometrically constrained yet collision free contact motions are sought, that have $K(=2,3)$ simultaneous tangential contact points between the robot and the obstacles. The $K$-contact motion analysis effectively reduces the degrees of freedom of the robot, which enables a more efficient motion planning. The geometric conditions for the $K$-contact motions can be formulated as a system of non-linear polynomial equations, which can be solved precisely using a multivariate equation solver. The solutions for $K$-contact motions are represented as curves in a 4-dimensional $(x,y,\theta ,t)$ space, where $x,y,\theta$ are the degrees of freedom of the rigid motion and $t$ is the deformation’s parameter. Using the graph structure of the solution curves for the $K$-contact motions, our algorithm efficiently finds a feasible path connecting two configurations via a graph searching algorithm, whenever available. We demonstrate the effectiveness of the proposed approach using several examples.     

Uniform unweighted set cover: The power of non-oblivious local search

We are given $n$ base elements and a finite collection of subsets of them. The size of any subset varies between $p$ to $k$ ($p<k$). In addition, we assume that the input contains all possible subsets of size $p$. Our objective is to find a subcollection of minimum-cardinality which covers all the elements. This problem is known to be NP-hard. We provide two approximation algorithms for it, one for the generic case, and an improved one for the special case of $(p,k)=(2,4)$.The algorithm for the generic case is a greedy one, based on packing phases: at each phase we pick a collection of disjoint subsets covering $i$ new elements, starting from $i=k$ down to $i=p+1$. At a final step we cover the remaining base elements by the subsets of size $p$. We derive the exact performance guarantee of this algorithm for all values of $k$ and $p$, which is less than $H_k$, where $H_k$ is the $k$’th harmonic number. However, the algorithm exhibits the known improvement methods over the greedy one for the unweighted $k$-set cover problem (in which subset sizes are only restricted not to exceed $k$), and hence it serves as a benchmark for our improved algorithm.The improved algorithm for the special case of $(p,k)=(2,4)$ is based on non-oblivious local search: it starts with a feasible cover, and then repeatedly tries to replace sets of size 3 and 4 so as to maximize an objective function which prefers big sets over small ones. For this case, our generic algorithm achieves an asymptotic approximation ratio of $1.5+?$, and the local search algorithm achieves a better ratio, which is bounded by $1.458333\dots +?$.