Comptes Rendus
Logique
Ensembles reconnaissables de séries formelles sur un corps fini
[Recognizable sets of power series over finite fields]
Comptes Rendus. Mathématique, Volume 354 (2016) no. 3, pp. 225-229.

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.

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.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2015.12.015
Luc Bélair 1; Maxime Gélinas 1; Françoise Point 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 = {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/

[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 Fpt, 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,+,Vk, 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,+,Vk,V is undecidable, Theor. Comput. Sci., Volume 106 (1992) no. 2, pp. 337-349

Cited by Sources:

Comments - Policy


Articles of potential interest

Automaticité des ordinaux et des graphes homogènes

Christian Delhommé

C. R. Math (2004)


Systèmes de numération et automates

Ali Messaoudi

C. R. Math (2002)


S-arrangements avec répétitions

Sylviane R. Schwer

C. R. Math (2002)