Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
An efficient algorithm to decide the periodicity of b-recognisable sets using MSDF convention
du groupe Séminaire Méthodes Formelles

Date 2017-05-30  11:00-12:00
TitreAn efficient algorithm to decide the periodicity of b-recognisable sets using MSDF convention 
RésuméGiven an integer base b>1, a set of integers is represented in base b by a language over {0,1,...,b-1}. The set is said b-recognisable if its representation is a regular language. It is known that eventually periodic sets are b-recognisable in every base b, and Cobham's theorem imply the converse: no other set is b-recognisable in every base b. We are interested in deciding whether a b-recognisable set of integers (given as a finite automaton) is eventually periodic. Honkala showed in 1986 that this problem is decidable and recent developments give efficient decision algorithms. However, they only work when the integers are written with the least significant digit first. In this work, we consider here the natural order of digits (Most Significant Digit First) and give a quasi-linear algorithm to solve the problem in this case. 
Lieu178 
OrateurVictor Marsault 
Emailhttp://victor.marsault.xyz/en/Home/index.html 
UrlUniversity of Liège 



Aucun document lié à cet événement.

Retour
Retour à l'index