Source author record

Jean Berstel

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Formal Languages and Automata Theory Discrete Mathematics math.CO math.DS

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2011arXiv

Bifix codes and Sturmian words

We prove new results concerning the relation between bifix codes, episturmian words and subgroups offree groups. We study bifix codes in factorial sets of words. We generalize most properties of ordinary maximal bifix codes to bifix codes maximal in a recurrent set $F$ of words ( $F$ -maximal bifix codes). In the case of bifix codes contained in Sturmian sets of words, we obtain several new results. Let $F$ be a Sturmian set of words, defined as the set of factors of a strict episturmian word. Our results express the fact that an $F$ -maximal bifix code of degree $d$ behaves just as the set of words of $F$ of length $d$ . An $F$ -maximal bifix code of degree $d$ in a Sturmian set of words on an alphabet with $k$ letters has $(k-1)d+1$ elements. This generalizes the fact that a Sturmian set contains $(k-1)d+1$ words of length $d$ . Moreover, given an infinite word $x$ , if there is a finite maximal bifix code $X$ of degree $d$ such that $x$ has at most $d$ factors of length $d$ in $X$ , then $x$ is ultimately periodic. Our main result states that any $F$ -maximal bifix code of degree $d$ on the alphabet $A$ is the basis of a subgroup of index $d$ of the free group on~ $A$ .

preprint2011arXiv

Splicing systems and the Chomsky hierarchy

In this paper, we prove decidability properties and new results on the position of the family of languages generated by (circular) splicing systems within the Chomsky hierarchy. The two main results of the paper are the following. First, we show that it is decidable, given a circular splicing language and a regular language, whether they are equal. Second, we prove the language generated by an alphabetic splicing system is context-free. Alphabetic splicing systems are a generalization of simple and semi-simple splicin systems already considered in the literature.

preprint2011arXiv

Symbolic dynamics

This chapter presents some of the links between automata theory and symbolic dynamics. The emphasis is on two particular points. The first one is the interplay between some particular classes of automata, such as local automata and results on embeddings of shifts of finite type. The second one is the connection between syntactic semigroups and the classification of sofic shifts up to conjugacy.

preprint2010arXiv

Minimization of Automata

This chapter is concerned with the design and analysis of algorithms for minimizing finite automata. Getting a minimal automaton is a fundamental issue in the use and implementation of finite automata tools in frameworks like text processing, image analysis, linguistic computer science, and many other applications. There are two main families of minimization algorithms. The first by a sequence of refinements of a partition of the set of states, the second by a sequence of fusions or merges of states. Hopcroft's and Moore's algorithms belong to the first family, the linear-time minimization of acyclic automata of Revuz belongs to the second family. One of our studies is upon the comparison of the nature of Moore's and Hopcroft's algorithms. This gives some new insight in both algorithms. As we shall see, these algorithms are quite different both in behavior and in complexity. In particular, we show that it is not possible to simulate the computations of one of the algorithm by the other. We describe the minimization algorithm by fusion for so-called local automata. A special case of minimization is the construction o minimal automata for finite sets. We consider briefly this case, and in particular describe incremental algorithms. Finally, we consider the case of updating a minimal automaton when a word is added or removed from the set it recognizes.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jean Berstel

Research overview

Is this your work?

4 publications

Bifix codes and Sturmian words

Splicing systems and the Chomsky hierarchy

Symbolic dynamics

Minimization of Automata

See the researcher in context

Building this map preview