Ensembles reconnaissables de séries formelles sur un corps fini

Bélair, Luc; Gélinas, Maxime et Point, Françoise (2015). « Ensembles reconnaissables de séries formelles sur un corps fini ». Comptes rendus de l'Académie des Sciences de Paris, vol(no), p-p.

Fichier(s) associé(s) à ce document :
[img]
Prévisualisation
PDF
Télécharger (463kB)

Résumé

Soit l'alphabet donné par un corps fini F, nous montrons que les langages oméga-reconnaissables de mots infinis correspondent exactement aux ensembles définissables dans le groupe additif des séries formelles sur F muni de prédicats naturels. En particulier, on obtient la décidabilité par automate. / ABSTRACT. RECOGNIZABLE SETS OF POWER SERIES OVER FINITE FIELDS. Given the alphabet yilded by a finite field F, we show that infinite words languages which are omega-recognizable correspond exactly to sets definable in the additive group of power series over F together with some natural predicates. In particular, we obtain decidability by automata.

Type: Article de revue scientifique
Informations complémentaires: Version pratiquement identique à a version qui sera publiée./ Version almost identical to the version to appear.
Mots-clés ou Sujets: Logique, automates, théorie des modèles.
Unité d'appartenance: Faculté des sciences > Département de mathématiques
Déposé par: Luc Bélair
Date de dépôt: 18 déc. 2015 19:20
Dernière modification: 03 févr. 2017 05:10
Adresse URL : http://www.archipel.uqam.ca/id/eprint/7635

Statistiques

Voir les statistiques sur cinq ans...