no. 3
Logique
Ensembles reconnaissables de séries formelles sur un corps fini

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

Bélair, Luc1 ; Gélinas, Maxime1 ; Point, Françoise2
1 Département de mathématiques, Université du Québec, C.P. 8888, succ. Centre-ville, Montréal, Québec, H3C 3P8, Canada
2 Département de mathématique (Le Pentagone), Université de Mons, 20, place du Parc, B-7000 Mons, Belgium
Comptes Rendus. Mathématique, Tome 354 (2016) no. 3, pp. 225-229.

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 :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2015.12.015
Bélair, Luc 1 ; Gélinas, Maxime 1 ; Point, Françoise 2

1 Département de mathématiques, Université du Québec, C.P. 8888, succ. Centre-ville, Montréal, Québec, H3C 3P8, Canada
2 Département de mathématique (Le Pentagone), Université de Mons, 20, place du Parc, B-7000 Mons, Belgium 
@article{CRMATH_2016__354_3_225_0,
     author = {B\'elair, Luc and G\'elinas, Maxime and Point, Fran\c{c}oise},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2015.12.015/}
}
TY  - JOUR
AU  - Bélair, Luc
AU  - Gélinas, Maxime
AU  - Point, Françoise
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2015.12.015/
DO  - 10.1016/j.crma.2015.12.015
LA  - fr
ID  - CRMATH_2016__354_3_225_0
ER  - 
%0 Journal Article
%A Bélair, Luc
%A Gélinas, Maxime
%A Point, Françoise
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2015.12.015/
%R 10.1016/j.crma.2015.12.015
%G fr
%F CRMATH_2016__354_3_225_0
Bélair, Luc; Gélinas, Maxime; Point, Françoise. Ensembles reconnaissables de séries formelles sur un corps fini. Comptes Rendus. Mathématique, Tome 354 (2016) no. 3, pp. 225-229. doi : 10.1016/j.crma.2015.12.015. http://www.numdam.org/articles/10.1016/j.crma.2015.12.015/

[1] Alur, R.; Degorre, A.; Maler, O.; Weiss, G. 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] Delon, F.; Simonetta, P. 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] Denef, J.; Schoutens, H. On the decidability of the existential theory of Fp〚t〛, Saskatoon, SK, 1999 (Fields Inst. Commun.), Volume vol. 33, Amer. Math. Soc., Providence, RI, USA (2003), pp. 43-60

[4] Elgot, C.C.; Rabin, M.O. 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] Gélinas, M. Séries formelles à coefficients dans un corps fini et automates, mémoire de maîtrise, Université du Québec à Montréal, 2015

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

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

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

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

[10] Villemaire, R. The theory of 〈N,+,Vk,Vℓ〉 is undecidable, Theor. Comput. Sci., Volume 106 (1992) no. 2, pp. 337-349

Cité par Sources :