The repetition threshold is a measure of the extent to which there need to be consecutive (partial) repetitions of finite words within infinite words over alphabets of various sizes. Dejean's Conjecture, which has been recently proven, provides this threshold for all alphabet sizes. Motivated by a question of Krieger, we deal here with the analogous threshold when the infinite word is restricted to be a D0L word. Our main result is that, asymptotically, this threshold does not exceed the unrestricted threshold by more than a little.

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O log (p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

A word u defined over an alphabet $\mathcal A$ is c-balanced (c∈$\mathbb N$) if for all pairs of factors v, w of u of the same length and for all letters a∈$\mathcal A$, the difference between the number of letters a in v and w is less or equal to c. In this paper we consider a ternary alphabet $\mathcal A$ = {L, S, M} and a class of substitutions $\varphi_p$ defined by $\varphi_p$(L) = LpS, $\varphi_p$(S) = M, $\varphi_p$(M) = Lp–1S where p> 1. We prove that the fixed point of $\varphi_p$, formally written as $\varphi_p^\infty$(L), is 3-balanced and that its Abelian complexity is bounded above by the value 7, regardless of the value of p. We also show that both these bounds are optimal, i.e. they cannot be improved.

In a previous paper, we have described the construction of an automaton from a rational expression which has the property that the automaton built from an expression which is itself computed from a co-deterministic automaton by the state elimination method is co-deterministic. It turned out that the definition on which the construction is based was inappropriate, and thus the proof of the property was flawed. We give here the correct definition of the broken derived terms of an expression which allow to define the automaton and the detailed full proof of the property.

Analyzing genomic data for finding those gene variations which are responsible for hereditary diseases is one of the great challenges in modern bioinformatics. In many living beings (including the human), every gene is present in two copies, inherited from the two parents, the so-called haplotypes. In this paper, we propose a simple combinatorial model for classifying the set of haplotypes in a population according to their responsibility for a certain genetic disease. This model is based on the minimum-ones 2SAT problem with uniform clauses. The minimum-ones 2SAT problem asks for a satisfying assignment to a satisfiable formula in 2CNF which sets a minimum number of variables to true. This problem is well-known to be $\mathcal{NP}$-hard, even in the case where all clauses are uniform, i.e., do not contain a positive and a negative literal. We analyze the approximability and present the first non-trivial exact algorithm for the uniform minimum-ones 2SAT problem with a running time of $\mathcal{O}$(1.21061n) on a 2SAT formula with n variables. We also show that the problem is fixed-parameter tractable by showing that our algorithm can be adapted to verify in $\mathcal{O}^*$(2k) time whether an assignment with at most k true variables exists.

A modified version of the classical µ-operator as well as the first value operator and the operator of inverting unary functions, applied in combination with the composition of functions and starting from the primitive recursive functions, generate all arithmetically representable functions. Moreover, the nesting levels of these operators are closely related to the stratification of the arithmetical hierarchy. The same is shown for some further function operators known from computability and complexity theory. The close relationships between nesting levels of operators and the stratification of the hierarchy also hold for suitable restrictions of the operators with respect to the polynomial hierarchy if one starts with the polynomial-time computable functions. It follows that questions around P vs. NP and NP vs. coNP can equivalently be expressed by closure properties of function classes under these operators. The polytime version of the first value operator can be used to establish hierarchies between certain consecutive levels within the polynomial hierarchy of functions, which are related to generalizations of the Boolean hierarchies over the classes $\mbox{$\Sigma^p_{k}$}$.