Ensembles reconnaissables de séries formelles sur un corps fini

Luc Bélair; Maxime Gélinas; Françoise Point

doi:10.1016/j.crma.2015.12.015

Logique

Ensembles reconnaissables de séries formelles sur un corps fini

Présenté par : le comité de rédaction

Luc Bélair ¹ ; Maxime Gélinas ¹ ; Françoise Point ²

¹ Département de mathématiques, Université du Québec, C.P. 8888, succ. Centre-ville, Montréal, Québec, H3C 3P8, Canada
² Département de mathématique (Le Pentagone), Université de Mons, 20, place du Parc, B-7000 Mons, Belgium

Comptes Rendus. Mathématique, Volume 354 (2016) no. 3, pp. 225-229.

Résumé
Abstract

Soit l'alphabet donné par un corps fini $F$ , nous montrons que les langages ω-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.

Given the alphabet yielded by a finite field $F$ , we show that infinite words languages that are ω-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.

Reçu le : 2015-07-21
Accepté le : 2015-12-16
Publié le : 2016-02-03

DOI : 10.1016/j.crma.2015.12.015

Affiliations des auteurs :

Luc Bélair ¹ ; Maxime Gélinas ¹ ; Françoise Point ²

@article{CRMATH_2016__354_3_225_0,
     author = {Luc B\'elair and Maxime G\'elinas and Fran\c{c}oise Point},
     title = {Ensembles reconnaissables de s\'eries formelles sur un corps fini},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {225--229},
     publisher = {Elsevier},
     volume = {354},
     number = {3},
     year = {2016},
     doi = {10.1016/j.crma.2015.12.015},
     language = {fr},
}

TY  - JOUR
AU  - Luc Bélair
AU  - Maxime Gélinas
AU  - Françoise Point
TI  - Ensembles reconnaissables de séries formelles sur un corps fini
JO  - Comptes Rendus. Mathématique
PY  - 2016
SP  - 225
EP  - 229
VL  - 354
IS  - 3
PB  - Elsevier
DO  - 10.1016/j.crma.2015.12.015
LA  - fr
ID  - CRMATH_2016__354_3_225_0
ER  -

%0 Journal Article
%A Luc Bélair
%A Maxime Gélinas
%A Françoise Point
%T Ensembles reconnaissables de séries formelles sur un corps fini
%J Comptes Rendus. Mathématique
%D 2016
%P 225-229
%V 354
%N 3
%I Elsevier
%R 10.1016/j.crma.2015.12.015
%G fr
%F CRMATH_2016__354_3_225_0

Luc Bélair; Maxime Gélinas; Françoise Point. Ensembles reconnaissables de séries formelles sur un corps fini. Comptes Rendus. Mathématique, Volume 354 (2016) no. 3, pp. 225-229. doi : 10.1016/j.crma.2015.12.015. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2015.12.015/

Bibliographie
Cité par

[1] R. Alur; A. Degorre; O. Maler; G. Weiss On omega-languages defined by mean-payoff conditions, Foundations of Software Science and Computational Structures, Lecture Notes in Computer Science, vol. 5504, Springer, Berlin, 2009, pp. 333-347

[2] F. Delon; P. Simonetta Un principe d'Ax–Kochen–Ershov pour des structures intermédiaires entre groupes et corps valués, J. Symb. Log., Volume 64 (1999), pp. 991-1027

[3] J. Denef; H. Schoutens On the decidability of the existential theory of $F_{p} 〚 t 〛$ , Saskatoon, SK, 1999 (Fields Inst. Commun.), Volume vol. 33, Amer. Math. Soc., Providence, RI, USA (2003), pp. 43-60

[4] C.C. Elgot; M.O. Rabin Decidability and undecidability of extensions of second (first) order theory of (generalized) successor, J. Symb. Log., Volume 31 (1966) no. 2, pp. 169-181

[5] M. Gélinas Séries formelles à coefficients dans un corps fini et automates, mémoire de maîtrise, Université du Québec à Montréal, 2015

[6] B.R. Hodgson Décidabilité par automate fini, Ann. Sci. Math. Qué., Volume 7 (1983), pp. 39-57

[7] C. Michaux; F. Point Les ensembles k-reconnaissables sont définissables dans $〈 N, +, V_{k} 〉$ , C. R. Acad. Sci. Paris, Ser. I, Volume 303 (1986) no. 19, pp. 939-942

[8] D. Perrin; J.-E. Pin Infinite Words, Automata, Semigroups, Logic and Games, Elsevier, Amsterdam, 2004

[9] M. Rigo; L. Waxweiler Logical characterization of recognizable sets of polynomials over a finite field, Int. J. Found. Comput. Sci., Volume 22 (2011), pp. 1549-1563

[10] R. Villemaire The theory of $〈 N, +, V_{k}, V_{ℓ} 〉$ is undecidable, Theor. Comput. Sci., Volume 106 (1992) no. 2, pp. 337-349