Source author record

Olivier Carton

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 Information Theory math.CO math.IT math.NT

Catalog footprint

Research overview

5works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Nested perfect toroidal arrays

We introduce two-dimensional toroidal arrays that are a variant of the de Bruijn tori. We call them nested perfect toroidal arrays. Instead of asking that every array of a given size has exactly one occurrence, we partition the positions in congruence classes and we ask exactly one occurrence in each congruence class. We also ask that this property applies recursively to each of the subarrays. We give a method to construct nested perfect toroidal arrays based on Pascal triangle matrix modulo 2. For the two-symbol alphabet, and for $n$ being a power of $2$ , our method yields $2^{n^2+n-1}$ different nested perfect toroidal arrays allocating all the different $n\times n$ arrays in each congruence class that arises from taking the line number modulo $n$ and the column number modulo $n$ .

preprint2022arXiv

Ambiguity through the lens of measure theory

In this paper, we establish a strong link between the ambiguity for finite words of a Büchi automaton and the ambiguity for infinite words of the same automaton. This link is based on measure theory. More precisely, we show that such an automaton is unambiguous, in the sense that no finite word labels two runs with the same starting state and the same ending state if and only if for each state, the set of infinite sequences labelling two runs starting from that state has measure zero. The measure used to define these negligible sets, that is sets of measure zero, can be any measure computed by a weighted automaton which is compatible with the Büchi automaton. This latter condition is very natural: the measure must put weight on cylinders [w] where w is the label of some run in the Büchi automaton.

preprint2020arXiv

A direct proof of Agafonov's theorem and an extension to shift of finite type

We provide a direct proof of Agafonov's theorem which states that finite state selection preserves normality. We also extends this result to the more general setting of shifts of finite type by defining selections which are compatible the shift. A slightly more general statement is obtained as we show that any Markov measure is preserved by finite state compatible selection.

preprint2020arXiv

Preservation of normality by unambiguous transducers

We consider finite state non-deterministic but unambiguous transducers with infinite inputs and infinite outputs, and we consider the property of Borel normality of sequences of symbols. When these transducers are strongly connected, and when the input is a Borel normal sequence, the output is a sequence in which every block has a frequency given by a weighted automaton over the rationals. We provide an algorithm that decides in cubic time whether a unambiguous transducer preserves normality.

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.