We present two methods based on decimation for computing finite billiard words on any finite alphabet. The first method computes finite billiard words by iteration of some transformation on words. The number of iterations is explicitly bounded. The second one gives a direct formula for the billiard words. Some results remain true for infinite standard Sturmian words, but cannot be used for computation as they only are limit results.

This contribution extends the notions of roots and periodicity to strings of transfinite lengths. It shows that given a transfinite string, either it possesses a unique root or the set of its roots are equivalent in a strong way.

In the XML standard, data are represented as unranked labeledordered trees. Regular unranked tree automata provide a usefulformalism for the validation of schemas enforcing regular structuralconstraints on XML documents. However some concrete applicationcontexts need the expression of more general constraints than theregular ones. In this paper we propose a new framework in whichcontext-free style structural constraints can be expressed andvalidated. This framework is characterized by: (i) the introductionof a new notion of trees, the so-called typed unranked labeledtrees (tulab trees for short) in which each node receivesone of three possible types (up, down or fix), and (ii) thedefinition of a new notion of tree automata, the so-callednested sibling tulab tree automata, able to enforcecontext-free style structural constraints on tulab tree languages.During their structural control process, such automata are usingvisibly pushdown languages of words [R. Alur and P. Madhusudan, Visibly pushdown languages, 36th ACM symposium on Theory of Computing, Chicago, USA (2004) 202–211] on theiralphabet of states. We show that the resulting class NSTL oftulab tree languages recognized by nested sibling tulab treeautomata is robust, i.e. closed under Boolean operations and withdecision procedures for the classical membership, emptiness andinclusion problems. We then give three characterizations of NSTL :a logical characterization by defining an adequate logic in whichNSTL happens to coincide with the models of monadic second ordersentences; the two other characterizations are using adequateencodings and map together languages of NSTL with some regularsets of 3-ary trees or with particular sets of binary trees.

In this paper, we define k-counting automata as recognizers forω-languages, i.e. languages of infinite words. Weprove that the class of ω-languages they recognize is a proper extensionof the ω-regular languages. In addition we prove that languagesrecognized by k-counting automata are closed under Boolean operations. Itremains an open problem whether or not emptiness is decidable fork-counting automata. However, we conjecture strongly that it is decidableand give formal reasons why we believe so.

This paper is a contribution to the general tiling problem for the hyperbolic plane. It is an intermediary result between the result obtained by R. Robinson [Invent. Math.44 (1978) 259–264] and the conjecture that the problem is undecidable.

We add a sufficient condition for validity of Propo- sition 4.10 in the paper Frougny et al. (2004). This condition is not a necessary one, it is nevertheless convenient, since anyway most of the statements in the paper Frougny et al. (2004) use it.


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.

Classically, in order to resolve an equation u ≈ v over a free monoid X*, we reduce it by a suitable family $\cal F$ of substitutions to a family of equations uf ≈ vf, $f\in\cal F$, each involving less variables than u ≈ v, and then combine solutions of uf ≈ vf into solutions of u ≈ v. The problem is to get $\cal F$ in a handy parametrized form. The method we propose consists in parametrizing the path traces in the so called graph of prime equations associated to u ≈ v. We carry out such a parametrization in the case the prime equations in the graph involve at most three variables.

Pattern avoidance is an important topic in combinatorics on words which dates back to the beginning of the twentieth century when Thue constructed an infinite word over a ternary alphabet that avoids squares, i.e., a word with no two adjacent identical factors. This result finds applications in various algebraic contexts where more general patterns than squares are considered. On the other hand, Erdős raised the question as to whether there exists an infinite word that avoids abelian squares, i.e., a word with no two adjacent factors being permutations of one another. Although this question was answered affirmately years later, knowledge of abelian pattern avoidance is rather limited. Recently, (abelian) pattern avoidance was initiated in the more general framework of partial words, which allow for undefined positions called holes. In this paper, we show that any pattern p with n> 3 distinct variables of length at least 2n is abelian avoidable by a partial word with infinitely many holes, the bound on the length of p being tight. We complete the classification of all the binary and ternary patterns with respect to non-trivial abelian avoidability, in which no variable can be substituted by only one hole. We also investigate the abelian avoidability indices of the binary and ternary patterns.

LetLϕ,λ = {ω ∈ Σ∗| ϕ(ω) > λ} be thelanguage recognized by a formal seriesϕ:Σ∗ → ℝ with isolated cut pointλ. We provide new conditions that guarantee the regularity of thelanguage Lϕ,λ in the case thatϕ is rational or ϕ is a Hadamard quotient of rationalseries. Moreover the decidability property of such conditions is investigated.

We answer to a question of De Luca and Restivo whether there exists a circular code which is maximal as circular code and not as code.

