A note on one-sided recognizable morphisms
We revisit the notion of one-sided recognizability of morphisms and its relation to two-sided recognizability.
Source author record
Marie-Pierre Béal
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
7works
4topics
4close collaborators
Published work
7 publications
preprint2022arXiv
Checking whether a word is Hamming-isometric in linear time
A finite word f is Hamming-isometric if for any two word u and v of same length avoiding f, u can be transformed into v by changing one by one all the letters on which u differs from v, in such a way that all of the new words obtained in this process also avoid~f. Words which are not Hamming-isometric have been characterized as words having a border with two mismatches. We derive from this characterization a linear-time algorithm to check whether a word is Hamming-isometric. It is based on pattern matching algorithms with k mismatches. Lee-isometric words over a four-letter alphabet have been characterized as words having a border with two Lee-errors. We derive from this characterization a linear-time algorithm to check whether a word over an alphabet of size four is Lee-isometric.
Open access
preprint2022arXiv
Unambiguously coded shifts
We study the coded systems introduced by Blanchard and Hansel. We give several constructions which allow one to represent a coded system as a strongly unambiguous one.
Open access
preprint2015arXiv
Sofic-Dyck shifts
We define the class of sofic-Dyck shifts which extends the class of Markov-Dyck shifts introduced by Inoue, Krieger and Matsumoto. Sofic-Dyck shifts are shifts of sequences whose finite factors form unambiguous context-free languages. We show that they correspond exactly to the class of shifts of sequences whose sets of factors are visibly pushdown languages. We give an expression of the zeta function of a sofic-Dyck shift.
Open access
preprint2013arXiv
A quadratic algorithm for road coloring
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 Problem before being settled by A. Trahtman. Trahtman's proof leads to an algorithm that finds a synchronized labeling with a cubic worst-case time complexity. We show a variant of his construction with a worst-case complexity which is quadratic in time and linear in space. We also extend the Road Coloring Theorem to the periodic case.
Open access
preprint2013arXiv
Finite-type-Dyck shift spaces
We study some basic properties of sofic-Dyck shifts and finite-type-Dyck shifts. We prove that the class of sofic-Dyck shifts is stable under proper conjugacies. We prove a Decomposition Theorem of a proper conjugacy between edge-Dyck shifts into a sequence of Dyck splittings and amalgamations.
Open access
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.
Open access
Research graph
See the researcher in context
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.