6 citations · 20 across the 10 of their papers we have counts for
13 papers
Morphisms and minimisation of weighted automata
Sylvain Lombardy, Jacques Sakarovitch
This paper studies the algorithms for the minimisation of weighted automata. It starts with the definition of morphisms-which generalises and unifies the notion of bisimulation to…
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…
The carry propagation of the successor function
Valérie Berthé, Christiane Frougny, Michel Rigo +1
Given any numeration system, we call carry propagation at a number the number of digits that are changed when going from the representation of to the one of , and amor…
On subtrees of the representation tree in rational base numeration systems
Shigeki Akiyama, Victor Marsault, Jacques Sakarovitch
Every rational number p/q defines a rational base numeration system in which every integer has a unique finite representation, up to leading zeroes. This work is a contribution to…
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 enumerating series of an abstract numeration system
Pierre-Yves Angrand, Jacques Sakarovitch
It is known that any rational abstract numeration system is faithfully, and effectively, represented by an N-rational series. A simple proof of this result is given which yields a…
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…
On the decomposition of k-valued rational relations
Jacques Sakarovitch, Rodrigo De Souza
We give a new, and hopefully more easily understandable, structural proof of the decomposition of a -valued transducer into unambiguous functional ones, a result established…