Cobham's theorem; Iterated function system; real number; Büchi automata; Pisot number; Parry number
Abstract :
[en] Feng and Wang showed that two homogeneous iterated function systems in $\mathbb{R}$
with multiplicatively independent contraction ratios necessarily have different attractors.
In this paper, we extend this result to graph directed iterated function systems in $\mathbb{R}^n$ with contraction ratios that are of the form $\frac{1}{\beta}$, for integers $\beta$. By using a result of Boigelot {\em et al.}, this allows us to give a proof of a conjecture of Adamczewski and Bell. In doing so, we link the graph directed iterated function systems to Büchi automata. In particular, this link extends to real numbers $\beta$.
We introduce a logical formalism that permits to characterize sets of $\mathbb{R}^n$
whose representations in base $\beta$ are recognized by some Büchi automata.
This result depends on the algebraic properties of the base: $\beta$ being a Pisot or a Parry number. The main motivation of this work is to draw a general picture representing
the different frameworks where an analogue of Cobham's theorem is known.
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Leroy, Julien ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
An analogue of Cobham's theorem for graph directed iterated function systems
Publication date :
2015
Journal title :
Advances in Mathematics
ISSN :
0001-8708
eISSN :
1090-2082
Publisher :
Academic Press, San Diego, United States - California
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
Adamczewski B., Bell J. An analogue of Cobham's theorem for fractals. Trans. Amer. Math. Soc. 2011, 363(8):4421-4442.
Arnoux P., Ito S. Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 2001, 8(2):181-207.
Barnsley M.F., Demko S. Iterated function systems and the global construction of fractals. Proc. R. Soc. Lond. Ser. A 1985, 399(1817):243-275.
Berend D., Frougny C. Computability by finite automata and Pisot bases. Math. Syst. Theory 1994, 27(3):275-282.
Bertrand-Mathis A. Comment écrire les nombres entiers dans une base qui n'est pas entière. Acta Math. Hungar. 1989, 54(3-4):237-241.
Boigelot B., Brusten J. A generalization of Cobham's theorem to automata over real numbers. Theoret. Comput. Sci. 2009, 410(18):1694-1703.
Boigelot B., Bronne L., Rassart S. An improved reachability analysis method for strongly linear hybrid systems. Lecture Notes in Comput. Sci. 1997, vol. 1254:167-177.
Boigelot B., Rassart S., Wolper P. On the expressiveness of real and integer arithmetic automata (extended abstract). ICALP 1998, 152-163.
Boigelot B., Jodogne S., Wolper P. On the use of weak automata for deciding linear arithmetic with integer and real variables. Lecture Notes in Comput. Sci. 2001, vol. 2083:611-625. Springer, Berlin.
Boigelot B., Jodogne S., Wolper P. An effective decision procedure for linear arithmetic over the integers and reals. ACM Trans. Comput. Log. 2005, 6(3):614-633.
Boigelot B., Brusten J., Bruyère V. On the sets of real numbers recognized by finite automata in multiple bases. Lecture Notes in Comput. Sci. 2008, vol. 5126:112-123. Springer-Verlag.
Boigelot B., Brusten J., Leroux J. A generalization of Semenov's theorem to automata over real numbers. Lecture Notes in Comput. Sci. 2009, vol. 5663:469-484. R.A. Schmidt (Ed.).
Boigelot B., Brusten J., Bruyère V. On the sets of real numbers recognized by finite automata in multiple bases. Log. Methods Comput. Sci. 2010, 6(1).
Bruyère V., Hansel G., Michaux C., Villemaire R. Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. Simon Stevin 1994, 1(2):191-238.
Chan D.H.-Y., Hare K.G. A multi-dimensional analogue of Cobham's theorem for fractals. Proc. Amer. Math. Soc. 2014, 142(2):449-456.
Cobham A. On the base-dependence of sets of numbers recognizable by finite automata. Math. Syst. Theory 1969, 3:186-192.
Daubechies I., Yilmaz Ö. Robust and practical analog-to-digital conversion with exponential precision. IEEE Trans. Inform. Theory 2006, 52(8):3533-3545.
Daubechies I., Güntürk S., Wang Y., Yilmaz Ö. The golden ratio encoder. IEEE Trans. Inform. Theory 2010, 56(10):5097-5110.
Durand F. Cobham's theorem for substitutions. J. Eur. Math. Soc. (JEMS) 2011, 13(6):1799-1814.
Edgar G. Measure, Topology, and Fractal Geometry. Undergrad. Texts Math. 2008, Springer, New York. second ed.
Elekes M., Keleti T., Máthé A. Self-similar and self-affine sets: measure of the intersection of two copies. Ergodic Theory Dynam. Systems 2010, 30(2):399-440.
Feng D.-J., Wang Y. On the structures of generating iterated function systems of Cantor sets. Adv. Math. 2009, 222(6):1964-1981.
Ferrante J., Rackoff C. A decision procedure for the first order theory of real addition with order. SIAM J. Comput. 1975, 4:69-76.
Frougny C. Representations of numbers and finite automata. Math. Syst. Theory 1992, 25(1):37-60.
Frougny C., Sakarovitch J. Number representation and finite automata. Encyclopedia Math. Appl. 2010, vol. 135:34-107. Cambridge Univ. Press, Cambridge.
Hutchinson J.E. Fractals and self-similarity. Indiana Univ. Math. J. 1981, 30(5):713-747.
Löding C. Efficient minimization of deterministic weak ω-automata. Inform. Process. Lett. 2001, 79(3):105-109.
Lothaire M. Algebraic Combinatorics on Words. Encyclopedia Math. Appl. 2002, vol. 90. Cambridge Univ. Press.
Parry W. On the β-expansions of real numbers. Acta Math. Acad. Sci. Hung. 1960, 11:401-416.
Pin J.-E., Perrin D. Infinite Words: Automata, Semigroups, Logic and Games 2004, Elsevier.
Pisot C. Répartition (mod1) des puissances successives des nombres réels. Comment. Math. Helv. 1946, 19:153-160.
Rauzy G. Nombres algébriques et substitutions. Bull. Soc. Math. France 1982, 110(2):147-178.
Sirvent V.F., Wang Y. Self-affine tiling via substitution dynamical systems and Rauzy fractals. Pacific J. Math. 2002, 206(2):465-485.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
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.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.