The calculus of looping sequences is a formalism for describing theevolution of biological systems by means of term rewriting rules. Inthis paper we enrich this calculus with a type discipline whichpreserves some biological properties depending on the minimum andthe maximum number of elements of some type requested by the present elements. The typesystem enforces these properties and typed reductions guarantee thatevolution preserves them. As an example, we model the hemoglobinstructure and the equilibrium between cell death and division: typedreductions prevent undesirable behaviors.

We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.

This paper studies the computational complexity of the properinterval colored graph problem (PICG), when the input graphis a colored caterpillar, parameterized by hair length. In order prove ourresult we establish a close relationship between the PICG anda graph layout problem the proper colored layout problem(PCLP). We show a dichotomy: the PICG and thePCLP are NP-complete for colored caterpillars of hair length ≥2, while both problems are in P for colored caterpillarsof hair length <2.For the hardness results we provide a reduction from the multiprocessor scheduling problem, while the polynomial time resultsfollow from a characterization in terms of forbidden subgraphs.

Motivated by a problem posed by Hamming in 1980, we define even codes. They are Huffman type prefix codes with the additional property of being able to detect the occurrence of an odd number of 1-bit errors in the message. We characterize optimal even codes and describe a simple method for constructing the optimal codes. Further, we compare optimal even codes with Huffman codes for equal frequencies. We show that the maximum encoding in an optimal even code is at most two bits larger than the maximum encoding in a Huffman tree. Moreover, it is always possible to choose an optimal even code such that this difference drops to 1 bit. We compare average sizes and show that the average size of an encoding in a optimal even tree is at least 1/3 and at most 1/2 of a bit larger than that of a Huffman tree. These values represent the overhead in the encoding sizes for having the ability to detect an odd number of errors in the message. Finally, we discuss the case of arbitrary frequencies and describe some results for this situation.

A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in time polynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and certain well-known properties of $\mathbb{Z}$-rational sequences.

We consider conditional tabled Lindenmayer sytems without interaction, where each table is associated with a regular set and a table can only be applied to a sentential form which is contained in its associated regular set. We study the effect to the generative power, if we use instead of arbitrary regular languages only finite, nilpotent, monoidal, combinational, definite, ordered, union-free, star-free, strictly locally testable, commutative regular, circular regular, and suffix-closed regular languages. Essentially, we prove that the hierarchy of language families obtained from conditional Lindenmayer systems with subregular conditions is almost identical to the hierarchy of families of subregular languages.

The product w = u ⊗ v of two sequences u and v is a naturally defined sequence on the alphabet of pairs of symbols. Here, we study when the product w of two balanced sequences u,v is balanced too. In the case u and v are binary sequences, we prove, as a main result, that, if such a product w is balanced and deg(w) = 4, then w is an ultimately periodic sequence of a very special form. The case of arbitrary alphabets is approached in the last section. The partial results obtained and the problems proposed show the interest of the notion of product in the study of balanced sequences.

Joint 2-adic complexity is a new important index of the cryptographic security for multisequences. In this paper, we extend the usual Fourier transform to the case of multisequences and derive an upper bound for the joint 2-adic complexity. Furthermore, for the multisequences with pn-period, we discuss the relation between sequences and their Fourier coefficients. Based on the relation, we determine a lower bound for the number of multisequences with given joint 2-adic complexity.

We construct, for each integer n, three functions from {0,1}n to {0,1} such that any boolean mapping from {0,1}n to {0,1}n can be computed with a finite sequence of assignations only using the n input variables and those three functions.

We prove that the function that maps a word of a rational language onto its successor for the radix order in this language is a finite union of co-sequential functions.

For both the edge deletion heuristic and the maximum-degree greedy heuristic, we studythe problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of r, where r is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to NP. To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs for which either of these heuristics can find an optimal solution remains NP-hard.

