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.

In this paper we will deal with the balance properties of the infinite binary words associated to β-integers when β is a quadratic simple Pisot number. Those words are the fixed points of the morphisms of the type $\varphi(A)=A^pB$, $\varphi(B)=A^q$ for $p\in\mathbb N$, $q\in\mathbb N$, $p\geq q$, where $\beta=\frac{p+\sqrt{p^2+4q}}{2}$. We will prove that such word is t-balanced with $t=1+\left[(p-1)/(p+1-q)\right]$. Finally, in the case that p < q it is known [B. Adamczewski, Theoret. Comput. Sci.273 (2002) 197–224] that the fixed point of the substitution $\varphi(A)=A^pB$, $\varphi(B)=A^q$ is not m-balanced for any m. We exhibit an infinite sequence of pairs of words with the unbalance property.

We explore the borderline between decidability and undecidability of the following question: “Let C be a class of codes. Given a machine ${\mathfrak{M}}$ of type X, is it decidable whether the language $L({{\mathfrak{M}}})$ lies in C or not?” for codes in general, ω-codes, codes of finite and bounded deciphering delay, prefix, suffix and bi(pre)fix codes, and for finite automata equipped with different versions of push-down stores and counters.

This paper describes a modification of the power set construction for the transformation of self-verifying nondeterministic finite automata to deterministic ones. Using a set counting argument, the upper bound for this transformation can be lowered from $2^n$ to $O(\frac{2^n}{\sqrt{n}}).$

A parallel communicating automata system consists of several automata working independently in parallel and communicating with each other by request with the aim of recognizing a word. Rather surprisingly, returning parallel communicating finite automata systems are equivalent to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata. Some open problems are finally formulated.

A real number x is called Δ20 if its binary expansion corresponds to a Δ20-set of natural numbers. Such reals are just the limits of computable sequences of rational numbers and hence also called computably approximable. Depending on how fast the sequences converge, Δ20-reals have different levels of effectiveness. This leads to various hierarchies of Δ20 reals. In this survey paper we summarize several recent developments related to such kind of hierarchies shown by the author and his collaborators.

The HP model is one of the most popular discretized models for attacking the protein folding problem, i.e., for the computational prediction of the tertiary structure of a protein from its amino acid sequence. It is based on the assumption that interactions between hydrophobic amino acids are the main force in the folding process. Therefore, it distinguishes between polar and hydrophobic amino acids only and tries to embed the amino acid sequence into a two- or three-dimensional grid lattice such as to maximize the number of contacts, i.e., of pairs of hydrophobic amino acids that are embedded into neighboring positions of the grid. In this paper, we propose a new generalization of the HP model which overcomes one of the major drawbacks of the original HP model, namely the bipartiteness of the underlying grid structure which severely restricts the set of possible contacts. Moreover, we introduce the (biologically well-motivated) concept of weighted contacts, where each contact gets assigned a weight depending on the spatial distance between the embedded amino acids. We analyze the applicability of existing approximation algorithms for the original HP model to our new setting and design a new approximation algorithm for this generalized model.

We consider the defect theorem in the context of labelled polyominoes, i.e., two-dimensional figures. The classical version of this property states that if a set of n words is not a code then the words can be expressed as a product of at most n - 1 words, the smaller set being a code. We survey several two-dimensional extensions exhibiting the boundaries where the theorem fails. In particular, we establish the defect property in the case of three dominoes (n × 1 or 1 × n rectangles).

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.

For polyominoes coded by their boundary word, we describe a quadratic O(n2) algorithm in the boundary length n which improves the naive O(n4) algorithm. Techniques used emanate from algorithmics, discrete geometry and combinatorics on words.

Une substitution est un morphisme de monoïdes libres : chaque lettre a pour image un mot, et l'image d'un mot est la concaténation des images de ses lettres. Cet article introduit une généralisation de la notion de substitution, où l'image d'une lettre n'est plus un mot mais un motif, c'est-à-dire un “mot à trous”, l'image d'un mot étant obtenue en raccordant les motifs correspondant à chacune de ses lettres à l'aide de règles locales. On caractérise complètement les substitutions par des motifs qui sont définies sur toute suite biinfinie, et on explique comment les construire. On montre que toute suite biinfinie qui est point fixe d'une substitution par des motifs est substitutive, c'est-à-dire est l'image, par un morphisme lettre à lettre, d'un point fixe de substitution (au sens usuel).

