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.

Fichier(s) associé(s) à ce document :

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

• Ensembles reconnaissables de séries formelles sur un corps fini. (déposé le 18 déc. 2015 19:20)
  • Ensembles reconnaissables de séries formelles sur un corps fini. (déposé le 07 sept. 2018 12:38) [Actuellement Affiché]

Modifier les métadonnées (propriétaire du document)

Statistiques