6 citations · 20 across the 10 of their papers we have counts for
8 papers · 1 filter
Derived terms without derivation a shifted perspective on the derived-term automaton
Sylvain Lombardy, Jacques Sakarovitch
We present here a construction for the derived term automaton (aka partial derivative, or Antimirov, automaton) of a rational (or regular) expression based on a sole induction on t…
Automata and rational expressions
Jacques Sakarovitch
This text is an extended version of the chapter 'Automata and rational expressions' in the AutoMathA Handbook that will appear soon, published by the European Science Foundation an…
Breadth-first serialisation of trees and rational languages
Victor Marsault, Jacques Sakarovitch
We present here the notion of breadth-first signature and its relationship with numeration system theory. It is the serialisation into an infinite word of an ordered infinite tree…
Rhythmic generation of infinite trees and languages
Victor Marsault, Jacques Sakarovitch
This work builds on the notion of breadth-first signature of infinite trees and (prefix-closed) languages introduced by the authors in a previous work. We focus here on periodic si…
Auto-similarity in rational base number systems
Shigeki Akiyama, Victor Marsault, Jacques Sakarovitch
This work is a contribution to the study of set of the representations of integers in a rational base number system. This prefix-closed subset of the free monoid is naturally repre…
Ultimate periodicity of b-recognisable sets : a quasilinear procedure
Victor Marsault, Jacques Sakarovitch
It is decidable if a set of numbers, whose representation in a base b is a regular language, is ultimately periodic. This was established by Honkala in 1986. We give here a structu…
On sets of numbers rationally represented in a rational base number system
Victor Marsault, Jacques Sakarovitch
In this work, it is proved that a set of numbers closed under addition and whose representations in a rational base numeration system is a rational language is not a finitely gener…
On the Minimal Uncompletable Word Problem
Gabriele Fici, Elena V. Pribavkina, Jacques Sakarovitch
Let S be a finite set of words over an alphabet Sigma. The set S is said to be complete if every word w over the alphabet Sigma is a factor of some element of S*, i.e. w belongs to…