[{"publication_status":"epub_ahead","external_id":{"arxiv":["2405.05279"]},"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"abstract":[{"lang":"eng","text":"It is known that for a uniform morphic sequence 𝒖 =⟨𝑢𝑛⟩∞\r\n𝑛=0 and an algebraic number 𝛽 such that |𝛽| >1, the number [[𝒖]]𝛽 :=∑∞\r\n𝑛=0(𝑢𝑛/𝛽𝑛) either lies in ℚ⁡(𝛽) or is transcendental. In this paper, we show a similar rational–transcendental dichotomy for sequences defined by irreducible Pisot morphisms on binary alphabets. Subject to the Pisot conjecture (an irreducible Pisot morphism has pure discrete spectrum), we generalise the latter result to arbitrary finite alphabets. In certain cases, we are able to show transcendence of [[𝒖]]𝛽 outright. In particular, for 𝑘 ≥2, if 𝒖 is the k-Bonacci word, then [[𝒖]]𝛽 is transcendental."}],"fulldoi":"https://doi.org/10.1017/etds.2026.10324","scopus_import":"1","doi":"10.1017/etds.2026.10324","department":[{"_id":"ToHe"},{"_id":"GradSch"}],"acknowledgement":"We thank the anonymous referee for identifying an error in an earlier\r\nversion of the paper. We gratefully acknowledge support from UKRI Frontier Research\r\nGrant EP/X033813/1, ERC grant DynAMiCS (101167561) and DFG grant 389792660 as\r\npart of TRR 248. J.O. is also affiliated with Keble College, Oxford as an Emmy Network\r\nfellow.","date_updated":"2026-08-03T06:17:50Z","mathsc":["11J81","37B10","11J87"],"supplementarymaterial":"no","publication_identifier":{"eissn":["1469-4417"],"issn":["0143-3857"]},"license":"https://creativecommons.org/licenses/by/4.0/","page":"1-22","year":"2026","keyword":["balanced-pair algorithm","Cobham’s conjecture","k-Bonacci words","Pisot conjecture","subspace theorem"],"OA_type":"hybrid","month":"07","type":"journal_article","arxiv":1,"status":"public","date_published":"2026-07-10T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1017/etds.2026.10324"}],"title":"Transcendence for Pisot morphic words over an algebraic base","citation":{"ieee":"P. Kebis, F. LUCA, J. OUAKNINE, A. SCOONES, and J. WORRELL, “Transcendence for Pisot morphic words over an algebraic base,” <i>Ergodic Theory and Dynamical Systems</i>. Cambridge University Press, pp. 1–22, 2026.","chicago":"Kebis, Pavol, FLORIAN LUCA, JOEL OUAKNINE, ANDREW SCOONES, and JAMES WORRELL. “Transcendence for Pisot Morphic Words over an Algebraic Base.” <i>Ergodic Theory and Dynamical Systems</i>. Cambridge University Press, 2026. <a href=\"https://doi.org/10.1017/etds.2026.10324\">https://doi.org/10.1017/etds.2026.10324</a>.","ista":"Kebis P, LUCA F, OUAKNINE J, SCOONES A, WORRELL J. 2026. Transcendence for Pisot morphic words over an algebraic base. Ergodic Theory and Dynamical Systems., 1–22.","apa":"Kebis, P., LUCA, F., OUAKNINE, J., SCOONES, A., &#38; WORRELL, J. (2026). Transcendence for Pisot morphic words over an algebraic base. <i>Ergodic Theory and Dynamical Systems</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/etds.2026.10324\">https://doi.org/10.1017/etds.2026.10324</a>","ama":"Kebis P, LUCA F, OUAKNINE J, SCOONES A, WORRELL J. Transcendence for Pisot morphic words over an algebraic base. <i>Ergodic Theory and Dynamical Systems</i>. 2026:1-22. doi:<a href=\"https://doi.org/10.1017/etds.2026.10324\">10.1017/etds.2026.10324</a>","mla":"Kebis, Pavol, et al. “Transcendence for Pisot Morphic Words over an Algebraic Base.” <i>Ergodic Theory and Dynamical Systems</i>, Cambridge University Press, 2026, pp. 1–22, doi:<a href=\"https://doi.org/10.1017/etds.2026.10324\">10.1017/etds.2026.10324</a>.","short":"P. Kebis, F. LUCA, J. OUAKNINE, A. SCOONES, J. WORRELL, Ergodic Theory and Dynamical Systems (2026) 1–22."},"oa":1,"has_accepted_license":"1","quality_controlled":"1","PlanS_conform":"1","date_created":"2026-07-27T05:53:25Z","ddc":["000"],"article_type":"original","OA_place":"publisher","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"2e0132b3-4e98-11ef-b275-cf7281c2802a","last_name":"Kebis","first_name":"Pavol","full_name":"Kebis, Pavol"},{"first_name":"FLORIAN","full_name":"LUCA, FLORIAN","last_name":"LUCA"},{"full_name":"OUAKNINE, JOEL","first_name":"JOEL","last_name":"OUAKNINE"},{"last_name":"SCOONES","full_name":"SCOONES, ANDREW","first_name":"ANDREW"},{"full_name":"WORRELL, JAMES","first_name":"JAMES","last_name":"WORRELL"}],"language":[{"iso":"eng"}],"das_tickbox":"0","day":"10","researchdata_availability":"no","publication":"Ergodic Theory and Dynamical Systems","publisher":"Cambridge University Press","_id":"22406","oa_version":"Published Version","article_processing_charge":"Yes (in subscription journal)"},{"oa_version":"None","_id":"21516","publisher":"Elsevier","article_processing_charge":"No","publication":"Wear","day":"01","language":[{"iso":"eng"}],"author":[{"id":"e2e68fc9-6505-11ef-a541-eb4e72cc3e82","last_name":"Roques-Carmes","first_name":"Charles","full_name":"Roques-Carmes, Charles"},{"last_name":"Bodin","full_name":"Bodin, N.","first_name":"N."},{"full_name":"Monteil, G.","first_name":"G.","last_name":"Monteil"},{"full_name":"Quiniou, J.F.","first_name":"J.F.","last_name":"Quiniou"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","ddc":["530"],"article_type":"original","date_created":"2026-03-30T12:22:47Z","extern":"1","quality_controlled":"1","intvolume":"       248","citation":{"ama":"Roques-Carmes C, Bodin N, Monteil G, Quiniou JF. Description of rough surfaces using conformal equivalent structure concept: Part 1. Stereological approach. <i>Wear</i>. 2001;248(1-2):82-91. doi:<a href=\"https://doi.org/10.1016/s0043-1648(00)00562-7\">10.1016/s0043-1648(00)00562-7</a>","ista":"Roques-Carmes C, Bodin N, Monteil G, Quiniou JF. 2001. Description of rough surfaces using conformal equivalent structure concept: Part 1. Stereological approach. Wear. 248(1–2), 82–91.","apa":"Roques-Carmes, C., Bodin, N., Monteil, G., &#38; Quiniou, J. F. (2001). Description of rough surfaces using conformal equivalent structure concept: Part 1. Stereological approach. <i>Wear</i>. Elsevier. <a href=\"https://doi.org/10.1016/s0043-1648(00)00562-7\">https://doi.org/10.1016/s0043-1648(00)00562-7</a>","short":"C. Roques-Carmes, N. Bodin, G. Monteil, J.F. Quiniou, Wear 248 (2001) 82–91.","mla":"Roques-Carmes, Charles, et al. “Description of Rough Surfaces Using Conformal Equivalent Structure Concept: Part 1. Stereological Approach.” <i>Wear</i>, vol. 248, no. 1–2, Elsevier, 2001, pp. 82–91, doi:<a href=\"https://doi.org/10.1016/s0043-1648(00)00562-7\">10.1016/s0043-1648(00)00562-7</a>.","chicago":"Roques-Carmes, Charles, N. Bodin, G. Monteil, and J.F. Quiniou. “Description of Rough Surfaces Using Conformal Equivalent Structure Concept: Part 1. Stereological Approach.” <i>Wear</i>. Elsevier, 2001. <a href=\"https://doi.org/10.1016/s0043-1648(00)00562-7\">https://doi.org/10.1016/s0043-1648(00)00562-7</a>.","ieee":"C. Roques-Carmes, N. Bodin, G. Monteil, and J. F. Quiniou, “Description of rough surfaces using conformal equivalent structure concept: Part 1. Stereological approach,” <i>Wear</i>, vol. 248, no. 1–2. Elsevier, pp. 82–91, 2001."},"date_published":"2001-03-01T00:00:00Z","title":"Description of rough surfaces using conformal equivalent structure concept: Part 1. Stereological approach","month":"03","type":"journal_article","status":"public","OA_type":"closed access","page":"82-91","year":"2001","keyword":["Rough surface topography","Stereology","Algorithm","Equivalent structure concept"],"issue":"1-2","publication_identifier":{"issn":["0043-1648"],"eissn":["1873-2577"]},"volume":248,"date_updated":"2026-04-15T13:21:44Z","doi":"10.1016/s0043-1648(00)00562-7","abstract":[{"lang":"eng","text":"The notion of elliptic or ellipsoidal conformal equivalent structure is introduced to model rough surface topography by use of convex homogenized shapes. The method is based on classical stereological results dealing with the relation between the number of intersections of an object with a set of parallel straight lines. The approach leads to an algorithm comparing the number of intercepts on both sampled surfaces and homogenized shapes selected for modeling. Some applications using the comparative values of the parameters of the homogenized structures are presented in this paper."}],"scopus_import":"1","fulldoi":"https://doi.org/10.1016/s0043-1648(00)00562-7","publication_status":"published"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Susanne","full_name":"Albers, Susanne","last_name":"Albers"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"article_type":"original","extern":"1","date_created":"2022-07-29T09:04:36Z","quality_controlled":"1","conference":{"name":"STOC97: 29th Annual Symposium on Theory of Computing","end_date":"1997-05-06","location":"El Paso, TX, United States","start_date":"1997-05-04"},"publication":"SIAM Journal on Computing","article_processing_charge":"No","publisher":"Society for Industrial and Applied Mathematics","_id":"11694","oa_version":"None","day":"01","language":[{"iso":"eng"}],"acknowledgement":"We thank Prabhakar Raghavan for bringing to our attention the literature on the s-t connectivity  problem. We also thank  an anonymous referee for many helpful comments which improved the presentation of the paper.","fulldoi":"https://doi.org/10.1137/s009753979732428x","scopus_import":"1","abstract":[{"text":"We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using the minimum number R of edge traversals. Deng and Papadimitriou [Proceedings of the 31st Symposium on the Foundations of Computer Science, 1990, pp. 356-361] showed an upper bound for R ofd O(d)m and Koutsoupias (reported by Deng and Papadimitriou) gave a lower bound of Ω≠(d2m), where m is the number of edges in the graph and d is the minimum number of edges that have to be added to make the graph Eulerian.  We give the 1rst subexponential algorithm for this exploration problem, which achieves an upper bound of dO(logd)m.  We also show a matching lower bound of d≠(logd)m for our algorithm. Additionally, we give lower bounds of 2≠(d)m, respectively, d≠(logd)m for various other natural exploration algorithms.","lang":"eng"}],"doi":"10.1137/s009753979732428x","publication_status":"published","title":"Exploring unknown environments","date_published":"2000-07-01T00:00:00Z","citation":{"mla":"Albers, Susanne, and Monika Henzinger. “Exploring Unknown Environments.” <i>SIAM Journal on Computing</i>, vol. 29, no. 4, Society for Industrial and Applied Mathematics, 2000, pp. 1164–88, doi:<a href=\"https://doi.org/10.1137/s009753979732428x\">10.1137/s009753979732428x</a>.","short":"S. Albers, M. Henzinger, SIAM Journal on Computing 29 (2000) 1164–1188.","apa":"Albers, S., &#38; Henzinger, M. (2000). Exploring unknown environments. <i>SIAM Journal on Computing</i>. El Paso, TX, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/s009753979732428x\">https://doi.org/10.1137/s009753979732428x</a>","ista":"Albers S, Henzinger M. 2000. Exploring unknown environments. SIAM Journal on Computing. 29(4), 1164–1188.","ama":"Albers S, Henzinger M. Exploring unknown environments. <i>SIAM Journal on Computing</i>. 2000;29(4):1164-1188. doi:<a href=\"https://doi.org/10.1137/s009753979732428x\">10.1137/s009753979732428x</a>","ieee":"S. Albers and M. Henzinger, “Exploring unknown environments,” <i>SIAM Journal on Computing</i>, vol. 29, no. 4. Society for Industrial and Applied Mathematics, pp. 1164–1188, 2000.","chicago":"Albers, Susanne, and Monika Henzinger. “Exploring Unknown Environments.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2000. <a href=\"https://doi.org/10.1137/s009753979732428x\">https://doi.org/10.1137/s009753979732428x</a>."},"intvolume":"        29","status":"public","month":"07","type":"journal_article","volume":29,"publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"year":"2000","issue":"4","keyword":["directed graph","exploration algorithm"],"page":"1164-1188","date_updated":"2024-11-06T12:09:07Z"},{"related_material":{"record":[{"relation":"earlier_version","id":"11928","status":"public"}]},"language":[{"iso":"eng"}],"day":"01","publisher":"Springer Nature","_id":"11680","oa_version":"None","article_processing_charge":"No","publication":"Algorithmica","quality_controlled":"1","date_created":"2022-07-28T06:50:51Z","extern":"1","article_type":"original","author":[{"last_name":"Alberts","first_name":"D.","full_name":"Alberts, D."},{"full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2024-11-06T12:26:40Z","page":"31-60","year":"1998","keyword":["Dynamic graph algorithm","Average-case analysis","Minimum spanning forest","Connectivity","Bipartiteness","Maximum matching."],"publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"volume":20,"month":"01","type":"journal_article","status":"public","intvolume":"        20","citation":{"mla":"Alberts, D., and Monika Henzinger. “Average-Case Analysis of Dynamic Graph Algorithms.” <i>Algorithmica</i>, vol. 20, Springer Nature, 1998, pp. 31–60, doi:<a href=\"https://doi.org/10.1007/pl00009186\">10.1007/pl00009186</a>.","short":"D. Alberts, M. Henzinger, Algorithmica 20 (1998) 31–60.","apa":"Alberts, D., &#38; Henzinger, M. (1998). Average-case analysis of dynamic graph algorithms. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/pl00009186\">https://doi.org/10.1007/pl00009186</a>","ista":"Alberts D, Henzinger M. 1998. Average-case analysis of dynamic graph algorithms. Algorithmica. 20, 31–60.","ama":"Alberts D, Henzinger M. Average-case analysis of dynamic graph algorithms. <i>Algorithmica</i>. 1998;20:31-60. doi:<a href=\"https://doi.org/10.1007/pl00009186\">10.1007/pl00009186</a>","ieee":"D. Alberts and M. Henzinger, “Average-case analysis of dynamic graph algorithms,” <i>Algorithmica</i>, vol. 20. Springer Nature, pp. 31–60, 1998.","chicago":"Alberts, D., and Monika Henzinger. “Average-Case Analysis of Dynamic Graph Algorithms.” <i>Algorithmica</i>. Springer Nature, 1998. <a href=\"https://doi.org/10.1007/pl00009186\">https://doi.org/10.1007/pl00009186</a>."},"date_published":"1998-01-01T00:00:00Z","title":"Average-case analysis of dynamic graph algorithms","publication_status":"published","doi":"10.1007/pl00009186","abstract":[{"text":"We present a model for edge updates with restricted randomness in dynamic graph algorithms and a general technique for analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1) it allows restrictions on the set of edges which can be used for insertions and (2) the type (insertion or deletion) of each update operation is arbitrary, i.e., not random. We use our technique to analyze existing and new dynamic algorithms for the following problems: maximum cardinality matching, minimum spanning forest, connectivity, 2-edge connectivity, k -edge connectivity, k -vertex connectivity, and bipartiteness. Given a random graph G with m 0 edges and n vertices and a sequence of l update operations such that the graph contains m i edges after operation i , the expected time for performing the updates for any l is O(llogn+∑li=1n/m−−√i) in the case of minimum spanning forests, connectivity, 2-edge connectivity, and bipartiteness. The expected time per update operation is O(n) in the case of maximum matching. We also give improved bounds for k -edge and k -vertex connectivity. Additionally we give an insertions-only algorithm for maximum cardinality matching with worst-case O(n) amortized time per insertion.","lang":"eng"}],"scopus_import":"1","fulldoi":"https://doi.org/10.1007/pl00009186","acknowledgement":"The authors would like to thank Emo Welzl for helpful discussions."}]