We present an algorithm which for any aperiodic and primitive substitution outputs a finite representation of each special word in the shift space associated to that substitution, and determines when such representations are equivalent under orbit and shift tail equivalence. The algorithm has been implemented and applied in the study of certain new invariants for flow equivalence of substitutional dynamical systems.

Duplication is the replacement of a factor w within a word by ww. This operation can be used iteratively to generate languages starting from words or sets of words. By undoing duplications, one can eventually reach a square-free word, the original word's duplication root. The duplication root is unique, if the length of duplications is fixed. Based on these unique roots we define the concept of duplication code. Elementary properties are stated, then the conditions under which infinite duplication codes exist are fully characterized; the relevant parameters are the duplication length and alphabet size. Finally, some properties of the languages generated by duplication codes are investigated.

As already 2-monotone R-automata accept NP-complete languages, we introduce a restricted variant of j-monotonicity for restarting automata, called sequential j-monotonicity. For restarting automata without auxiliary symbols, this restricted variant still yields infinite hierarchies. However, for restarting automata with auxiliary symbols, all degrees of sequential monotonicity collapse to the first level, implying that RLWW-automata that are sequentially monotone of degree j for any j ≥ 1 only accept context-free languages.

Pseudozeros are useful to describe how perturbations of polynomial coefficients affect its zeros. We compare two types of pseudozero sets: the complex and the real pseudozero sets. These sets differ with respect to the type of perturbations. The first set – complex perturbations of a complex polynomial – has been intensively studied while the second one – real perturbations of a real polynomial – seems to have received little attention. We present a computable formula for the real pseudozero set and a comparison between these two pseudozero sets. We conclude that the complex pseudozero sets have to be preferred except when the perturbed real polynomials admit non-real zeros. We also give some applications of pseudozero set in control theory.

Nous établissons quelques propriétés des mots sturmiens et classifions, ensuite, les mots infinis qui possèdent, pour tout entier naturel non nul n, exactement n+2 facteurs de longueur n. Nous définissons également la notion d'insertion k à k sur les mots infinis puis nous calculons la complexité des mots obtenus en appliquant cette notion aux mots sturmiens. Enfin nous étudions l'équilibre et la palindromie d'une classe particulière de mots de complexité n+2 que nous appelons mots quasi-sturmiens par insertion et que nous caractérisons à l'aide des vecteurs de Parikh.

This paper analyses the complexity of model checking fixpoint logic with Chop – an extension of the modal μ-calculus with a sequential composition operator. It uses two known game-based characterisations to derive the following results: the combined model checking complexity as well as the data complexity of FLC are EXPTIME-complete. This is already the case for its alternation-free fragment. The expression complexity of FLC is trivially P-hard and limited from above by the complexity of solving a parity game, i.e. in UP ∩ co-UP. For any fragment of fixed alternation depth, in particular alternation- free formulas it is P-complete.

Floating-point arithmetic provides a fast but inexact way of computing geometric predicates. In order for these predicates to be exact, it is important to rule out all the numerical situations where floating-point computations could lead to wrong results. Taking into account all the potential problems is a tedious work to do by hand. We study in this paper a floating-point implementation of a filter for the orientation-2 predicate, and how a formal and partially automatized verification of this algorithm avoided many pitfalls. The presented method is not limited to this particular predicate, it can easily be used to produce correct semi-static floating-point filters for other geometric predicates.

We study some arithmetical and combinatorial properties of β-integers for β being the larger root of the equation x2 = mx - n,m,n ∈ ℵ, m ≥ n +2 ≥ 3. We determine with the accuracy of ± 1 the maximal number of β-fractional positions, which may arise as a result of addition of two β-integers. For the infinite word uβ> coding distances between the consecutive β-integers, we determine precisely also the balance. The word uβ> is the only fixed point of the morphism A → Am-1B and B → Am-n-1B. In the case n = 1, the corresponding infinite word uβ> is sturmian, and, therefore, 1-balanced. On the simplest non-sturmian example with n≥ 2, we illustrate how closely the balance and the arithmetical properties of β-integers are related.