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 :

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 :	https://archipel.uqam.ca/secure/id/eprint/7635

Versions disponibles de ce document

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

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

Statistiques