Journées Montoises d'Informatique Théorique

Irisa - Rennes
to IRISA

Orateurs invités

Titres et résumés

Jean Berstel - Arbres sturmiens

Les arbres sturmiens sont une généralisation naturelle des mots sturmiens. Un arbre binaire étiqueté est sturmien s'il possède n+1 sous-arbres distincts de hauteur n pour tout n. Ce sont les arbres irrationnels de complexité minimale.
Dans cet exposé, on donne des exemples variés d'arbres sturmiens, montrant que la situation est bien plus compliquée que pour les mots. L'automate minimal infini naturellement associé à un mot sturmien a d'intéressantes propriétés. Nous caractérisons une famille d'arbres sturmiens par une propriété structurelle de leurs automates.
Ce travail a été réalisé en commun avec Luc Boasson, Olivier Carton et Isabelle Fagnot.

Valérie Berthé - Word combinatorics, tilings and discrete geometry

The aim of this lecture is to illustrate the natural interactions that exist between word combinatorics, tilings and arithmetic discrete geometry through the discussion of some discretizations of Euclidean objects or of elementary transformations (lines, planes, surfaces, rotations). We will first see how classical techniques in symbolic dynamics applied to some codings of such discretizations allow one to obtain results concerning the enumeration of configurations and their statistical properties. We will then show how natural notions such as morphisms of the free monoid in word combinatorics, or flips in tiling theory apply in an efficient way in discrete geometry (generation algorithms, recognition issues).

Daniel Kirsten - Distance Desert Automata and the Star Height Problem

In the talk, we introduce desert automata. Desert automata are non-deterministic finite automata with a set of marked transitions which are called water transitions. The weight of a path is defined as the length of a longest subpath which does not contain a water transition. The weight of a word is the minimum of the weights of all successful paths of the word. In this way, desert automata compute mappings from a free monoid to the integers. We also show some extensions of this concept which include Hashiguchi's distance automata. We consider the limitedness problems of these automata, i.e., we show that it is PSPACE-complete to decide whether the range of the mapping of a given desert automaton is finite. As an application of this result, e.g., we show the decidability and the first upper complexity bound to the star height problem.

D. Kirsten. Distance desert automata and the star height problem.
R.A.I.R.O. Informatique Théorique et Applications, special issue of long versions of selected best papers from FoSSaCS 2004, 29(3) 455--509 (2005).

Felix Klaedtke - Automata and Linear Arithmetics

As already pointed out by Büchi, automata can be used to decide certain first-order theories of linear arithmetic, like Presburger arithmetic: Integers are represented as words (e.g., using the 2's complement representation), and the automata are recursively constructed from the formulas. The constructed automaton for a formula precisely accepts the words representing integers that make the formula true. After introducing the basic concepts, I will analyze such automata-based decision procedures. The analysis provides upper and lower bounds on the automata sizes of the minimal deterministic automata for Presburger arithmetic formulas. Furthermore, I will sketch applications of this automata-based approach in infinite state model checking. Finally, I will conclude with some open research problems.

Michel Rigo - Abstract numeration systems on a regular language : a survey

In a general setting, a numeration system is a (one-to-one) map which sends nonnegative integers onto words over a finite alphabet. Usually, a numeration system is built on an increasing sequence of integers, like the powers of a given integer or the Fibonacci sequence. The corresponding representations are computed using a greedy algorithm. A classical question which goes back to the late 1960's and the celebrated Cobham's theorem deals with the recognizability of a set of integers and the relationship existing between arithmetical properties of integers and syntaxical properties of their representations : a set of integers is said to be recognizable if the language made of the representations of its elements is a regular language, i.e., a language accepted by a finite automaton.

With Pierre Lecomte, we have introduced in 2000 the notion of abstract numeration system. Consider an infinite regular language L over a totally ordered alphabet A. Ordering the words of L with respect to the genealogical ordering induced by the ordering of A gives a one-to-one correspondence between the set of nonnegative integers and L. In this general framework, we are studying various classical questions connected with numeration systems: recognizable sets of integers, preservation of recognizability under arithmetical operations, automatic sequences, representation of real numbers, periodic representations of these numbers, additive functions, ... This approach extends classical results leading to some new phenomena related to the theory of automata. In this talk, we will present some selected aspects of abstract numeration systems.

Wolfgang Thomas - The ordering of natural numbers with a unary predicate: Approaches to show decidability results

The subject of this talk are structures (N,<,P) where P is a set of natural numbers. Since the 1960's, following Büchi's theorem that the monadic second-order theory of (N,<) is decidable, many authors have studied the question which sets P can be adjoined to (N,<) without destroying this decidability result. For numerous predicates this can be shown (e.g., for the set of factorial numbers), in interesting cases (in particular, for the set of prime numbers) this is open, and so far no interesting P is known where the MSO-theory of (N,<,P) is undecidable. We give an overview of the area, addressing the recursion theoretic status of the MSO-theory of a structure (N,<,P), the approaches using automata, semigroups, and logical composition results for showing decidability, and we present a recent study of the problem using the concept of uniformly homogeneous set (joint work with Alexander Rabinovich).