The fixed point submonoid of an endomorphism of a free product of a free monoid and cyclic groups is proved to be rational using automata-theoretic techniques. Maslakova’s result on the computability of the fixed point subgroup of a free group automorphism is generalized to endomorphisms of free products of a free monoid and a free group which are automorphisms of the maximal subgroup.

The paper presents an elementary approach for the calculation of the entropy of a class of languages. This approach is based on the consideration of roots of a real polynomial and is also suitable for calculating the Bernoulli measure. The class of languages we consider here is a generalisation of the Łukasiewicz language.

We investigate the Sandpile Model and Chip Firing Game and an extension of these modelson cycle graphs. The extended model consists of allowing a negative number of chips ateach vertex. We give the characterization of reachable configurations and of fixed pointsof each model. At the end, we give explicit formula for the number of their fixedpoints.

It is known that the class of factorizing codes, i.e.,codes satisfying the factorization conjectureformulated by Schützenberger, isclosed under two operations:the classicalcomposition of codes and substitutionof codes.A natural question which arisesis whethera finite set Oof operations existssuch that each factorizingcode can be obtained by usingthe operations inO and starting with prefix or suffix codes.O is named herea complete setof operations (for factorizing codes).We show that composition and substitutionare not enough in order to obtaina completeset. Indeed, we exhibit a factorizing code over a two-letter alphabet A = {a,b}, precisely a 3-code, which cannot beobtained by decomposition or substitution.

For any finite word w on a finite alphabet, we consider the basic parameters Rw and Kw of w defined as follows: Rw is the minimal natural number for which w has no right special factor of length Rw and Kw is the minimal natural number for which w has no repeated suffix of length Kw. In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.

We introduce and investigate several variants of a bidirectional string assemblingsystem, which is a computational model that generates strings from copies of assemblyunits. The underlying mechanism is based on two-sided piecewise assembly of adouble-stranded sequence of symbols, where the upper and lower strand have to match. Thegenerative capacities and the relative power of the variants are our main interest. Inparticular, we prove that bidirectional string assembling system generate languages notrepresented as any finite concatenation of one-sided string assembling systems. The latterbuild an infinite, strict and tight concatenation hierarchy. Moreover, it is shown thateven the strongest system in question can only generate NL languages, while there areunary regular languages that cannot be derived. Furthermore, a finite strict hierarchywith respect to the different variants considered is shown and closure properties of thelanguages generated are presented.

It is well-known that some of the most basic properties of words, like the commutativity (xy = yx) and the conjugacy (xz = zy), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation xMyN = zP has only periodic solutions in a free monoid, that is, if xMyN = zP holds with integers m,n,p ≥ 2, then there exists a word w such that x, y, z are powers of w. This result, which received a lot of attention, was first proved by Lyndon and Schützenberger for free groups. In this paper, we investigate equations on partial words. Partial words are sequences over a finite alphabet that may contain a number of “do not know” symbols. When we speak about equations on partial words, we replace the notion of equality (=) with compatibility (↑). Among other equations, we solve xy ↑ yx, xz ↑ zy, and special cases of xmyn ↑ zp for integers m,n,p ≥ 2. 


In the literature various types of restarting automata have been studied that are basedon contextual rewriting. A word w is accepted by such an automaton if,starting from the initial configuration that corresponds to input w, theword w is reduced to the empty word by a finite number of applications ofthese contextual rewritings. This approach is reminiscent of the notion of McNaughtonfamilies of languages. Here we put the aforementioned types of restarting automata intothe context of McNaughton families of languages, relating the classes of languagesaccepted by these automata in particular to the class GCSL of growing context-sensitivelanguages and to the class CRL of Church–Rosser languages.

We study two topological properties of the 5-ary n-cube $Q_{n}^{5}$. Given two arbitrary distinct nodes x and y in $Q_{n}^{5}$, we prove that there exists an x-y path of every length ranging from 2n to 5n - 1, where n ≥ 2. Based on this result, we prove that $Q_{n}^{5}$ is 5-edge-pancyclic by showing that every edge in $Q_{n}^{5}$ lies on a cycle of every length ranging from 5 to 5n.