Robustness of Pisot-regular sequences

[en] We consider numeration systems based on a d-tuple U=(U_1,...,U_d) of sequences of integers and we define (U,K)-regular sequences through K-recognizable formal series, where K is any semiring. We show that, for any d-tuple U of Pisot numeration systems and any commutative semiring K, this definition does not depend on the greediness of the U-representations of integers. The proof is constructive and is based on the fact that the normalization is realizable by a 2d-tape finite automaton. In particular, we use an ad hoc operation mixing a 2d-tape automaton and a K-automaton in order to obtain a new K-automaton.

Disciplines :

Mathematics

Author, co-author :

Charlier, Emilie ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Cisternino, Célia ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Stipulanti, Manon ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

Robustness of Pisot-regular sequences

Publication date :

2021

Journal title :

Advances in Applied Mathematics

ISSN :

0196-8858

eISSN :

1090-2074

Publisher :

Elsevier, Atlanta, Georgia

Volume :

125

Pages :

102151

Peer reviewed :

Peer Reviewed verified by ORBi

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique

Available on ORBi :

since 22 June 2020

Statistics

Number of views

107 (16 by ULiège)

Number of downloads

65 (6 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

publications

supporting

mentioning

contrasting

Smart Citations

Citing PublicationsSupportingMentioningContrasting

View Citations

See how this article has been cited at scite.ai

scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.

Bibliography

Allouche, Jean-Paul, Scheicher, Klaus, Tichy, Robert F., Regular maps in generalized number systems. Math. Slovaca 50:1 (2000), 41–58.
Allouche, Jean-Paul, Shallit, Jeffrey, The ring of k-regular sequences. Theor. Comput. Sci. 98:2 (1992), 163–197.
Allouche, Jean-Paul, Shallit, Jeffrey, Automatic Sequences. Theory, Applications, Generalizations. 2003, Cambridge University Press, Cambridge.
Berstel, Jean, Reutenauer, Christophe, Noncommutative Rational Series with Applications. Encyclopedia of Mathematics and Its Applications., vol. 137, 2011, Cambridge University Press, Cambridge.
Bertrand-Mathis, Anne, Comment écrire les nombres entiers dans une base qui n'est pas entière. Acta Math. Hung. 54:3–4 (1989), 237–241.
Bruyère, Véronique, Hansel, Georges, Bertrand numeration systems and recognizability. Theor. Comput. Sci. 181:1 (1997), 17–43.
Büchi, J. Richard, Weak second-order arithmetic and finite automata. Z. Math. Log. Grundl. Math. 6 (1960), 66–92.
Charlier, Émilie, First-order logic and numeration systems. Sequences, Groups, and Number Theory Trends Math., 2018, Birkhäuser/Springer, Cham, 89–141.
Charlier, Émilie, Rampersad, Narad, Shallit, Jeffrey, Enumeration and decidable properties of automatic sequences. Int. J. Found. Comput. Sci. 23:5 (2012), 1035–1066.
Cobham, Alan, On the base-dependence of sets of numbers recognizable by finite automata. Math. Syst. Theory 3 (1969), 186–192.
Eilenberg, Samuel, Automata, Languages, and Machines. Vol. A. Pure and Applied Mathematics, vol. 58, 1974, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York.
Frougny, Christiane, Sakarovitch, Jacques, Number representation and finite automata. Combinatorics, Automata and Number Theory Encyclopedia Math. Appl., vol. 135, 2010, Cambridge Univ. Press, Cambridge, 34–107.
Frougny, Christiane, Solomyak, Boris, On representation of integers in linear numeration systems. Ergodic Theory of Zd Actions, Warwick, 1993–1994 London Math. Soc. Lecture Note Ser., vol. 228, 1996, Cambridge Univ. Press, Cambridge, 345–368.
Leroy, Julien, Rigo, Michel, Stipulanti, Manon, Counting the number of non-zero coefficients in rows of generalized Pascal triangles. Discrete Math. 340:5 (2017), 862–881.
Lothaire, M., Algebraic Combinatorics on Words. Encyclopedia of Mathematics and Its Applications., vol. 90, 2002, Cambridge University Press, Cambridge.
Rigo, Michel, Maes, Arnaud, More on generalized automatic sequences. J. Autom. Lang. Comb. 7:3 (2002), 351–376.
Sakarovitch, Jacques, Elements of Automata Theory. 2009, Cambridge University Press, Cambridge Translated from the 2003 French original by Reuben Thomas.
Zeckendorf, Édouard, Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. R. Sci. Liège 41 (1972), 179–182.

Name	Provider / Domaine	Expiration	Description
JSESSIONID	Oracle Corporation www.uliege.be	Session	General purpose platform session cookie, used by sites written in JSP. Usually used to maintain an anonymous user session by the server.
CookieScriptConsent	CookieScript .uliege.be	1 year	This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.

Name	Provider / Domaine	Expiration	Description
_pk_id	InnoCraft Ltd .uliege.be	1 year	Used to store a few details about the user such as the unique visitor ID
_pk_ses	InnoCraft Ltd .uliege.be	30 minutes	Short lived cookies used to temporarily store data for the visit
_pk_ref	InnoCraft Ltd .uliege.be	6 months	Used to store the attribution information, the referrer initially used to visit the website