In this work we study some probabilistic models for the random generation of words over a given alphabet used in the literature in connection with pattern statistics. Our goal is to compare models based on Markovian processes (where the occurrence of a symbol in a given position only depends on a finite number of previous occurrences) and the stochastic models that can generate a word of given length from a regular language under uniform distribution. We present some results that show the differences between these two stochastic models and their relationship with the rational probabilistic measures.

In the last decade, formal methods have proved their interest whenanalyzing security protocols. Security protocols require inparticular to reason about the attacker knowledge. Two standardnotions are often considered in formal approaches: deducibility andindistinguishability relations. The first notion states whether anattacker can learn the value of a secret, while the latter stateswhether an attacker can notice some difference between protocol runswith different values of the secret. Several decision procedureshave been developed so far for both notions but none of them can beapplied in the context of e-voting protocols, which requirededicated cryptographic primitives. In this work, we show that bothdeduction and indistinguishability are decidable in polynomial timefor two theories modeling the primitives of e-voting protocols.

This paper is the first step in thesolution of the problem of finite completion of comma-free codes.We show that every finite comma-free code is included in afinite comma-free code of particular kind, which we called, for lack of a better term, canonical comma-free code. Certainly, finite maximal comma-free codesare always canonical. The final step of the solution which consistsin proving further that every canonical comma-free code is completedto a finite maximal comma-free code, is intended to be published in a forthcomingpaper.

Entity and referential integrity are the most fundamental constraints that any relational database should satisfy. We re-examine these fundamental constraints in the context of incomplete relations, which may have null values of the types "value exists but is unknown" and "value does not exist" . We argue that in practice the restrictions that these constraints impose on the occurrences of null values in relations are too strict. We justify a generalisation of the said constraints wherein we use key families, which are collections of attribute sets of a relation schema, rather than keys, and foreign key families which are collections of pairs of attribute sets of two relation schemas, rather than foreign keys. Intuitively, a key family is satisfied in an incomplete relation if each one of its tuples is uniquely identifiable on the union of the attribute sets of the key family, in all possible worlds of the incomplete relation, and, in addition, is distinguishable from all the other tuples in the incomplete relation by its nonnull values on some element in the key family. Our proposal can be viewed as an extension of Thalheim's key set, which only deals with null values of type "value exists but is unknown" . The intuition behind the satisfaction of a foreign key family in an incomplete database is that each pair $(F_i, K_i)$ of attribute sets in the foreign key family takes the foreign key attribute values over Fi of a tuple in one incomplete relation referencing the key attribute values over Ki of a tuple in another incomplete relation. Such referencing is defined only in the case when the foreign key attribute values do not have any null values of the type "value does not exist" ; we insist that the referencing be defined for at least one such pair. We also investigate some combinatorial properties of key families, and show that they are comparable to the standard combinatorial properties of keys.

This note is about functions ƒ : Aω → Bω whose graph is recognized by a Büchi finite automaton on the product alphabet A x B. These functions are Baire class 2 in the Baire hierarchy of Borel functions and it is decidable whether such function are continuous or not. In 1920 W. Sierpinski showed that a function $f : \mathbb{ R} \rightarrow \mathbb{R} $ is Baire class 1 if and only if both the overgraph and the undergraph of f are Fσ. We show that such characterization is also true for functions on infinite words if we replace the real ordering by the lexicographical ordering on Bω. From this we deduce that it is decidable whether such function are of Baire class 1 or not. We extend this result to real functions definable by automata in Pisot base.

A Σ-labeled n-poset is an (at most) countable set, labeled in the set Σ, equipped with n partial orders. The collection of all Σ-labeled n-posets is naturally equipped with n binary product operations and nω-ary product operations. Moreover, the ω-ary product operations give rise to nω-power operations. We show that those Σ-labeled n-posets that can be generated from the singletons by the binary and ω-ary product operations form the free algebra on Σ in a variety axiomatizable by an infinite collection of simple equations. When n = 1, this variety coincides with the class of ω-semigroups of Perrin and Pin. Moreover, we show that those Σ-labeled n-posets that can be generated from the singletons by the binary product operations and the ω-power operations form the free algebra on Σ in a related variety that generalizes Wilke's algebras. We also give graph-theoretic characterizations of those n-posets contained in the above free algebras. Our results serve as a preliminary study to a development of a theory of higher dimensional automata and languages on infinitary associative structures.

We study the problem of learning regular tree languages from text. We show that the framework of function distinguishability, as introduced by the author in [Theoret. Comput. Sci.290 (2003) 1679–1711], can be generalized from the case of string languages towards tree languages. This provides a large source of identifiable classes of regular tree languages. Each of these classes can be characterized in various ways. Moreover, we present a generic inference algorithm with polynomial update time and prove its correctness. In this way, we generalize previous works of Angluin, Sakakibara and ourselves. Moreover, we show that this way all regular tree languages can be approximately identified.