Ensembles reconnaissables de séries formelles sur un corps fini

Bélair, Luc; Gélinas, Maxime et Point, Françoise (2016). « Ensembles reconnaissables de séries formelles sur un corps fini ». Comptes rendus de l'Académie des Sciences de Paris, Série I, t. 354, p 225-p 229.

Il s'agit de la dernière version de ce document.

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 à la version publiée./ Version almost identical to the published version.
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: 07 sept. 2018 12:38
Dernière modification: 07 sept. 2018 12:38
Adresse URL : http://archipel.uqam.ca/id/eprint/11579

Versions disponibles de ce document

Statistiques

Voir les statistiques sur cinq ans...