Minimizing local automata (2009)
Abstract — We design an algorithm that minimizes irreducible deterministic local automata by a sequence of state mergings. Two states can be merged if they have exactly the same outputs. The...
Minimizing local automata (2008)
Abstract — We design an algorithm that minimizes irreducible deterministic local automata by a sequence of state mergings. Two states can be merged if they have exactly the same outputs. The...
A hierarchy of shift equivalent sofic shifts (2008)
Marie-pierre Béal, Francesca Fiorenzi, Dominique Perrin
We define new subclasses of the class of irreducible sofic shifts. These classes form an infinite hierarchy where the lowest class is the class of almost finite type shifts introduced by B. Marcus....
Chapter 1 Variable Length Codes and Finite Automata (2008)
Marie-pierre Béal, Jean Berstel, Brian Marcus, Dominique Perrin, Christophe Reutenauer, ...
1.2 Definitions and notation...................... 3 1.3 Optimal prefix codes........................ 6 1.4 Prefix codes for integers...................... 19 1.5 Encoders and...
Habilitation Dissertation, Mathieu Raffinot, Alberto Apostolico (reviewer, Marie-pierre Béal, Maxime Crochemore, Gregory Kucherov (reviewer, ...
I would like to thank my three reviewers, Alberto Apostolico,
Presentations of constrained systems with unconstrained positions (2008)
Marie-pierre Béal, Maxime Crochemore, Gabriele Fici
Abstract — We give a polynomial-time construction of the set of sequences that satisfy a finite-memory constraint defined by a finite list of forbidden blocks, with a specified set of bit positions...
A quadratic algorithm for road coloring (2008)
Béal, Marie-Pierre, Perrin, Dominique
The road coloring theorem states that every aperiodic directed graph with constant out-degree has a synchronized coloring. This theorem had been conjectured during many years as the road coloring...
On the equivalence of Z-automata (2008)
Marie-pierre Béal, Jacques Sakarovitch
Abstract. We prove that two automata with multiplicity in Z are equivalent, i.e. define the same rational series, if and only if there is a sequence of Z-coverings, co-Z-coverings, and circulations...
Minimizing incomplete automata (2008)
Marie-pierre Béal, Maxime Crochemore
We develop a O(m log n)-time and O(k + n + m)-space algorithm for minimizing incomplete deterministic automata, where n is the number of states, m the number of edges, and k the size of the alphabet....
Determinization of Transducers Over Infinite Words (2007)
Marie-Pierre Béal, Olivier Carton
We study the determinization of transducers over infinite words. We consider transducers with all their states final. We give an effective characterization of sequential functions over infinite...
Variable Length Codes and Finite Automata (2007)
Marie-pierre Béal, Jean Berstel, Brian Marcus, Dominique Perrin, Christophe Reutenauer
The aim of this chapter is to present, in appropriate perspective, some selected new progress in the theory of variable length codes. The emphasis will be on practical aspects. The chapter is of a...
Regular coding partitions (2006)
Marie-pierre Béal, Fabio Burderi, Antonio Restivo
The canonical coding partition of a set of words is the finest partition such that the words contained in at least two factorizations of a same sequence belong to a same class. In the case the set is...
Conjugacy and equivalence of weighted automata and functional transducers (2006)
Marie-pierre Béal, Sylvain Lombardy, Jacques Sakarovitch
Abstract. We show that two equivalent K-automata are conjugate to a third one, when K is equal to B, N, Z, or any (skew) field and that the same holds true for functional tranducers as well. 1...
On the equivalence of Z-automata (2005)
Béal, Marie-Pierre, Lombardy, Sylvain, Sakarovitch, Jacques
We prove that two automata with multiplicity in Z are equivalent, i.e. define the same rational series, if and only if there is a sequence of Z-coverings, co-Z-coverings, and circulations of 1,...
Determinization of transducers over infinite words: the general case (2004)
Béal, Marie-Pierre, Carton, Olivier
We study the determinization of transducers over infinite words. We consider transducers with all their states final. We give an effective characterization of sequential functions over infinite...
Determinization of transducers over infinite words: the general case (2004)
Béal, Marie-Pierre, Carton, Olivier
We study the determinization of transducers over infinite words. We consider transducers with all their states final. We give an effective characterization of sequential functions over infinite...
The syntactic graph of a sofic shift (2004)
Marie-pierre Béal, Francesca Fiorenzi, Dominique Perrin
invariant under shift equivalence
A Weak Equivalence Between Shifts of Finite Type (2001)
Marie-Pierre Béal, Dominique Perrin, To A
We introduce the following notion of weak equivalence between shifts of finite type. Two shifts of finite type S and T are equivalent if and only if there are finite alphabets A and B and sliding...
A Finite State Version Of The Kraft-McMillan Theorem (2000)
Frédérique Bassino, Marie-Pierre Béal, Erique Bassino, Dominique Perrin
. The main result is a nite-state version of the Kraft-McMillan theorem characterizing the generating sequence of a k-ary regular tree. The proof uses a new construction called the multiset...
Length Distributions and Regular Sequences (2000)
Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin, Erique Bassino
. This paper presents a survey on length distributions of regular languages. The accent is on problems in coding theory and the relation with symbolic dynamics. Key words. Regular sequences, nite...
Computing the Prefix of an Automaton (2000)
Marie-Pierre Béal, Olivier Carton
We present an algorithm for computating the prex of an automaton. Automata considered are non-deterministic, labelled on words, and can have "-transitions. The prex automaton of an automaton A...
Super-State Automata and Rational Trees (1998)
Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin
. We introduce the notion of super-state automaton constructed from another automaton. This construction is used to solve an open question about enumerative sequences in rational trees. We prove that...
Super-State Automata and Rational Trees (1998)
Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin
We introduce the notion of super-state automaton constructed from another automaton. This construction is used to solve an open question about enumerative sequences of leaves of rational trees. We...
Super-State Automata and Rational Trees (1998)
Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin
We introduce the notion of super-state automaton constructed from another automaton. This construction is used to solve an open question about enumerative sequences in rational trees. We prove that...
Super-State Automata and Rational Trees (1998)
Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin
We introduce the notion of super-state automaton constructed from another automaton. This construction is used to solve an open question about enumerative sequences of leaves of rational trees. We...
Extensions of the Method of Poles for Code Construction (1997)
The method of poles is a method introduced by P. A. Franaszek for constructing a rate 1 : 1 finite state code from k-ary data into a constrained channel S, where S is recognized by a given local...
On the Bound of the Synchronization Delay of a Local Automaton (1997)
Marie-Pierre Béal, Jean Senellart, Documentaire Et Linguistique, R. Mcnaughton, R. Mccloskey That, ...
The synchronization delay of an N-state local automaton is known to be O(N 2 ). It has been conjectured by S. Kim, R. McNaughton and R. McCloskey that, for deterministic local automata, it is O(N 1:5...
Enumerative Sequences of Leaves and Nodes in Rational Trees (1997)
Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin
We prove that any IN-rational sequence s = (s n ) n1 of nonnegative integers satisfying the Kraft strict inequality P n1 s n k \Gamman ! 1 is the enumerative sequence of leaves by height of a...
Enumerative Sequences of Leaves and Nodes in Rational Trees (1997)
Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin
We prove that any N-rational sequence s = (s n ) n1 of nonnegative integers satisfying the Kraft strict inequality P n1 s n k \Gamman ! 1 is the enumerative sequence of leaves by height of a rational...
Enumerative Sequences of Leaves in Rational Trees (1997)
Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin
. We prove that any IN-rational sequence s = (sn)n1 of nonnegative integers satisfying the Kraft strict inequality P n1 snk \Gamman ! 1 is the enumerative sequence of leaves by height of a rational...